Chris Conlan

Data Scientist

Fastest Way to Flatten a List in Python

By 20 Comments

In my latest book, Fast Python, I bust a lot of speed myths in Python. Some of the most basic advice people give about optimizing Python code is wrong, likely because no one ever bothered to test it. In this book, I go back to the basics and verify (or bust) all of the advice and assumed knowledge that we share as a programming community.

In this post, I’ll show you five ways to flatten a list in Python, and then show you the test results. I consider these results to be a myth-buster, because they are not at all what I expected based on what we consider best practice in the Python community.

The methods

# Use long-form list addition
def slow_add_flatten_lists(the_lists):
    result = []
    for _list in the_lists:
        result = result + _list
    return result

# Use list addition with the += operator
def add_flatten_lists(the_lists)
    result = []
    for _list in the_lists:
        result += _list
    return result

# Use List.extend
def extend_flatten_lists(the_lists):
    result = []
    for _list in the_lists:
        result.extend(_list)
    return result

# Use List.append
def append_flatten_lists(the_lists)
    result = []
    for _list in the_lists:
        for val in _list:
            result.append(val)
    return result

# Use a nested list comprehension
def comprehension_flatten_lists(the_lists)
    return [val for _list in the_lists for val in _list]

Most people would expect the third or fifth option to be fastest, because they are the most concise and best utilize Python’s existing data structures to achieve the desired outcome, but this is not the case. For some reason, the second method, using list addition with the += operator, is the fastest by a large margin. Here are the profiles.

Most people assume that the += operator on lists must be slow, because a += b is likely just syntactical sugar for a = a + b, which is provably slow. This isn’t the case. The += operator is optimized in some other ways for Python lists, as is proven by the code profiles, and it is not at all equivalent to a = a + b. Surprisingly enough, it is not only optimized, but it ends up being the fastest known method the flatten a list.

Check out Fast Python if you are interested in busting more speed myths and learning how to optimize your Python code. Writing this book has been very helpful to my own programming, because it has given me access to empirical evidence for my speed-based design decisions.

Comments

  3. says

    June 10, 2020 at 2:05 pm

    There’s another fast way to flatten a list:

    def reduce_flatten_list(
    the_lists: List[List[str]]) -> List[str]:
    “””
    Flatten a list of lists via functools.reduce
    “””
    return list(functools.reduce(operator.iconcat, the_lists, []))

    I benchmarked this and (on my machine) this is the fastest up to input length 10^5. Thereafter it’s nearly as fast the add_flatten_lists.
    I also noticed that my graphs are not consistent with yours (due to other processor, OS, …?)

    Reply

  4. says

    June 12, 2020 at 1:31 pm

    I’ve been using this function to flatten an arbitrary deep nested list:

    def flatten(arg: list, sort_results=False) -> list:
    """
    This function takes an object graph (really, just a list of lists/tuples of
    lists/tuples etc) and flattens it into a one-dimensional list.
    """

    def helper(result, arg):
        if isinstance(arg, list):
            for x in arg:
                helper(result, x)
        elif isinstance(arg, tuple):
            for x in arg:
                helper(result, x)
        elif isinstance(arg, set):
            for x in sorted(arg):
                helper(result, x)
        else:
            result.append(arg)
        return result

    r = helper(list(), arg)
    return sorted(r) if sort_results else r
    Reply

  6. Isaias says

    November 4, 2020 at 11:09 pm

    Indeed, I’ve checked that add_flatten_lists is faster even compared to :

    import functools, operator
    def functools_flatten(list_of_lists: Iterable[Iterable]):
    return functools.reduce(operator.iconcat, list_of_lists, [])

    Which was the fastest approach for python2

    Results for list of n list with variable number of up to 5 inner elements.
    n add_flatten_lists functools_flatten
    1 3.024376928806305e-07 5.057640373706817e-07
    10 6.841495633125305e-07 9.091570973396302e-07
    100 4.355348646640778e-06 5.3446926176548e-06
    1000 4.190962761640549e-05 4.575522616505623e-05
    10000 0.00041823429986834524 0.00044615136459469796
    100000 0.004164023883640766 0.004406414236873388
    1000000 0.04450144730508328 0.04704729903489351
    10000000 0.5981661455519497 0.6272326799668372

    Reply

Leave a Reply