Windows10 Wampserver下PHP斐波那契数列大参数运行超时优化咨询

问题根因定位 #

原有fibonacci函数虽然预留了offset、injectResult的结果复用入口，但没有落地实际的计算缓存，核心逻辑仍是无记忆的普通递归，时间复杂度达到O(2ⁿ)。当计算到fib(58)这类偏大的索引值时，会产生海量重复的子调用，在Wampserver默认30秒执行超时的限制下，很容易触发测试流程中断。
sumFibonacci的区间累加逻辑本身没有逻辑缺陷，只要把fibonacci模块的性能瓶颈解决，大参数场景自然可以跑通。

具体优化实现 #

1. 给fibonacci模块加函数级持久缓存 #

• 利用PHP的函数静态变量存储已计算的斐波那契值，既不污染全局作用域，也能在函数多次调用间复用计算结果
• 完整保留原有offset、injectResult参数的兼容逻辑，不破坏原有接口的调用规则
• 计算流程改成：每次调用先查缓存，命中直接返回；未命中再触发递归计算，结果算完立刻写入缓存

可直接替换原有fibonacci函数的实现：

function fibonacci(int $n, int $offset = 0, ?array $injectResult = null) {
    // 静态变量跨调用保存计算缓存
    static $cache = [0 => 0, 1 => 1];
    // 兼容原有injectResult注入外部计算结果的逻辑
    if (!is_null($injectResult)) {
        foreach ($injectResult as $key => $val) {
            $cache[$key + $offset] = $val;
        }
    }
    // 缓存命中直接返回，不再触发递归
    if (isset($cache[$n])) {
        return $cache[$n];
    }
    // 未命中的计算结果写入缓存
    $cache[$n] = fibonacci($n - 1, $offset, $injectResult) + fibonacci($n - 2, $offset, $injectResult);
    return $cache[$n];
}

改完这部分后，斐波那契计算的时间复杂度会直接从O(2ⁿ)降到O(n)，哪怕计算到fib(100)，耗时也能控制在毫秒级。

2. 对区间求和流程做性能适配 #

• 原有sumFibonacci如果是逐次调用fibonacci计算区间内每个值再累加，虽然加了缓存后不会超时，但可以进一步压缩计算耗时：因为调用fibonacci($b)的递归过程，会顺着计算路径把0到b的所有斐波那契值全部写入缓存，直接从缓存中读取a到b的区间值累加即可，不需要逐次触发fibonacci的函数调用

优化后的sumFibonacci实现：

function sumFibonacci(int $a, int $b) {
    // 触发最高索引值的计算，补全全量缓存
    fibonacci($b);
    $sum = 0;
    // 直接读取函数静态缓存的区间值累加
    $funcReflection = new ReflectionFunction('fibonacci');
    $cache = $funcReflection->getStaticVariables()['cache'];
    for ($i = $a; $i <= $b; $i++) {
        $sum += $cache[$i];
    }
    return $sum;
}

测试验证 #

• 直接运行sumFibonacci(38,58)场景，优化前该调用在无缓存递归下通常需要10秒以上，接近Wampserver默认超时阈值；优化后整体耗时一般在1毫秒以内，完全不会触发执行超时限制
• 不需要额外调高php.ini里的max_execution_time配置，优化后的计算量远低于默认30秒的执行时间限制

内容的提问来源于stack exchange，提问作者vinay mungra