flatten a list of list

[Steven D'Aprano]

On Sun, 16 Aug 2009 02:47:42 -0700, Terry wrote:

> Hi,
> 
> Is there a simple way (the pythonic way) to flatten a list of list?
> rather than my current solution:
> 
> new_list=[]
> for l in list_of_list:
>     new_list.extend(l)

I don't think that scales terribly well. In my testing, it performs about 
as badly as the O(N**2) behaviours others have suggested (using sum or 
reduce with add) -- perhaps a bit worse for small N, but not quite as 
badly for large N.


> new_list=reduce(lambda x,y:x.extend(y), list_of_list)

That doesn't even work.

>>> list_of_list = [ [1,2,3], [2, 4, 8] ]
>>> new_list=reduce(lambda x,y:x.extend(y), list_of_list)
>>> new_list is None
True



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