Fast function composer

Recently there was a thread about function composition in Python (and this was probably not the first). The fast way to create a (anonymous) composite function

f1 o f2 o ... o fn
in Python is via
lambda x: f1(f2(...fn(x)...)),
but according to some this is neither the most compact nor the most readable. I define a compose function such that the above can be written
compose(f1, f2, ...., fn),
the resulting funtion being as fast as the lambda version (or maybe faster?). The file compose.py contains the function definition (download here). The function getcomposer is a helper function (which in most cases will amount to a dictionary lookup).

This is how it works 

>>> def succ(x): return x+1
... 
>>> def double(x): return 2*x
... 
>>> def square(x): return x**2
... 
>>> def succ(x): return x+1
... 
>>> f1 = compose(double, square, succ, float)
>>> f1(8)

162.0

>>>

Here is a benchmark for speed against the traditional lambda method for composing functions. It shows that using compose incurs no speed penalty.

>>> f2 = lambda x: double(square(succ(float(x))))
>>> 
>>> def benchmark(f, n=1000000):
...     from time import time
...     t0 = time()
...     for x in xrange(n): f(x)
...     t1 = time()
...     return t1-t0
... 
>>> print 'compose', benchmark(f1)

compose 1.83817005157

>>> print 'lambda ', benchmark(f2)

lambda 1.99733304977

>>>

Looking at the bytecode for f1 and f2:

>>> import dis
>>> dis.dis(f1)

  1           0 LOAD_DEREF               0 (f0)
              3 LOAD_DEREF               3 (f1)
              6 LOAD_DEREF               1 (f2)
              9 LOAD_DEREF               2 (f3)
             12 LOAD_FAST                0 (x)
             15 CALL_FUNCTION            1
             18 CALL_FUNCTION            1
             21 CALL_FUNCTION            1
             24 CALL_FUNCTION            1
             27 RETURN_VALUE        

>>> dis.dis(f2)

 23           0 LOAD_GLOBAL              0 (double)
              3 LOAD_GLOBAL              1 (square)
              6 LOAD_GLOBAL              2 (succ)
              9 LOAD_GLOBAL              3 (float)
             12 LOAD_FAST                0 (x)
             15 CALL_FUNCTION            1
             18 CALL_FUNCTION            1
             21 CALL_FUNCTION            1
             24 CALL_FUNCTION            1
             27 RETURN_VALUE        

>>>

f1 and f2 are almost exaclty the same but array lookups (LOAD_DEREFs) in f1 replace dictionary lookups (LOAD_GLOBALs) in f2. A C version of compose could easily be written that doesn't the use of a python lambda-function (as created by getcomposer).

Last updated on Tue Oct 28 16:16:12 2008
arno AT marooned.org.uk