在Python中找到最佳的阶乘计算方法？

Question

我正在研究阶乘的速度。但我只使用了两种方法：

import timeit

def fact(N):
    B = N
    while N > 1:
        B = B * (N-1)
        N = N-1
    return B

def fact1(N):
    B = 1
    for i in range(1, N+1):
        B = B * i
    return B


print timeit.timeit('fact(5)', setup="from __main__ import fact"), fact(5)
print timeit.timeit('fact1(5)', setup="from __main__ import fact1"), fact1(5)

这里是输出结果，

0.540276050568 120
0.654400110245 120

从上面的代码中我观察到：

1. 使用while比for循环更快

我的问题是，

在Python中找到阶乘的最佳方式是什么？

- codeimplementer

---

使用更大的数字N，这样你就可以测试循环而不是函数开销。 - Floris

为什么要两次使用 N-1？你可以交换这两行代码并节省一次减法操作。 - John La Rooy

你想找到更有效的算法吗？ - atupal

@yes atupal。我想要一个更加有效的算法。 - codeimplementer

Answer 1

如果你在寻找最好的，为什么不使用数学模块中提供的那个呢？

>>> import math
>>> math.factorial
<built-in function factorial>
>>> math.factorial(10)
3628800

我的电脑上的时间比较：

>>> print timeit.timeit('fact(5)', setup="from __main__ import fact"), fact(5)
0.840167045593 120
>>> print timeit.timeit('fact1(5)', setup="from __main__ import fact1"), fact1(5)
1.04350399971 120
>>> print timeit.timeit('factorial(5)', setup="from math import factorial")
0.149857997894

我们看到内置函数要比您提出的两个纯Python变体都要好得多。

- mgilson

Answer 2

TLDR; 微基准测试并不是很有用。

对于Cpython，请尝试以下操作：

>>> from math import factorial


>>> print timeit.timeit('fact(5)', setup="from __main__ import fact"), fact(5)
1.38128209114 120
>>> print timeit.timeit('fact1(5)', setup="from __main__ import fact1"), fact1(5)
1.46199703217 120
>>> print timeit.timeit('factorial(5)', setup="from math import factorial"), factorial(5)
0.397044181824 120

但在pypy下，while比math更快。

>>>> print timeit.timeit('fact(5)', setup="from __main__ import fact"), fact(5)\
0.170556783676 120
>>>> print timeit.timeit('fact1(5)', setup="from __main__ import fact1"), fact1\
(5)
0.319650173187 120
>>>> print timeit.timeit('factorial(5)', setup="from math import factorial"), f\
actorial(5)
0.210616111755 120

因此，这取决于实现方式。现在尝试更大的数字。

>>>> print timeit.timeit('fact(50)', setup="from __main__ import fact"), fact(50)
7.71517109871 30414093201713378043612608166064768844377641568960512000000000000
>>>> print timeit.timeit('fact1(50)', setup="from __main__ import fact1"), fact1(50)
6.58060312271 30414093201713378043612608166064768844377641568960512000000000000
>>>> print timeit.timeit('factorial(50)', setup="from math import factorial"), factorial(50)
6.53072690964 30414093201713378043612608166064768844377641568960512000000000000

while 是最慢的方法，使用 for 的版本与 math 模块中的版本差不多

- John La Rooy

Answer 3

否则，如果您正在寻找Python实现（这是我最喜欢的）：

from operator import mul


def factorial(n):
    return reduce(mul, range(1, (n + 1)), 1)

使用方法：

>>> factorial(0)
1
>>> factorial(1)
1
>>> factorial(2)
2
>>> factorial(3)
6
>>> factorial(4)
24
>>> factorial(5)
120
>>> factorial(10)
3628800

性能：（在我的桌面上：）

$ python -m timeit -c -s "fact = lambda n: reduce(lambda a, x: a * x, range(1, (n + 1)), 1)" "fact(10)"
1000000 loops, best of 3: 1.98 usec per loop

- James Mills

Answer 4

我尝试过使用 reduce(lambda x, y: x*y, range(1, 5))

>>>timeit("import math; math.factorial(4)")
1.0205099133840179

>>>timeit("reduce(lambda x, y: x*y, range(1, 5))")
1.4047879075160665

>>>timeit("from operator import mul;reduce(mul, range(1, 5))")
2.530837320051319

- Nilesh