8 May 2006 - Memoize utility
Here is a small utility I use to memoize expensive function calls in python. This utility too (like compose seen some days ago) is a traslation from lisp to python of a utility found in the book On Lisp by Paul Graham:
def memoize(fun):
cache = {}
def inner(*args, **kwargs):
cached = cache.get((args, repr(kwargs)), None)
if cached is None:
val = fun(*args, **kwargs)
cache[(args, repr(kwargs))] = val
return val
return cached
return inner
The memoize function uses an internal dict (cache) to store the values already calculated and returns a function containing a binding to the cache, hence a closures.
The closure when called first tries to search in the cache for a previously stored value corresponding to the arguments passed. If found the cached value is returned, otherwise the value is calculated and stored in the cache using the arguments and the repr() of the keyword arguments as the cache key. The repr is used because a dictionary, in python, is not hashable and so it can't be used as a key.
To test the utility we define a function that calculates the fibonacci sequence:
def fib(n):
if n < 2:
return 1
return fib(n-1) + fib(n-2)
To use the memoize utility first we get the closure that memoizes the fib function:
import memoize
memo = memoize.memoize(fib)
Now we call the memo closure two times with the same argument and we time its execution:
def test_memoize_fib():
memo = memoize.memoize(fib)
start = time.time()
print memo(30)
end = time.time()
print "First call: %f" % (end - start)
start = time.time()
print memo(30)
end = time.time()
print "Second call: %f" % (end - start)
Calling the test function we get an output like this:
1346269
First call: 1.976743
1346269
Second call: 0.000072
Comments (0) -
Leave a Comment
1 May 2006 - Compose functions
Recently I'm reading the book "on Lisp" by Paul Garham. One the best books of programming I've ever read.
Here is an utility I translated from lisp to python to learn more on the use of closures. I wrote the function as part of a module functional (file
functional.py)
def compose(*fns):
if fns:
f1 = fns[-1]
fns = list(fns[:-1])
fns.reverse()
def inner(*args, **kwargs):
curr_arg = f1(*args, **kwargs)
for f in fns:
curr_arg = f(curr_arg)
return curr_arg
return inner
return None
The utility let you compose an arbitrary number of functions and apply each function to the result of the previous call. The first function can take any number of arguments or keyword arguments. All the others must take a single argument which is the result of the previous function call. Calling compose returns a closure that can be called with the number of arguments required by the first composed function:
>>> import functional
>>> import operator
>>> myop1 = functional.compose(operator.neg, operator.add)
>>> myop2 = functional.compose(operator.neg, operator.mul)
Now we can call the new operators like this:
>>> myop1(3, 2)
>>> myop1(3, 4)
>>> myop2(3, 2)
>>> myop2(3, 4)
and we get respectively:
-5, -7, -6 and -12
First operator.add (or operator.mul) is called with the two arguments passed. Then operator.neg is called with the result of the previous call as an argument.
Comments (0) -
Leave a Comment
21 February 2005 - Infix operators
Python has the wonderful "in" operator and it would be nice to have additional infix operator like this.
This recipe shows how (almost) arbitrary infix operators can be defined.
Comments (0) -
Leave a Comment
14 January 2005 - Cheetah Python Template
Cheetah is a flexible python Template system. It can be used to generate every kind of textual format (html, txt, sql, or even python code).
Read this article for an introduction.
Comments (0) -
Leave a Comment
