递归版本的速度较慢是由于需要在每次调用时解析命名(自变量)变量。我提供了一种不同的递归实现,该实现仅具有一个参数,并且运行速度稍快。
$ 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 2),其中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
尝试运行符合默认递归限制的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