An idea for fast function composition

A

Arnaud Delobelle

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, ..., fn:(lambda 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 %s:(lambda 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)
----------------------------------

marigold:python arno$ python -i simple_compose.py
compose 1.84630298615
lambda 1.86365509033 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 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').
 
C

castironpi

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, ..., fn:(lambda 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 %s:(lambda 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)
----------------------------------

marigold:python 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').

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

Boris Borcic

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, ..., fn:(lambda 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 %s:(lambda 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)
----------------------------------

marigold:python 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').

def compose( funcs ):
def reccompose( *args ):
return compose( funcs[:-1] )( funcs[-1]( *args ) ) if funcs else
funcs[0]( *args )
return reccompose
def reccompose( *args ):
return compose( funcs[:-1] )( funcs[-1]( *args ) ) if funcs else funcs[0]( *args )
return reccompose
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) 40 LOAD_DEREF 0 (funcs)
43 LOAD_CONST 2 (0)
46 BINARY_SUBSCR
47 LOAD_FAST 0 (args)
50 CALL_FUNCTION_VAR 0

Mmmhhh...
 
C

castironpi

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, ..., fn:(lambda 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 %s:(lambda 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)
----------------------------------
marigold:python 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').
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.>
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

Forum statistics

Threads
473,744
Messages
2,569,482
Members
44,901
Latest member
Noble71S45

Latest Threads

Top