# Is there a Python module that already does this?

David Eppstein eppstein at ics.uci.edu
Wed Feb 6 22:39:20 EST 2002

```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/

```

More information about the Python-list mailing list