Flattening lists

[rdmurray at bitdance.com]

Quoth J Kenneth King <james at agentultra.com>:
> mk <mrkafk at gmail.com> writes:
> 
> > Hello everybody,
> >
> > Any better solution than this?
> >
> > def flatten(x):
> >     res = []
> >     for el in x:
> >         if isinstance(el,list):
> >             res.extend(flatten(el))
> >         else:
> >             res.append(el)
> >     return res
> >
> > a = [1, 2, 3, [4, 5, 6], [[7, 8], [9, 10]]]
> > print flatten(a)
> >
> >
> > [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
> >
> > Regards,
> > mk
> 
> http://mail.python.org/pipermail/python-list/2005-July/330367.html

That's worth reading.  I'm not sure why I'm finding this fun, but who
cares.  I tried a couple of other functions after reading that article,
and it looks like a generator that scans the nested lists is actually
the winner, and also is in many ways the most elegant implementation.
Of course, as noted in the emails following above article, the test data
is really inadequate for proper optimization testing ;)

-----------------------------------------------------------------
from __future__ import print_function
from timeit import Timer
from itertools import chain

# This is the one from the article quoted above.
def flatten6(seq):
    i = 0
    while (i != len(seq)):
        while hasattr(seq[i], '__iter__'):
            seq[i:i+1] = seq[i]
        i = i + 1
    return seq


#This is my favorite from a readability standpoint out of
#all the things I tried.  It also performs the best.
def flatten8(seq):
    for x in seq:
        if not hasattr(x, '__iter__'): yield x
        else:
            for y in flatten8(x):
                yield y



l = [[1, 2, 3], 5, [7, 8], 3, [9, [10, 11, 12], 4, [9, [10, 5, 7]], 1, [[[[[5, 4], 3], 4, 3], 3, 1, 45], 9], 10]]



if __name__=="__main__":
    print(l)
    print('flatten6', flatten6(l))
    print('flatten8', list(flatten8(l)))
    print('flatten6', Timer("flatten6(l)", "from temp3 import flatten6, l").timeit())
    print('flatten8', Timer("list(flatten8(l))", "from temp3 import flatten8, l").timeit())


-----------------------------------------------------------------

>src/python/Python-3.0/python temp3.py
[[1, 2, 3], 5, [7, 8], 3, [9, [10, 11, 12], 4, [9, [10, 5, 7]], 1, [[[[[5, 4], 3], 4, 3], 3, 1, 45], 9], 10]]
flatten6 [1, 2, 3, 5, 7, 8, 3, 9, 10, 11, 12, 4, 9, 10, 5, 7, 1, 5, 4, 3, 4, 3, 3, 1, 45, 9, 10]
flatten8 [1, 2, 3, 5, 7, 8, 3, 9, 10, 11, 12, 4, 9, 10, 5, 7, 1, 5, 4, 3, 4, 3, 3, 1, 45, 9, 10]
flatten6 32.8386368752
flatten8 30.7509689331

>python temp3.py 
[[1, 2, 3], 5, [7, 8], 3, [9, [10, 11, 12], 4, [9, [10, 5, 7]], 1, [[[[[5, 4], 3], 4, 3], 3, 1, 45], 9], 10]]
flatten6 [1, 2, 3, 5, 7, 8, 3, 9, 10, 11, 12, 4, 9, 10, 5, 7, 1, 5, 4, 3, 4, 3, 3, 1, 45, 9, 10]
flatten8 [1, 2, 3, 5, 7, 8, 3, 9, 10, 11, 12, 4, 9, 10, 5, 7, 1, 5, 4, 3, 4, 3, 3, 1, 45, 9, 10]
flatten6 34.730714798
flatten8 32.3252940178

--RDM