Понимание факториальной функции в 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 #. Это была единственная функция, которую я не до конца понимал.

Answer 1

вот основной алгоритм

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

другой код предназначен для кэширования результатов.

Answer 2

IANAPG (Python Guru), но мне кажется, что функция создает статический массив из 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
}

Answer 3

Даже не зная Python, вам должно быть ясно, что эти две функции далеко не идентичны. Версия C # вычисляет факториал с помощью рекурсии, тогда как версия Python делает это с помощью итерации (хотя и немного странным образом, с некоторым странным запоминанием / кэшированием - думаю, если вы захотите вычислить несколько факториалов за время существования программа).

В любом случае, поскольку вычисление факториала является очень простым алгоритмом, он работает одинаково в обоих случаях.

Answer 4

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

Answer 5

Он просто присоединяет атрибут с именем lstFactorial к factorial. Этот атрибут представляет собой список из 1000 значений, используемых для кэширования результатов предыдущих вызовов.

Answer 6

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