An idea for fast function composition

[castironpi at gmail.com]

On Feb 16, 5:57 pm, Boris Borcic <bbor... at gmail.com> wrote:
> castiro... at gmail.com wrote:
> > On Feb 16, 3:47 pm, Arnaud Delobelle <arno... at googlemail.com> 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, ..., 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').
>
> >> --
> >> 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.>