Python for Bioinformatics: Memoizing the factorial in Python

Thursday, February 10, 2011

Memoizing the factorial in Python

A Python class can be defined very simply:

>>> class A:  pass
... 
>>> a = A()
>>> print a
<__main__.A instance at 0x424670>

>>> def f():  return "I'm an A!"
... 
>>> a.__repr__ = f
>>> print a
I'm an A!
>>> a.x = 3
>>> print a.x
3
>>> print a.__dict__
{'x': 3, '__repr__': <function f at 0x1ee3b0>}

Of course it would be more typical to define some state for objects of the class, and perhaps also an inheritance hierarchy. Save this in script.py:

class A(object):
    def __init__(self,n):
        self.n = n
    def __repr__(self):
        return str(self.n)

a = A(3)
print a

Run it from the command line:

> python script.py 
3

Two other standard Python operators are the "getitem" operator [ ], and the "call" operator ( ). These can be implemented for any user-defined class:

class B(object):
    def __init__(self,n):
        self.n = n

    def __repr__(self):
        return 'rep:   ' + str(self.n)

    def __call__(self,arg):
        return 'call:  %d, %s' % (self.n, arg)

    def __getitem__(self,arg):
        return 'get:   %d, %s' % (self.n, arg)

b = B(3)
print b
print b('x')
print b['y']

Run it:

> python script.py 
rep:   3
call:  3, x
get:   3, y

I wrote a simple class to implement the factorial function that uses the call operator. This class keeps the values it currently knows in a list. (Apparently, this technique is called memoization). If we knew that we only wanted the last value, it would be better not to do this..

class factorial:
    def __init__(self):
        self.L = [1,1]
    def __call__(self,n):
        if type(n) != type(2) or n < 0:
            raise ValueError('invalid number')
        L = self.L
        i = len(L) - 1
        while i < n:
            i += 1
            L.append(L[-1]*i)
        return L[n]
        
f = factorial()
for i in range(10):
    print i, f(i)

> python factorial.py
0 1
1 1
2 2
3 6
4 24
5 120
6 720
7 5040
8 40320
9 362880

def test():
    for i in range(0,26000,5000):
        current = len(str(f(i)))
        print i, current

test()

> python factorial.py
5000 16326
10000 35660
15000 56130
20000 77338
25000 99094

25,000 factorial has nearly 100,000 digits!