Python equivalent vector :: reserve ()

Question

I am looking for the Python equivalent for a C ++ :: reserve () vector. I don’t know how large the list will be in front, but I know that it will be quite large, and I want to avoid as many changes as possible, as the list grows inside a deep inner loop.

The only solution I came up with so far is very cumbersome compared to the idiom vector :: reserve (). This solution is to pre-create the list using [No] * K, keeping track of the size of the list in a separate counter, adding or installing items in the list as necessary, and then copying a fragment of the list after it is fully assembled. Is there an alternative?

Answer 1

Similar to std::vector , the CPython list already pre-allocates more elements than it needs, and then increases the allocated space in such a way that it gives O(1) amortization. Therefore, I would leave this to this until I could prove that this profiling is indeed a bottleneck.

edit: You mentioned in the comments that you have already done profiling. In such a case, pre-allocating [None]*n may be reasonable to try to understand if these are redistributions that are a bottleneck.

If your array is numeric, I would recommend you take a look at NumPy .

Answer 2

To express this, you can create a list of predefined values ​​as follows:

 lst = [None] * N # where N = size of list 

Of course, you will need to set each index manually (as opposed to append ()) and track the last index you use.

If you must do this, this is another question (which our comrades did a good job).

Answer 3

To do this, I did some performance testing:

 def foo(n): x = [] for y in xrange(n): x.append(y) def bar(n): x = [None] * n for y in xrange(n): x[y] = y def baz(n): # This is obviously silly; we could just do range(n) # but this way makes for a fairer test x = [y for y in xrange(n)] >>> timeit.timeit(lambda:foo(1000000), number=10) 1.761765391970215 >>> timeit.timeit(lambda:bar(1000000), number=10) 0.79829286962450396 >>> timeit.timeit(lambda:baz(1000000), number=10) 0.9904259479906159 >>> timeit.timeit(lambda:foo(10000), number=1000) 1.3354106457664443 >>> timeit.timeit(lambda:bar(10000), number=1000) 0.70596751821813086 >>> timeit.timeit(lambda:baz(10000), number=1000) 0.58049759117432131