Python: fastest way to create a list of n lists


Question

So I was wondering how to best create a list of blank lists:

[[],[],[]...]

Because of how Python works with lists in memory, this doesn't work:

[[]]*n

This does create [[],[],...] but each element is the same list:

d = [[]]*n
d[0].append(1)
#[[1],[1],...]

Something like a list comprehension works:

d = [[] for x in xrange(0,n)]

But this uses the Python VM for looping. Is there any way to use an implied loop (taking advantage of it being written in C)?

d = []
map(lambda n: d.append([]),xrange(0,10))

This is actually slower. :(

1
86
4/1/2011 8:23:59 PM

Accepted Answer

The probably only way which is marginally faster than

d = [[] for x in xrange(n)]

is

from itertools import repeat
d = [[] for i in repeat(None, n)]

It does not have to create a new int object in every iteration and is about 5 % faster on my machine.

Edit: Using NumPy, you can avoid the Python loop using

d = numpy.empty((n, 0)).tolist()

but this is actually 2.5 times slower than the list comprehension.

92
5/11/2019 11:09:01 PM

The list comprehensions actually are implemented more efficiently than explicit looping (see the dis output for example functions) and the map way has to invoke an ophaque callable object on every iteration, which incurs considerable overhead overhead.

Regardless, [[] for _dummy in xrange(n)] is the right way to do it and none of the tiny (if existent at all) speed differences between various other ways should matter. Unless of course you spend most of your time doing this - but in that case, you should work on your algorithms instead. How often do you create these lists?


Licensed under: CC-BY-SA with attribution
Not affiliated with: Stack Overflow
Icon