在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像递归一样添加一些次数.该lambda在reduce将被称为n时间就像递归方法......所以,既然我们没有尾巴调用优化在这两个情况下,堆栈将创建/销毁和返回n时间.并且if生成器中的a应检查何时引发StopIteration异常.

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

在一个测试中,我用递归方法代替rest*x,x花费的时间与使用的方法相当reduce.

这是我的事实时间(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

UPDATE

尝试factorial_recursive?()使用x=4000命中默认递归限制来运行版本,因此必须增加限制:

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