Velocity Reviews > An idea for fast function composition

# An idea for fast function composition

Arnaud Delobelle
Guest
Posts: n/a

 02-16-2008
Hi all,

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. Below I define a 'compose' function such that the above can
be written

compose(f1, f2, ...., fn),

the resulting function being as fast as the lambda version (or maybe
faster?). 'getcomposer' is a helper function (which in most cases
will amount to a dictionary lookup).

----------------------------------
def getcomposer(nfunc, _cache={}):
"getcomposer(n) -> lambda f1, ..., fnlambda x: f1(...fn(x)...))"
try:
return _cache[nfunc]
except KeyError:
fnames = ['f%s' % i for i in range(nfunc)]
call = ''.join('%s(' % f for f in fnames)
args = ','.join(fnames)
cstr = 'lambda %slambda x:%sx%s)' % (args, call, ')'*nfunc)
composer = _cache[nfunc] = eval(cstr)
return composer

def compose(*functions):
"compose(f1, ..., fn) -> lambda x: f1(f2(...fn(x)...))"
return getcomposer(len(functions))(*functions)

# Test

def double(x): return 2*x
def square(x): return x**2
def succ(x): return x+1

f1 = compose(double, square, succ, float)
f2 = lambda x: double(square(succ(float(x))))

def benchmark(f, n=1000000):
from time import time
from itertools import imap
t0 = time()
for _ in imap(f1, xrange(n)): pass
t1 = time()
return t1-t0

print 'compose', benchmark(f1)
print 'lambda ', benchmark(f2)
----------------------------------

marigoldython arno\$ python -i simple_compose.py
compose 1.84630298615
lambda 1.86365509033
>>> import dis
>>> dis.dis(f1)

15 CALL_FUNCTION 1
18 CALL_FUNCTION 1
21 CALL_FUNCTION 1
24 CALL_FUNCTION 1
27 RETURN_VALUE
>>> dis.dis(f2)

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 require the use of a
python lambda-function (as created by 'getcomposer').

--
Arnaud

castironpi@gmail.com
Guest
Posts: n/a

 02-16-2008
On Feb 16, 3:47*pm, Arnaud Delobelle <(E-Mail Removed)> wrote:
> Hi all,
>
> 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. *Below I define a 'compose' function such that the above can
> be written
>
> * * *compose(f1, f2, ...., fn),
>
> the resulting function being as fast as the lambda version (or maybe
> faster?). *'getcomposer' is a helper function (which in most cases
> will amount to a dictionary lookup).
>
> ----------------------------------
> def getcomposer(nfunc, _cache={}):
> * * *"getcomposer(n) -> lambda f1, ..., fnlambda x: f1(...fn(x)...))"
> * * *try:
> * * * * *return _cache[nfunc]
> * * *except KeyError:
> * * * * *fnames = ['f%s' % i for i in range(nfunc)]
> * * * * *call = ''.join('%s(' % f for f in fnames)
> * * * * *args = ','.join(fnames)
> * * * * *cstr = 'lambda %slambda x:%sx%s)' % (args, call, ')'*nfunc)
> * * * * *composer = _cache[nfunc] = eval(cstr)
> * * * * *return composer
>
> def compose(*functions):
> * * *"compose(f1, ..., fn) -> lambda x: f1(f2(...fn(x)...))"
> * * *return getcomposer(len(functions))(*functions)
>
> # Test
>
> def double(x): return 2*x
> def square(x): return x**2
> def succ(x): return x+1
>
> f1 = compose(double, square, succ, float)
> f2 = lambda x: double(square(succ(float(x))))
>
> def benchmark(f, n=1000000):
> * * *from time import time
> * * *from itertools import imap
> * * *t0 = time()
> * * *for _ in imap(f1, xrange(n)): pass
> * * *t1 = time()
> * * *return t1-t0
>
> print 'compose', benchmark(f1)
> print 'lambda ', benchmark(f2)
> ----------------------------------
>
> marigoldython arno\$ python -i simple_compose.py
> compose 1.84630298615
> lambda *1.86365509033
> *>>> 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 require the use of a
> python lambda-function (as created by 'getcomposer').
>
> --
> Arnaud

def compose( funcs ):
def reccompose( *args ):
return compose( funcs[:-1] )( funcs[-1]( *args ) ) if funcs else
funcs[0]( *args )
return reccompose

