найти лучший способ для факториала в 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. Хотя занимает меньше времени, чем для

Мой вопрос:

Является лучшим способом найти факториал в python?

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 

Мы видим, что встроенная команда значительно лучше, чем любой из чистых вариантов питона вы предложили.

Answer 2

TLDR; microbenchmarks не очень полезны

Для 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 модуля

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 

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