flatten a level one list

Michael Spencer mahs at telcopartners.com
Thu Jan 12 19:00:20 CET 2006


Peter Otten wrote:

> I you require len(xdata) == len(ydata) there's an easy way to move the loop
> into C:
> 
> def flatten7():
>     n = len(xdata)
>     assert len(ydata) == n
>     result = [None] * (2*n)
>     result[::2] = xdata
>     result[1::2] = ydata
>     return result
> 
> $ python -m timeit 'from flatten import flatten6 as f' 'f()'
> 1000 loops, best of 3: 847 usec per loop
> $ python -m timeit 'from flatten import flatten7 as f' 'f()'
> 10000 loops, best of 3: 43.9 usec per loop
> 
> Peter
Very nice observation, Peter.  Easily the "winner".  It reminds me of 
str.translate beating python loops in filtering applications: 
http://groups.google.com/group/comp.lang.python/msg/e23cdc374144a4bd


What's more, you can generalize your approach to any number of sequences and 
un-equal lengths, with only modest loss of speed:

def interleave(*args, **kw):
     """Peter Otten flatten7 (generalized by Michael Spencer)
     Interleave any number of sequences, padding shorter sequences if kw pad
     is supplied"""
     dopad = "pad" in kw
     pad = dopad and kw["pad"]
     count = len(args)
     lengths = map(len, args)
     maxlen = max(lengths)
     result = maxlen*count*[None]
     for ix, input in enumerate(args):
         try:
             result[ix::count] = input
         except ValueError:
             if dopad:
                 result[ix::count] = input + [pad]*(maxlen-lengths[ix])
             else:
                 raise
     return result


def test_interleave():
     assert interleave([1,3,5], [2,4,6]) == [1,2,3,4,5,6]
     assert interleave([1,2,3]) == [1,2,3]
     assert interleave(*[[1,2,3]]*10) == [1]*10+[2]*10+[3]*10
     assert interleave(range(0,1000,2),range(1,1000,2)) == range(1000)
     def raises(func,*args, **kw):
         exc = kw.get("exc", Exception)
         try:
             func(*args)
         except exc:
             return True
     assert raises(interleave,[1,2],[3,4,5])
     assert interleave([1,3],[2,4,6], pad = None) == [1,2,3,4,None,6]


def timethem():
     for n in [1000, 10000, 100000, 1000000]:
         x = range(n); y = range(n)
         print "List length: ",n
         for func in [flatten7, interleave]:
             print shell.timefunc(func, x, y)

  >>> timethem()
  List length:  1000
  flatten7(...)  6442 iterations, 77.62usec per call
  interleave(...)  5475 iterations, 91.33usec per call
  List length:  10000
  flatten7(...)  318 iterations, 1.57msec per call
  interleave(...)  315 iterations, 1.59msec per call
  List length:  100000
  flatten7(...)  25 iterations, 20.61msec per call
  interleave(...)  24 iterations, 21.06msec per call
  List length:  1000000
  flatten7(...)  3 iterations, 198.51msec per call
  interleave(...)  3 iterations, 198.91msec per call
  >>>


Michael




More information about the Python-list mailing list