Is there a Python module that already does this?

[David Eppstein]

In article <a3sq4m$1an2ll$1 at ID-11957.news.dfncis.de>,
 "Emile van Sebille" <emile at fenx.com> wrote:

> You can squeeze out another (ugly) 15-20% performance gain
> by making almost everything local and taking out the len check:
> 
> def flatten(x, isseq=operator.isSequenceType,
>     concat=operator.concat, reduce=reduce, map=map):
>     if isseq(x) and x[0] != x:
>         return reduce(concat, map(flatten, x), [])
>     else:
>         return [x]
> 

No, the len check is important, otherwise you get a crash when the input 
contains [] (that's also why I included the third arg to reduce).

Anyway, the reason I said that this is inefficient is that there are ways 
of making flatten take time linear in the length of the input, while the 
code I wrote is quadratic in the worst case, and its worst case (an 
already flattened list) is not especially unlikely. Using an algorithm 
with better asymptotic efficiency can make an improvement of much more 
than a few percent, for large inputs. For instance, when I test the code 
below, for n=10^5, my functional flatten takes 425 seconds while the mixed 
functional-imperative flat2 takes only 1:

def flatten(x):
        if operator.isSequenceType(x) and (len(x) != 1 or x[0] != x):
                return reduce(operator.concat, map(flatten, x), [])
        else:
                return [x]

def flat2(x):
        L = []
        def recurse(x):
                if operator.isSequenceType(x) and (len(x)!=1 or x[0]!=x):
                        map(recurse, x)
                else:
                        L.append(x)
        recurse(x)
        return L

def testflat(n):
        L = [0]*n

        start = time.clock()
        F = flatten(L)
        print "flatten time for", len(F), "items:", time.clock() - start
        
        start = time.clock()
        F = flat2(L)
        print "flat2 time for", len(F), "items:", time.clock() - start
-- 
David Eppstein       UC Irvine Dept. of Information & Computer Science
eppstein at ics.uci.edu http://www.ics.uci.edu/~eppstein/