python中大量的字体

Question

这是我处理阶乘的方法：

def factorial(n):
    '''Returns factorial of n'''
    r = 1
    for i in range(1, n + 1):
        r *= i
    return r

我认为这很简单，尽管我想您可以使某些事情变得更有效，因为它需要花费大量时间才能存储100000这样的数字。我的问题是，在那里吗？ math.factorial（）也不好，它花费的时间大致相同。

Answer 1

按顺序乘以数字，

r = 1
for i in range(1, n + 1):
    r *= i
return r

非常快地创建大量数字（成千上万个位），然后您将得到一个大数和一个小数的许多乘法。至少其中一个因素很大的乘法运算很慢。

例如，您可以通过减少涉及大量数字的乘法运算的数量来显着加快其速度

def range_prod(lo,hi):
    if lo+1 < hi:
        mid = (hi+lo)//2
        return range_prod(lo,mid) * range_prod(mid+1,hi)
    if lo == hi:
        return lo
    return lo*hi

def treefactorial(n):
    if n < 2:
        return 1
    return range_prod(1,n)

产生，对100000! % 100019的计算进行计时（我首先尝试了len(str(fun(100000))，但是到字符串的转换非常慢，因此使差异看起来比实际要小）：

$ python factorial.py 
81430
math.factorial took 4.06193709373 seconds
81430
factorial took 3.84716391563 seconds
81430
treefactorial took 0.344486951828 seconds

所以100000!的加速超过10倍。

Answer 2

如果需要较短的执行时间并且不需要最佳的准确性，则可以使用近似公式，例如Stirling approximation

Answer 3

脚架非常大，因此处理数字的对数通常会更好。

许多语言都有库函数，可计算n-1阶乘的自然对数。这意味着您可以通过

lgamma（n + 1）

计算阶乘（n）的自然对数。您可以将log10除以10为底的对数。

因此，如果您只想要位数，那么此Python代码将立即给出答案：

from math import *
print ceil(lgamma(100000+1)/log(10))

Answer 4

如果您只需要一个近似值，Ramanujan的阶乘近似应该比Stirling的更精确。

Answer 5

确实需要真正的阶乘值n实际上是不寻常的！在许多应用领域中。通常，使用阶乘的自然对数更现实。我想不出无法将日志用作更好的选择的任何应用程序，因为阶乘最常用于计算相关的值选择事物组合的可能性。

Answer 6

您确实意识到阶乘（100000）是aproximately 2.8242294080×10 ^ 456,573这就是为什么它很慢，它很大。

Answer 7

您可以返回gamma函数（math.gamma(x)），但是使用for循环生成阶乘可能会更快

Answer 8

由四元效应引起的减慢：随着n变大，您必须执行更多的乘法运算，但是您还必须乘以更大的数字。

Answer 9

您可以使用reduce函数而不是显式循环：