Is it faster substantially to start with a preallocated list and set items at each index, as opposed to starting with an empty list and appending items? I need this list to hold 10k-100k items.
I ask because I am trying to implement an algorithm that requires O(n) time at each level of recursion, but I am getting results that indicate O(n^2) time. I thought perhaps python needing to keep resizing the list might cause this slowdown.
I found similar questions but none that explicitly answered my question. One answer indicated that garbage collecting might be very slow with so many items, so I tried turning gc on and off at saw no improvement in results.
PROBLEM SOLVED: If anyone is curious, the slowdown was caused by unioning sets together too often. Now I use a different method (involves sorting), to check if the same key is seen twice.
Python preallocates the list in chunks that are proportional to the size of the list. This gives amortized O(1) for appending to lists
Here is a simple test to see when a list grows. Note that many of these will be able to be reallocated in place, so a copy over isn't always necessary
>>> import sys
>>> A = []
>>> sz = sys.getsizeof(A)
>>> for i in range(100000):
... if sz != sys.getsizeof(A):
... sz = sys.getsizeof(A)
... print i, sz
... A.append(i)
...
1 48
5 64
9 96
17 132
26 172
36 216
47 264
59 320
73 384
89 456
107 536
127 624
149 724
174 836
202 964
234 1108
270 1268
310 1448
355 1652
406 1880
463 2136
527 2424
599 2748
680 3116
772 3528
875 3992
991 4512
1121 5100
1268 5760
1433 6504
1619 7340
1828 8280
2063 9336
2327 10524
2624 11864
2959 13368
3335 15060
3758 16964
4234 19108
4770 21520
5373 24232
6051 27284
6814 30716
7672 34580
8638 38924
9724 43812
10946 49312
12321 55500
13868 62460
15608 70292
17566 79100
19768 89012
22246 100160
25033 112704
28169 126816
31697 142692
35666 160552
40131 180644
45154 203248
50805 228676
57162 257284
64314 289468
72360 325676
81412 366408
91595 412232