flatten a level one list

David Murmann david.murmann at rwth-aachen.de
Thu Jan 12 03:03:22 CET 2006


Robin Becker schrieb:
> Is there some smart/fast way to flatten a level one list using the 
> latest iterator/generator idioms.
> 
> The problem arises in coneverting lists of (x,y) coordinates into a 
> single list of coordinates eg
> 
> f([(x0,y0),(x1,y1),....]) --> [x0,y0,x1,y1,....] or
> 
> g([x0,x1,x2,......],[y0,y1,y2,....]) -->  [x0,y0,x1,y1,....]
> 
> clearly if f is doable then g can be done using zip. I suppose this is a 
> special case flatten, but can flatten be done fast? The python  recipes 
> seem rather slow compared to the builtin functions.

well then:

first of all, i need to say, if speed really matters, do it in C.
that being said, python can be fast, too. for this task psyco is your
friend. i got this output from the script given below:

without psyco:

flatten1: 2.78046748059
flatten2: 2.90226239686
flatten3: 4.91070862996
goopy_flatten1: 8.22951110963
goopy_flatten2: 8.56373180172

with psyco:

flatten1: 1.17390339924
flatten2: 1.7209583052
flatten3: 1.18490295558
goopy_flatten1: 1.34892236194
goopy_flatten2: 1.68568386584

the goopy function is taken from the google-functional package (but is
treated a bit unfair, i must admit, being wrapped in a lambda)

so, what does that show us? izip seems a bit faster than zip with these
input data. you want to do your own timings with more realistic data. 
and all these functions are what just came to my mind, i'm sure they
can be improved.

hope this helps,

--
David.

used script:
----------------------------------------------------------------

from itertools import izip

xdata = range(1000)
ydata = range(1000)[::-1]

def flatten1():
    return [x for pair in izip(xdata, ydata) for x in pair]

def flatten2():
    return [x for pair in zip(xdata, ydata) for x in pair]

def flatten3():
    res = []
    for pair in izip(xdata, ydata):
        for x in pair:
            res.append(x)
    return res

def goopy_flatten(seq):
  lst = []
  for x in seq:
    if type(x) is list or type(x) is tuple:
      for val in x:
        lst.append(val)
    else:
      lst.append(x)
  return lst

goopy_flatten1 = lambda: goopy_flatten(izip(xdata, ydata))
goopy_flatten2 = lambda: goopy_flatten(zip(xdata, ydata))

if __name__=='__main__':
    from timeit import Timer
    
    functions = ['flatten1', 'flatten2', 'flatten3', 'goopy_flatten1', 'goopy_flatten2']

    print 'without psyco:'
    print

    for fn in functions:
        t = Timer(fn+'()', 'from __main__ import '+fn)
        print fn+':', t.timeit(5000)
    
    try: import psyco; psyco.full()
    except ImportError: pass
    
    print
    print 'with psyco:'
    print

    for fn in functions:
        t = Timer(fn+'()', 'from __main__ import '+fn)
        print fn+':', t.timeit(5000)



More information about the Python-list mailing list