flatten a list of list

[Scott David Daniels]

Steven D'Aprano wrote:
> On Sun, 16 Aug 2009 02:47:42 -0700, Terry wrote:
>> Is there a simple way (the pythonic way) to flatten a list of list?
> 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]

OK, it definitely helps to get a size estimate before building:

 >>> setup = """\\
L = [ [None]*5000 for _ in xrange(%d) ]
import itertools

class Holder(object):
     def __init__(self, list_of_lists):
         self._list = list_of_lists
     def __iter__(self):
         return itertools.chain.from_iterable(self._list)
     def __len__(self):
         return sum(len(x) for x in self._list)
"""

 >>> timeit.Timer("list(Holder(L))", setup % 4).repeat(number=1000)
[0.59912279353940789, 0.59505886921382967, 0.59474989139681611]
 >>> timeit.Timer("list(Holder(L))", setup % 8).repeat(number=1000)
[1.1898235669617208, 1.194797383466323, 1.1945367358141823]
 >>> timeit.Timer("list(Holder(L))", setup % 16).repeat(number=1000)
[2.4244464031043123, 2.4261885239604482, 2.4050011942858589]

vs straight chain.from_iterable (on my machine):

[0.7828263089303249, 0.79326171343005925, 0.80967664884783019]
[1.499510971366476, 1.5263249938190455, 1.5599706107899181]
[3.4427520816193109, 3.632409426337702, 3.5290488036887382]

--Scott David Daniels
Scott.Daniels at Acm.Org