使用python反覆追加的速度

從預先分配的列表開始，並在每個索引處設置項目，而不是以空列表和附加項目開始，是否更快？我需要這個清單來保存10k-100k的物品。使用python反覆追加的速度

我問，因爲我想實現一個算法，需要O（n）時間在遞歸的每個級別，但我得到的結果表明O（n^2）時間。我想可能python需要不斷調整列表大小可能會導致這種放緩。

我發現了類似的問題，但沒有明確回答我的問題。一個答案表明，垃圾收集可能會非常緩慢，所以我試着打開和關閉gc，結果沒有改善。

問題已解決：如果有人很好奇，經濟衰退是由於經常性地將工會集合在一起造成的。現在我使用一種不同的方法（涉及排序）來檢查是否同一個鍵被看到兩次。

2013-10-09 Tyler Brabham

當你試圖獲得更好的性能，我不會使用追加或在位置插入在所有推薦：嘗試使用列表理解，它可以一次構建所有列表，而不是從C跳到Python多次。另一個可能的瓶頸可能是測試列表中項目的成員身份，在這種情況下，設置或字典速度更快，但是您爲每個存儲項目消耗的內存支付了一點。祝你好運。 –

感謝您的回覆。我將嘗試僅使用列表解析來初始化所有列表。 –

另外，正如你所建議的那樣，我正在使用字典和成員集。 –

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

來源

2013-10-10 00:00:40

你是說python離開當前列表，然後創建一個相同大小的新列表，並將兩者連接起來？ –

@TylerBrabham，如果沒有足夠的空間來重新分配列表，則會創建一個新的更大的列表並將其引用複製到它 –

您認爲這種線性重新分配會導致明顯更長的時間來計算嗎？由於O（1）攤銷時間，我傾向於「不常用」。 –

使用python反覆追加的速度

回答

相關問題