python - python中的慢递归

Question

我知道这个主题讨论得很好，但我遇到了一个案例，我不太明白递归方法为什么比使用“reduce、lambda、xrange”的方法“慢”。

def factorial2(x, rest=1):
    if x <= 1:
        return rest
    else:
        return factorial2(x-1, rest*x)


def factorial3(x):
    if x <= 1:
        return 1
    return reduce(lambda a, b: a*b, xrange(1, x+1))

我知道 python 不会优化尾递归，所以问题不在于此。据我了解，生成器仍应使用 +1 运算符生成 n 个数字。所以从技术上讲，fact(n) 应该像递归一样添加一个数字 n 次。 reduce 中的 lambda 将被调用 n 次，就像递归方法一样...所以因为我们没有尾调用优化在这两种情况下，堆栈都将被创建/销毁并返回 n 次。生成器中的 if 应该检查何时引发 StopIteration 异常。

这让我想知道为什么递归方法仍然比另一种方法慢，因为递归方法使用简单的算术而不使用生成器。

在一次测试中，我在递归方法中用 x 替换了 rest*x 并且花费的时间减少了与使用 reduce.

这是我对 fact(400) 的计时，1000 次

factorial3 : 1.22370505333

factorial2 : 1.79896998405

编辑:

使方法从 1 开始到 n 代替 n 到 1 也没有帮助。所以 -1 不是开销。

另外，我们能否使递归方法更快。我尝试了多种方法，例如我可以更改的全局变量...通过将变量放置在我可以像数组一样修改的单元格中使用可变上下文，并保持没有参数的递归方法。将用于递归的方法作为参数发送，这样我们就不必在我们的范围内“取消引用”它了……？!但是没有什么能让它更快。

我要指出的是，我有一个使用 forloop 的事实版本，它比这两种方法都快得多，因此显然还有改进的空间，但我不希望有比 forloop 更快的东西。

Answer 1

递归版本的缓慢来自于需要在每次调用时解析命名(参数)变量。我提供了一种不同的递归实现，它只有一个参数并且运行速度稍快。

$ cat fact.py 
def factorial_recursive1(x):
    if x <= 1:
        return 1
    else:
        return factorial_recursive1(x-1)*x

def factorial_recursive2(x, rest=1):
    if x <= 1:
        return rest
    else:
        return factorial_recursive2(x-1, rest*x)

def factorial_reduce(x):
    if x <= 1:
        return 1
    return reduce(lambda a, b: a*b, xrange(1, x+1))

# Ignore the rest of the code for now, we'll get back to it later in the answer
def range_prod(a, b):
    if a + 1 < b:
        c = (a+b)//2
        return range_prod(a, c) * range_prod(c, b)
    else:
        return a
def factorial_divide_and_conquer(n):
    return 1 if n <= 1 else range_prod(1, n+1)

$ ipython -i fact.py 
In [1]: %timeit factorial_recursive1(400)
10000 loops, best of 3: 79.3 µs per loop
In [2]: %timeit factorial_recursive2(400)
10000 loops, best of 3: 90.9 µs per loop
In [3]: %timeit factorial_reduce(400)
10000 loops, best of 3: 61 µs per loop

由于在您的示例中涉及非常大的数字，最初我怀疑性能差异可能是由于乘法顺序造成的。在每次迭代中将较大的部分乘积乘以下一个数字与乘积中的数字/位数成正比，因此这种方法的时间复杂度为 O(n²)，其中 n 为最终产品中的位数。相反，最好使用分而治之的技术，其中最终结果是作为两个大致相等长度的值的乘积获得的，每个值都以相同的方式递归计算。所以我也实现了那个版本(参见上面代码中的 factorial_divide_and_conquer(n))。正如您在下面看到的，它在小参数方面仍然输给基于 reduce() 的版本(由于命名参数的相同问题)，但在大参数方面优于它。

In [4]: %timeit factorial_divide_and_conquer(400)
10000 loops, best of 3: 90.5 µs per loop
In [5]: %timeit factorial_divide_and_conquer(4000)
1000 loops, best of 3: 1.46 ms per loop
In [6]: %timeit factorial_reduce(4000)
100 loops, best of 3: 3.09 ms per loop

更新

尝试使用 x=4000 运行 factorial_recursive?() 版本会达到默认递归限制，因此该限制必须为 increased :

In [7]: sys.setrecursionlimit(4100)
In [8]: %timeit factorial_recursive1(4000)
100 loops, best of 3: 3.36 ms per loop
In [9]: %timeit factorial_recursive2(4000)
100 loops, best of 3: 7.02 ms per loop