从预先分配的列表开始并在每个索引处设置项目是否比从空列表开始并附加项目更快？我需要这个列表来保存 10k-100k 项。
我问是因为我正在尝试实现一种算法，该算法在每个递归级别都需要 O(n) 时间，但我得到的结果表明 O(n^2) 时间。我想也许 python 需要不断调整列表的大小可能会导致这种放缓。
我发现了类似的问题，但没有一个明确回答我的问题。一个答案表明垃圾收集可能非常慢，有这么多项目，所以我尝试打开和关闭 gc，但结果没有改善。
已解决的问题：如果有人好奇，减速是由于联合集合太频繁造成的。现在我使用不同的方法（涉及排序）来检查是否两次看到相同的键。
Python 以与列表大小成比例的块的形式预先分配列表。这为附加到列表提供了摊销 O(1)
这是一个简单的测试，用于查看列表何时增长。请注意，其中许多将能够就地重新分配，因此并不总是需要复制
>>> 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