# flatten a list of list

Francesco Bochicchio bieffe62 at gmail.com
Sun Aug 16 19:12:29 CEST 2009

```On Aug 16, 1:25 pm, Steven D'Aprano <st... at REMOVE-THIS-
cybersource.com.au> wrote:

...

> Chris' suggestion using itertools seems pretty good:
>
> >>> from timeit import Timer
> >>> setup = """\\
>
> ... L = [ [None]*5000 for _ in xrange(%d) ]
> ... from itertools import chain
> ... """>>> Timer("list(chain.from_iterable(L))", setup % 4).repeat(number=1000)
>
> [0.61839914321899414, 0.61799716949462891, 0.62065696716308594]>>> Timer("list(chain.from_iterable(L))", setup % 8).repeat(number=1000)
>
> [1.2618398666381836, 1.3385050296783447, 3.9113419055938721]>>> Timer("list(chain.from_iterable(L))", setup % 16).repeat(number=1000)
>
> [3.1349358558654785, 4.8554730415344238, 5.4319999217987061]
>
> --
> Steven

I had a peek at itertools ( which is a C module btw) and realized that
chain solves the problem by creating a chain object,
which is a sort of generator. Both creating the chain object and
converting the chain object to a list seem to be O(N), so
the whole is O(N) too ...

Then I tried this pure python version:

# ----- CODE
from timeit import Timer
setup = """\\
L = [ [None]*5000 for _ in range(%d) ]
def pychain( list_of_list ):
for l in list_of_list:
for elem in l:
yield elem
"""

print( Timer("list(pychain(L))", setup % 4).repeat(number=1000))
print( Timer("list(pychain(L))", setup % 8).repeat(number=1000))
print( Timer("list(pychain(L))", setup % 16).repeat(number=1000))
# ----- END CODE

and got times that seem to confirm it :

[2.818755865097046, 2.7880589962005615, 2.79232120513916]
[5.588631868362427, 5.588244915008545, 5.587780952453613]
[11.620548009872437, 11.39465618133545, 11.40834903717041]

For reference, here are the times of the itertools.chain solution on
my laptop:

[0.6518809795379639, 0.6491332054138184, 0.6483590602874756]
[1.3188841342926025, 1.3173959255218506, 1.3207998275756836]
[2.7200729846954346, 2.5402050018310547, 2.543621063232422]

All this with Python 3.1 compiled from source on Xubuntu 8.10.

Ciao
-----
FB

```