Create a list with initial capacity in Python

user_15055 0
Viewed 222192

Code like this often happens:

l = []
while foo:
    # baz
    l.append(bar)
    # qux

This is really slow if you're about to append thousands of elements to your list, as the list will have to be constantly resized to fit the new elements.

In Java, you can create an ArrayList with an initial capacity. If you have some idea how big your list will be, this will be a lot more efficient.

I understand that code like this can often be refactored into a list comprehension. If the for/while loop is very complicated, though, this is unfeasible. Is there an equivalent for us Python programmers?

initialization list dictionary python
10 Answers

Warning: This answer is contested. See comments.

def doAppend( size=10000 ):
    result = []
    for i in range(size):
        message= "some unique object %d" % ( i, )
        result.append(message)
    return result

def doAllocate( size=10000 ):
    result=size*[None]
    for i in range(size):
        message= "some unique object %d" % ( i, )
        result[i]= message
    return result

Results. (evaluate each function 144 times and average the duration)

simple append 0.0102
pre-allocate  0.0098

Conclusion. It barely matters.

Premature optimization is the root of all evil.

SLott_106610

Python lists have no built-in pre-allocation. If you really need to make a list, and need to avoid the overhead of appending (and you should verify that you do), you can do this:

l = [None] * 1000 # Make a list of 1000 None's
for i in xrange(1000):
    # baz
    l[i] = bar
    # qux

Perhaps you could avoid the list by using a generator instead:

def my_things():
    while foo:
        #baz
        yield bar
        #qux

for thing in my_things():
    # do something with thing

This way, the list isn't every stored all in memory at all, merely generated as needed.

user_143430

Python's list doesn't support preallocation. Numpy allows you to preallocate memory, but in practice it doesn't seem to be worth it if your goal is to speed up the program.

This test simply writes an integer into the list, but in a real application you'd likely do more complicated things per iteration, which further reduces the importance of the memory allocation.

import timeit
import numpy as np

def list_append(size=1_000_000):
    result = []
    for i in range(size):
        result.append(i)
    return result

def list_prealloc(size=1_000_000):
    result = [None] * size
    for i in range(size):
        result[i] = i
    return result

def numpy_prealloc(size=1_000_000):
    result = np.empty(size, np.int32)
    for i in range(size):
        result[i] = i
    return result

setup = 'from __main__ import list_append, list_prealloc, numpy_prealloc'
print(timeit.timeit('list_append()', setup=setup, number=10))     # 0.79
print(timeit.timeit('list_prealloc()', setup=setup, number=10))   # 0.62
print(timeit.timeit('numpy_prealloc()', setup=setup, number=10))  # 0.73
user_10791100
Piotr_Lesnicki_387960
Related