castironpi@gmail.com
Guest
Posts: n/a

 02-16-2008
> def compose( funcs ):
> * *def reccompose( *args ):
> * * * return compose( funcs[:-1] )( funcs[-1]( *args ) ) if funcs else
> funcs[0]( *args )
> * *return reccompose- Hide quoted text -

Which was, if funcs> 1, which is len( funcs )> 1.
>>> [1]>0

Traceback (most recent call last):
File "<stdin>", line 1, in <module>
TypeError: unorderable types: list() > int()

Boris Borcic
Guest
Posts: n/a

 02-16-2008
http://www.velocityreviews.com/forums/(E-Mail Removed) wrote:
> On Feb 16, 3:47 pm, Arnaud Delobelle <(E-Mail Removed)> wrote:
>> Hi all,
>>
>> 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. Below I define a 'compose' function such that the above can
>> be written
>>
>> compose(f1, f2, ...., fn),
>>
>> the resulting function being as fast as the lambda version (or maybe
>> faster?). 'getcomposer' is a helper function (which in most cases
>> will amount to a dictionary lookup).
>>
>> ----------------------------------
>> def getcomposer(nfunc, _cache={}):
>> "getcomposer(n) -> lambda f1, ..., fnlambda x: f1(...fn(x)...))"
>> try:
>> return _cache[nfunc]
>> except KeyError:
>> fnames = ['f%s' % i for i in range(nfunc)]
>> call = ''.join('%s(' % f for f in fnames)
>> args = ','.join(fnames)
>> cstr = 'lambda %slambda x:%sx%s)' % (args, call, ')'*nfunc)
>> composer = _cache[nfunc] = eval(cstr)
>> return composer
>>
>> def compose(*functions):
>> "compose(f1, ..., fn) -> lambda x: f1(f2(...fn(x)...))"
>> return getcomposer(len(functions))(*functions)
>>
>> # Test
>>
>> def double(x): return 2*x
>> def square(x): return x**2
>> def succ(x): return x+1
>>
>> f1 = compose(double, square, succ, float)
>> f2 = lambda x: double(square(succ(float(x))))
>>
>> def benchmark(f, n=1000000):
>> from time import time
>> from itertools import imap
>> t0 = time()
>> for _ in imap(f1, xrange(n)): pass
>> t1 = time()
>> return t1-t0
>>
>> print 'compose', benchmark(f1)
>> print 'lambda ', benchmark(f2)
>> ----------------------------------
>>
>> marigoldython arno\$ python -i simple_compose.py
>> compose 1.84630298615
>> lambda 1.86365509033
>> >>> import dis
>> >>> dis.dis(f1)

>> 1 0 LOAD_DEREF 0 (f0)
>> 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)
>> 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 require the use of a
>> python lambda-function (as created by 'getcomposer').
>>
>> --
>> Arnaud

>
> def compose( funcs ):
> def reccompose( *args ):
> return compose( funcs[:-1] )( funcs[-1]( *args ) ) if funcs else
> funcs[0]( *args )
> return reccompose

>>> def compose( *funcs ):

def reccompose( *args ):
return compose( funcs[:-1] )( funcs[-1]( *args ) ) if funcs else funcs[0]( *args )
return reccompose

>>> f3 = compose(double, square, succ, float)
>>> import dis
>>> dis.dis(f3)

3 JUMP_IF_FALSE 33 (to 39)
6 POP_TOP
16 SLICE+2
17 CALL_FUNCTION 1
26 BINARY_SUBSCR
30 CALL_FUNCTION_VAR 0
33 CALL_FUNCTION 1
36 JUMP_FORWARD 14 (to 53)
>> 39 POP_TOP

46 BINARY_SUBSCR
50 CALL_FUNCTION_VAR 0
>> 53 RETURN_VALUE

Mmmhhh...

castironpi@gmail.com
Guest
Posts: n/a

 02-17-2008
On Feb 16, 5:57*pm, Boris Borcic <(E-Mail Removed)> wrote:
> (E-Mail Removed) wrote:
> > On Feb 16, 3:47 pm, Arnaud Delobelle <(E-Mail Removed)> wrote:
> >> Hi all,

>
> >> 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. *Below I define a 'compose' function such that the above can
> >> be written

>
> >> * * *compose(f1, f2, ...., fn),

>
> >> the resulting function being as fast as the lambda version (or maybe
> >> faster?). *'getcomposer' is a helper function (which in most cases
> >> will amount to a dictionary lookup).

