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,

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

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)
>> 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...

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.>

 Thread Tools

 Posting Rules You may not post new threads You may not post replies You may not post attachments You may not edit your posts BB code is On Smilies are On [IMG] code is On HTML code is OffTrackbacks are On Pingbacks are On Refbacks are Off Forum Rules

 Similar Threads Thread Thread Starter Forum Replies Last Post Kay Schluehr Python 10 02-04-2008 05:08 PM Tom Moertel Ruby 2 04-07-2006 07:10 PM nimmi_srivastav@yahoo.com C Programming 10 02-02-2005 10:51 PM Alan G Isaac Python 6 10-25-2004 08:13 PM Edgardo Hames Ruby 7 08-07-2004 09:31 AM

Advertisments