If the profiling shows that you call some function a lot of times for the same arguments, then memoise it. The canonical example is memoising the intermediate results of the Fibonacci recursive calculator, presented below. But beware: if you do memoise, better make sure that you don't eat up the full memory! Memoising is a classic speed versus memory dilemma.
Here is example code, showing how memoisation speeded up Fibonacci calculator from 1.64 to 0.01 seconds:
#!/usr/bin/python
"""
Demonstrate the memoization technique for the Fibonacci calculator.
Results run on PCDH23 on 2004-12-06 are:
$ python memoize-demo.py
testing memoization for fib(20)...
fib took 1.640 sec
fib_memoized took 0.010 sec
fib_memoized stats: calls in cache: 117 out of 138 (84.8%)
"""
class Memoize:
"""Memoizator. Based on <http://www.norvig.com/python-iaq.html>."""
def __init__(self, function):
self.memo = {}
self.function = function
self.count_calls_total = 0
self.count_calls_in_cache = 0
def __call__(self, *args):
self.count_calls_total += 1
if self.memo.has_key(args):
self.count_calls_in_cache += 1
return self.memo[args]
else:
object = self.memo[args] = self.function(*args)
return object
def get_stats(self):
return "calls in cache: %d out of %d (%.1f%%)" % \
(self.count_calls_in_cache,
self.count_calls_total,
self.count_calls_in_cache*100.0/self.count_calls_total)
def fib(n):
"""Calculate Fibonacci number for N recursively."""
if n < 2:
return 1
else:
return fib(n-1) + fib(n-2)
def fib_memoized(n):
"""Calculate Fibonacci number for N recursively.
Identical to fib() defined above. This one will be memoized later.
"""
if n < 2:
return 1
else:
return fib_memoized(n-1) + fib_memoized(n-2)
# memoize one of the two identical fib() functions
fib_memoized = Memoize(fib_memoized)
import time
def timing(f, a, n=10):
"""Return timing of function F on argument A run N times.
Taken from <http://www.python.org/doc/essays/list2str.html>.
"""
r = range(n)
t1 = time.clock()
for i in r:
f(a); f(a); f(a); f(a); f(a); f(a); f(a); f(a); f(a); f(a)
t2 = time.clock()
return round(t2-t1, 3)
def main():
"""Demonstrate the memoization technique for the Fibonacci calculator."""
n = 20
print "testing memoization for fib(%d)..." % n
fib_time = timing(fib, n)
fib_memoized_time = timing(fib_memoized, n)
print "fib took %.3f sec" % fib_time
print "fib_memoized took %.3f sec" % fib_memoized_time
print "fib_memoized stats: %s" % fib_memoized.get_stats()
return
if __name__ == '__main__':
main()