>
> >> ----------------------------------
> >> def getcomposer(nfunc, _cache={}):
> >> * * *"getcomposer(n) -> lambda f1, ..., fnlambda x: f1(...fn(x)....))"
> >> * * *try:
> >> * * * * *return _cache[nfunc]
> >> * * *except KeyError:
> >> * * * * *fnames = ['f%s' % i for i in range(nfunc)]
> >> * * * * *call = ''.join('%s(' % f for f in fnames)
> >> * * * * *args = ','.join(fnames)
> >> * * * * *cstr = 'lambda %slambda x:%sx%s)' % (args, call, ')'*nfunc)
> >> * * * * *composer = _cache[nfunc] = eval(cstr)
> >> * * * * *return composer

>
> >> def compose(*functions):
> >> * * *"compose(f1, ..., fn) -> lambda x: f1(f2(...fn(x)...))"
> >> * * *return getcomposer(len(functions))(*functions)

>
> >> # Test

>
> >> def double(x): return 2*x
> >> def square(x): return x**2
> >> def succ(x): return x+1

>
> >> f1 = compose(double, square, succ, float)
> >> f2 = lambda x: double(square(succ(float(x))))

>
> >> def benchmark(f, n=1000000):
> >> * * *from time import time
> >> * * *from itertools import imap
> >> * * *t0 = time()
> >> * * *for _ in imap(f1, xrange(n)): pass
> >> * * *t1 = time()
> >> * * *return t1-t0

>
> >> print 'compose', benchmark(f1)
> >> print 'lambda ', benchmark(f2)
> >> ----------------------------------

>
> >> marigoldython arno\$ python -i simple_compose.py
> >> compose 1.84630298615
> >> lambda *1.86365509033
> >> *>>> 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 require the use of a
> >> python lambda-function (as created by 'getcomposer').

>
> >> --
> >> Arnaud

>
> > def compose( funcs ):
> > * *def reccompose( *args ):
> > * * * return compose( funcs[:-1] )( funcs[-1]( *args ) ) if funcs else
> > funcs[0]( *args )
> > * *return reccompose

>
> *>>> def compose( *funcs ):
> * * * * def reccompose( *args ):
> * * * * * * * * return compose( funcs[:-1] )( funcs[-1]( *args ) ) if funcs else funcs[0]( *args )
> * * * * return reccompose
>
> *>>> f3 = compose(double, square, succ, float)
> *>>> import dis
> *>>> dis.dis(f3)
> * *3 * * * * * 0 LOAD_DEREF * * * * * * * 0 (funcs)
> * * * * * * * *3 JUMP_IF_FALSE * * * * * 33 (to 39)
> * * * * * * * *6 POP_TOP
> * * * * * * * *7 LOAD_GLOBAL * * * * * * *0 (compose)
> * * * * * * * 10 LOAD_DEREF * * * * * * * 0 (funcs)
> * * * * * * * 13 LOAD_CONST * * * * * * * 1 (-1)
> * * * * * * * 16 SLICE+2
> * * * * * * * 17 CALL_FUNCTION * * * * * *1
> * * * * * * * 20 LOAD_DEREF * * * * * * * 0 (funcs)
> * * * * * * * 23 LOAD_CONST * * * * * * * 1 (-1)
> * * * * * * * 26 BINARY_SUBSCR
> * * * * * * * 27 LOAD_FAST * * * * * * * *0 (args)
> * * * * * * * 30 CALL_FUNCTION_VAR * * * *0
> * * * * * * * 33 CALL_FUNCTION * * * * * *1
> * * * * * * * 36 JUMP_FORWARD * * * * * *14 (to 53)
> * * * * *>> * 39 POP_TOP
> * * * * * * * 40 LOAD_DEREF * * * * * * * 0 (funcs)
> * * * * * * * 43 LOAD_CONST * * * * * * * 2 (0)
> * * * * * * * 46 BINARY_SUBSCR
> * * * * * * * 47 LOAD_FAST * * * * * * * *0 (args)
> * * * * * * * 50 CALL_FUNCTION_VAR * * * *0
> * * * * *>> * 53 RETURN_VALUE
>
> Mmmhhh...- Hide quoted text -
>
> - Show quoted text -

OOOOOOwwwwwwww! <Sulks off to lick wounds.>