Doing some benchmarks of Python code reminded me of those
discussions. Included here is a function memoizer in Python.
It takes advantage of the fact that Python's dictionaries can
contain not only string indexes, but argument tuples.
The results of previous calls of the function are indexed by
their arguments.
- Steve Majewski (804-982-0831) <sdm7g@Virginia.EDU>
- UVA Department of Molecular Physiology and Biological Physics
----------------------------------------------------------------
Edited output of './memo.py 7'
----------------------------------------------------------------
fib( 7 ): <function fib at 2006a808>
fib( 7 )
fib( 6 )
fib( 5 )
fib( 4 )
fib( 3 )
fib( 2 )
fib( 1 )
fib( 0 )
fib( 1 )
[ lines and lines removed... ]
fib( 0 )
fib( 3 )
fib( 2 )
fib( 1 )
fib( 0 )
fib( 1 )
13
fib( 7 ): <method MemoizedFunc._funapply of MemoizedFunc instance at 200747e8>
fib( 7 )
fib( 6 )
fib( 5 )
fib( 4 )
fib( 3 )
fib( 2 )
fib( 1 )
fib( 0 )
13
fib( 8 ): <method MemoizedFunc._funapply of MemoizedFunc instance at 200747e8>
fib( 8 )
21
fib( 10 ): <method MemoizedFunc._funapply of MemoizedFunc instance at 200747e8>
fib( 10 )
fib( 9 )
55
----------------------------------------------------------------
#!/usr/local/bin/python
#
# <module 'memo'>
#
# function memoizer class and associated function.
# Usage: function = memo.memoize( function ); function( *args )
#
if __name__ == '__main__' : _modname = ''
else: _modname = __name__ + '.'
class MemoizedFunc:
def __init__( self, fun ):
self._hist = {}
self._fun = fun
def _funapply( self, *args ):
hist = self._hist
try:
return hist[args]
except KeyError:
result = apply( self._fun, args )
hist[args] = result
return result
def fun( self ):
return self._funapply
def memoize( func ):
# returns a "memo-ized" version of func.
# For a recursive function to work, you MUST assign the
# returned value to the function ITSELF.
# usage is: module.function = memoize( module.function )
return MemoizedFunc( func ).fun()
def fib( n ):
print 'fib(',n,')'
if n < 2 : return n
else: return fib( n - 1 ) + fib( n - 2 )
# Note that module(__name__).fib is not necessary here, since
# test, (original)fib and (memoized) fib are all in the same module
# That is not the case if the function to be memoized is defined elsewhere.
def test( n ):
global fib
if n < 20 : # DON'T even try, for large values of n
print 'fib(',n,'):',fib
fib( n )
fib = memoize( fib )
print 'fib(',n,'):', fib
fib( n )
print 'fib(', n+1, '):', fib
fib( n+1 )
print 'fib(',n+3,'):', fib
fib( n+3 )
if __name__ == '__main__' :
import sys
import string
if sys.argv[1:] and sys.argv[1] : n = string.atoi( sys.argv[1] )
else: n = 9
test( n )