理解Python中的阶乘函数

Question

我将尝试理解下面这个Python函数：

def factorial(i):
    if not hasattr(factorial, 'lstFactorial'):
        factorial.lstFactorial = [None] * 1000
    if factorial.lstFactorial[i] is None:
        iProduct = 1
        for iFactor in xrange(1, i+1):
            iProduct *= iFactor
        factorial.lstFactorial[i] = iProduct
    return factorial.lstFactorial[i]

将会产生与C#中等效的结果：

long factorial(long n) 
{ 
   return n <= 1 ? 1 : n * factorial(n-1);
}

当值小于或等于12时。

我对Python一无所知，但刚刚将一些Python代码转换为C#。这是唯一一个我没有完全理解的函数。

- Guy

---

为什么不尝试一下并检查呢？ - Thomas Levesque

为什么不安装Python呢？它只是一个小型的MSI，不到5分钟就能完成。有什么阻碍吗？ - S.Lott

我能理解你为什么感到困惑。这是一段相当糟糕的 Python 代码。它的设计真的很糟糕。 - S.Lott

Answer 1

这是主要算法

iProduct = 1
for iFactor in xrange(1, i+1):
    iProduct *= iFactor

其他代码用于缓存结果。

- Oduvan

Answer 2

虽然我不是Python大师（IANAPG），但在我看来，这个函数似乎创建了一个静态数组，该数组有1000个条目，并在需要时填充它们以防止重新计算。在C++中，它可能是这样的：

long factorial(int i){
    //Cache array
    static long factorials[1000];
    if (!factorials[i]){ //If not cached, calculate & store
        int product = 1;
        for (int idx = 1; idx <= i + 1; ++idx){
            product *= idx;
        }
        factorials[i] = product;
    }
    return factorials[i]; //Return cached value
}

- Harper Shelby

---

注意+1的问题。Python中的xrange(a,b)会创建从a到b-1的所有值。这个想法是xrange返回b-a个不同的值。xrange(1,5)返回4个值：1、2、3、4。 - S.Lott

好的，我之前就已经放了免责声明，所以没关系。我会一些 Python 编程技巧，但并不是很熟练。 - Harper Shelby

此外，long 无法容纳高达阶乘（999）的值。已经计算阶乘（13）将会导致有符号32位整数溢出。 - Jukka Matilainen

你，你指望我全部都免费提供吗？:-) - Harper Shelby

Answer 3

即使您不了解Python，也应该清楚这两个函数远非相同。C#版本通过递归计算阶乘，而Python版本则通过迭代进行计算（尽管以稍微奇怪的方式进行一些备忘录/缓存 - 我猜如果您想在程序生命周期内计算多个阶乘，那么这种方式可能有用）。无论如何，由于计算阶乘是一个非常简单的算法，因此在两种情况下都能得到相同的结果。

- Daniel Roseman

---

+1 是对使用记忆化的解释（这是正确的）的肯定，这是加速计算的解决方案之一，如果过去已经计算出结果。 - Tadeck

Answer 4

它将返回相同的结果，但Python版本可能具有更好的性能，因为它会记忆结果

- Thomas Levesque

---

+1 说明它使用记忆化。然而这两种解决方案不同 - C#的解决方案使用递归，而Python的解决方案则不使用。 - Tadeck

Answer 5

它只是将一个名为lstFactorial的属性附加到factorial。该属性是一个包含1000个值的列表，用于缓存先前调用的结果。

- Daniel Brückner

Answer 6

def factorial(i):
    if not hasattr(factorial, 'lstFactorial'): #program checks whether caching list exists
        factorial.lstFactorial = [None] * 1000 #if so, it creates a list of thousand None elements (it is more or less equivalent to C/C++'s NULL
    if factorial.lstFactorial[i] is None: #prog checks if that factorial has been already calculated
        iProduct = 1 #set result to 1
        for iFactor in xrange(1, i+1): # C's for(iFactor = 1; iFactor <= i+1; iFactor++)
            iProduct *= iFactor #we multiply result times current loop counter
        factorial.lstFactorial[i] = iProduct #and put result in caching list
    return factorial.lstFactorial[i] #after all, we return the result, calculated jest now or obtained from cache

说实话，这不是最好的算法，因为它只部分使用缓存。

简单易用的阶乘函数（无缓存）如下：

def factorial(i):
    if i == 0 or i == 1:
        return 1
    return i*factorial(i-1)

对于懒惰的Python程序员来说，最类似于C#示例的是：

f = lambda i: i and i*f(i-1) or 1

- Krzysztof Bujniewicz

---

递归方法的问题（您可能已经知道，但为了OP的利益而提及），是当数字足够大时，您将超过最大递归深度。 （在Python中默认为1000。）即使您使用传递累加器并执行尾调用的版本，由于Python没有尾调用优化，您仍会达到该限制。 - Anon

是的，我知道。我应该在答案中写下它，只是忘了。抱歉，并感谢您的提醒。 :) - Krzysztof Bujniewicz