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.
What about itertools.chain.from_iterable?
Someone mentioned that before. Does that compress a list in one shot? How does it work? I will likely include it in the repo.
lol = [‘a’, [‘a’, ‘b’, ‘c’], range(1,22)]
lol
import itertools as it
list(it.chain.from_iterable(lol))
or [*it.chain.from_iterable(lol)], since the list() is slower than [].
https://twitter.com/tintvrtkovic/status/1248995617256374273
I didn’t think to try += though, it seems quadratic on the face of it.
https://twitter.com/tintvrtkovic/status/1248995617256374273
I didn’t think to try +=, it seemed quadratic on the face of it…
What Terry said.
I didn’t time it, but I’ll be surprised if it’s slower.
Also, unlike all of the examples used, this method uses a generator and would be well-suited to streaming very large inputs with minimal memory use. For example:
I tried the itertools variant. It is exactly the same speed at the List.extend variant. So, still not the fastest. I’ve added it to the GitHub repo: https://github.com/chrisconlan/fast-python/blob/master/src/flatten_lists.py
What about [*] instead of list()?
Same performance. Doesn’t affect it
I tested it. See my response to Reese.
Has anyone tried the following:
list = sum(list, [])
Quick tests on Python 3.8 with timeit and a short list show it the fastest, don’t know how it scales though. Got the snippet from StackOverflow (https://stackoverflow.com/questions/50082861/how-to-convert-a-magic-square-into-a-proper-magic-square-in-python-3)
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, …?)
It is very possible your profiles are different. I used whatever Python version ships with Anaconda, which might have OS-level or byte-compiler-level optimizations that others don’t.
One of the big lessons here is that we don’t know as Python programmers which C-level optimizations are in-play at any given time, so we just have to profile to find out.
What do you think of the quite different approach with reduce?
I haven’t tried it. I encourage you to download the repo and consider contributing if you think your example is constructive: https://github.com/chrisconlan/fast-python
I think it’s easier if you just add it yourself.
I’ve been using this function to flatten an arbitrary deep nested list:
what a about
Indeed, I’ve checked that add_flatten_lists is faster even compared to :
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
Thanks for this. I’m dealing with multidimensional lists with over a million rows once flattened. Flattening them has been quite the time-consuming challenge but the extend_flatten_lists() function you provided is exceptionally fast and computationally efficient.
This version of extend beats the
+=
one:def new_extend_flatten_lists(the_lists):
result = []
extend = result.extend
for _list in the_lists:
extend(_list)
return result