What is the fastest way to flatten arbitrarily nested lists in Python?


Question

Possible Duplicate:
Flattening a shallow list in Python
Flatten (an irregular) list of lists in Python

EDIT: The question is not how to do it - this has been discussed in other questions - the question is, which is the fastest method?

I've found solutions before, but I'm wondering what the fastest solution is to flatten lists which contain other lists of arbitrary length.

For example:

[1, 2, [3, 4, [5],[]], [6]]

Would become:

[1,2,3,4,5,6]

There can be infinitely many levels. Some of the list objects can be strings, which mustn't be flattened into their sequential characters in the output list.

1
45
7/13/2018 4:23:46 PM

Accepted Answer

Here's a recursive approach that is string friendly:

nests = [1, 2, [3, 4, [5],['hi']], [6, [[[7, 'hello']]]]]

def flatten(container):
    for i in container:
        if isinstance(i, (list,tuple)):
            for j in flatten(i):
                yield j
        else:
            yield i

print list(flatten(nests))

returns:

[1, 2, 3, 4, 5, 'hi', 6, 7, 'hello']

Note, this doesn't make any guarantees for speed or overhead use, but illustrates a recursive solution that hopefully will be helpful.

55
3/31/2016 6:41:32 PM

It doesn't have to be recursive. In fact, an iterative solution is often faster because of the overhead involved in function calls. Here's an iterative version I wrote a while back:

def flatten(items, seqtypes=(list, tuple)):
    for i, x in enumerate(items):
        while i < len(items) and isinstance(items[i], seqtypes):
            items[i:i+1] = items[i]
    return items

Haven't tested the performance of this specific implementation, but it is probably not so great because of all the slice assignments, which could end up moving a lot of memory around. Still, don't assume it has to be recursive, or that it's simpler to write it that way.

This implementation does have the advantage of flattening the list "in place" rather than returning a copy, as recursive solutions invariably do. This could be useful when memory is tight. If you want a flattened copy, just pass in a shallow copy of the list you want to flatten:

flatten(mylist)                # flattens existing list
newlist = flatten(mylist[:])   # makes a flattened copy

Also, this algorithm is not limited by the Python recursion limit because it's not recursive. I'm certain this will virtually never come into play, however.


Licensed under: CC-BY-SA with attribution
Not affiliated with: Stack Overflow
Icon