使用Python和Numpy高效计算阶乘

Question

在Python / NumPy中，有没有一种方法可以构建包含阶乘的表达式 - 但由于在我的场景中，许多阶乘将被重复或减少，因此等待我指示运行时计算它。

假设 F(x) := x! 如果我构建像 (F(6) + F(7)) / F(4) 这样的表达式 - 我可以通过执行以下操作大大加速它，甚至可以在脑海中完成

(F(6) * (1 + 7)) / F(4)
 = 5 * 6 * 8
 = 240

基本上，我要生成这样的表达式，希望计算机聪明一些，不是通过乘以1来计算所有阶乘，也就是说，使用我的示例不实际进行计算。

(6*5*4*3*2 + 7*6*5*4*3*2) / 4*3*2

我实际上已经开始开发一个阶乘类，但我对Python和Numpy都很新，想知道这是否是已经解决的问题。

- Matt

---

我认为符号计算引擎应该具备这个功能，可以查看http://www.sympy.org/en/index.html。 - Oleg

Answer 1

正如@Oleg建议的那样，您可以使用sympy完成此操作：

import numpy as np
import sympy as sp

# preparation
n = sp.symbols("n")
F = sp.factorial

# create the equation
f = (F(n) + F(n + 1)) / F(n - 2)
print(f)               # => (factorial(n) + factorial(n + 1))/factorial(n - 2)

# reduce it
f = f.simplify()
print(f)               # => n*(n - 1)*(n + 2)

# evaluate it in SymPy
# Note: very slow!
print(f.subs(n, 6))    # => 240

# turn it into a numpy function
# Note: much faster!
f = sp.lambdify(n, f, "numpy")
a = np.arange(2, 10)
print(f(a))            # => [  8  30  72 140 240 378 560 792]

- Hugh Bothwell

Answer 2

也许你可以考虑使用表查找来提高效率，如果空间效率不是一个主要问题的话。这将大大减少重复计算的次数。以下示例并不特别高效，但它展示了基本思路。

cache = {1:1}
def cached_factorial(n):
    if (n in cache):
        return cache[n]
    else:
        result = n * cached_factorial(n-1)
        cache[n] = result
        return result

- Spencer Brett

---

我也在编写的自定义类中这样做 :-) - Matt