[Tutor] Memoizing automatically?

[Gregor Lingl]

Hi all!

I've produced the code following below for two recursive functions,
which compute many values many times. And two
corresponding functions, which store values already computed
once in a dictionary. This results (of course) in an immense
improvement of runtime behaviour. (I give two examples to
stress the structural similarity)

My first question: Is this a reasonable approach or would you
recommend a better one, especially with respect to

my second question: how do I program some sort of factory-function
which produces automatically the memoizing version of  a
given recursive function with several recursive calls and a resulting
weird runtime-behaviour. Please do not discuss those many ways
to program a better fib, binom etc.

My interest lies in generating good programs from bad ones
automatically.

Thanks in advance
Gregor

Here follows the code:

class FIB:
    def fib(self,n):
        if n<3:
            return 1
        return self.fib(n-2) + self.fib(n-1)

class FIBM(FIB):
    memo = {}
    def fib(self,n):
        if n in self.memo:
            return self.memo[n]
        self.memo[n] = FIB.fib(self, n)
        return self.memo[n]


class BINOM:
    def binom(self,n,k):
        if n < 2 or k == 0 or k == n:
            return 1
        return self.binom(n-1,k-1) + self.binom(n-1,k)

class BINOMM(BINOM):
    memo = {}
    def binom(self,n,k):
        if (n,k) in self.memo:
            return self.memo[(n,k)]
        self.memo[(n,k)] = BINOM.binom(self, n, k)
        return self.memo[(n,k)]

### Example:

 >>> p = BINOM()
 >>> q = BINOMM()
 >>> if 1:
...     a=clock()
...     r1 = p.binom(22,8)
...     b=clock()
...     r2 = q.binom(22,8)
...     c=clock()
...     print b-a
...     print c-b
...
5.93672046679
0.00781942738013
 >>> q.memo
{(3, 3): 1, (3, 2): 3, (3, 1): 3, (3, 0): 1, (7, 7): 1, (7, 6): 7, (7, 
5): 21,
....
(15, 4): 1365, (15, 3): 455, (15, 2): 105, (15, 1): 15, (8, 8): 1, (15, 
8): 6435}
 >>> q.memo[(22,8)]
319770