CODEWITHSUNDEEP
c#python
Guy
Guy

Reputation: 67260

Understanding a factorial function in python

I'm trying to understand if the following Python function:

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]

would produce the same results as the equivalent in C#:

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

for a value of 12 or less.

I know nothing about Python but have just converted some Python code to C#. This was the only function that I didn't fully understand.

Upvotes: 3

Views: 662

Answers (6)

Krzysztof Bujniewicz
Krzysztof Bujniewicz

Reputation: 2417

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 &lt;= 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

To be honest, it is not the best algorithm, since it uses cache only partially.

The simple, user-friendly factorial function (no caching) would be:

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

Of for lazy python programmers, most similiar to that C# example:

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

Upvotes: 1

Daniel Br&#252;ckner
Daniel Br&#252;ckner

Reputation: 59645

It just attaches an attribute called lstFactorial to factorial. This attribute is a list of 1000 values used to cache the results of previous calls.

Upvotes: 1

Harper Shelby
Harper Shelby

Reputation: 16585

IANAPG (Python Guru), but it looks to me like the function is creating a static array of 1000 entries, then filling them on an as-needed basis to prevent recalculation. In C++, it'd be something like:

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
}

Upvotes: 2

Daniel Roseman
Daniel Roseman

Reputation: 599530

Even without knowing Python, it must be clear to you that the two functions are far from identical. The C# version is calculating the factorial via recursion, whereas the Python one is doing it via iteration (although in a slightly weird way, with some odd memoization/caching going on - I guess in case you want to calculate multiple factorials in the lifetime of a program).

Anyway, since calculating a factorial is a very simple algorithm, it works out the same in both cases.

Upvotes: 2

Thomas Levesque
Thomas Levesque

Reputation: 292405

it will return the same results, but the Python version will probably have better performance, because it memoizes the results

Upvotes: 1

Oduvan
Oduvan

Reputation: 2757

here is main algorithm

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

other code is for caching results.

Upvotes: 4

Related Questions