Сравнение производительности факториала Python (математика против Scipy)

Question

Почему math.factorial намного быстрее, чем scipy.special.factorial?

import timeit

t = timeit.timeit("from math import factorial; factorial(20)"); print(t)
0.6399730000412092

t = timeit.timeit("from scipy.special import factorial; factorial(20)"); print(t)
5.339432950946502

t = timeit.timeit("from scipy.special import factorial; factorial(20, exact=True)"); print(t)
1.7984685270348564

Я на Python 3.7 (версия scipy 1.1.0)

Answer 1

Помимо уже упомянутых фактов о векторизованных входах scipy target - здесь используется очень маленький тестовый пример - если вы его расширите, это будет не так ясно:

import timeit

for z in range(20,100000,10000):
    t1 = timeit.timeit(f"from math import factorial; factorial({z})",number=10)
    t2 = timeit.timeit(f"from scipy.special import factorial; factorial({z})",number=10)
    t3 = timeit.timeit(f"from scipy.special import factorial; factorial({z}, exact=True)",number=10)
    print(f"{z}  : {t1:<20}  {t2:<20}  {t3:<20}")

Вывод:

# facNr    factorial          scipy.special.factorial(*)   exact = True
   20  : 0.0003352240000822    0.18152283800009172     6.924199988134205e-05
10020  : 0.0368837539999731    0.00016821899953356478  0.03690350099986972 
20020  : 0.1258954189997894    0.00016980899999907706  0.12552139000035822 
30020  : 0.2532270950005113    0.00017434100027458044  0.2531732979996377  
40020  : 0.4068329990004713    0.00017545999980939087  0.406938215000082   
50020  : 0.6163399690003644    0.0001782059998731711   0.616294079999534   
60020  : 0.8626650409996728    0.00017887300055008382  0.8635997929995938  
70020  : 1.1321934719999263    0.00017422100063413382  1.130675204999534   
80020  : 1.369009857000492     0.00017408599978807615  1.369635687000482   
90020  : 1.7379734959995403    0.00017380499957653228  1.7343564000002516  

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

При выполнении таймингов всегда рассматривайте случаи с краями из нескольких и большого количества данных вместе с "нормальным"сумма "

---

(*) возвращает inf для z> 170 - поэтому не рассчитывается всерьез, а время перекошено

Answer 2

Когда exact=True функция scipy действительно действует как обёртка вокруг math.factorial (см. https://github.com/scipy/scipy/blob/v1.2.0/scipy/special/…), поэтому я предполагаю, что дополнительное время - это только накладные расходы на логику проверки аргументов и вызов дополнительной функции.

Когда exact=False или не указано, используется аппроксимация, которая будет медленнее, чем точное вычисление для небольших значений n.

Answer 3

math.factorial - встроенная функция Python, она не компилируется в байт-код Python и фактически выполняет код c.

Вы можете увидеть похожее поведение с другими функциями, такими как numpy cos / sin и т.д ...

Answer 4

Это распространенная ошибка, похожая на ожидание, что такие вещи, как np.exp(), будут работать быстрее, чем от модуля math.Это не цель таких функций.Научный стек (NumPy, Pandas, SciPy и другие) касается векторизованных подходов к массивам, а не отдельных значений.

from math import factorial

factorial([20, 20, 20])

Это даст TypeError: an integer is required (got type list)

Но:

from scipy.special import factorial

factorial([20, 20, 20])

Будет вычислять факториал для всего списка, давая:

array([2.43290201e+18, 2.43290201e+18, 2.43290201e+18])

Если вы поместили вычисление math.factorial в цикл for, чтобы охватить несколько элементовв списке он очень быстро отстает по времени от векторизованного подхода (что было бы еще быстрее, если бы вы сначала указали массив NumPy, а не список)