On Aug 16, 1:25 pm, Steven D'Aprano <st...@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 -- http://mail.python.org/mailman/listinfo/python-list