我知道這里回答了一個類似的問題：Python 的串列是如何實作的？但我想問更多關于具體情況。我想更多地了解 CPython 如何實作串列大小調整。我對 C 不太熟悉，所以我很難閱讀源代碼。
我想我明白的是，有串列的大小Py_ssize_t ob_size和分配給串列的數量Py_ssize_t allocated，當ob_size達到時allocated，需要分配更多的記憶體。我假設如果系統允許，記憶體將被分配到位，否則串列將被復制到記憶體中的另一個位置。特別是，我問的是選擇改變多少allocated。從listobject.c，新分配的記憶體如下：
new_allocated = (size_t)newsize (newsize >> 3) (newsize < 9 ? 3 : 6);
本質上，我們使分配的物件大小比所需的物件大小多 1/8（忽略常量）。我想知道為什么選擇這個 1/8？在我的介紹性編碼課程中，我記得學習了 ArrayLists，當它滿時，它的大小會增加一倍。也許也可以選擇增加 1/2 或 1/4。增加越小，一長串追加的攤銷時間越差（仍然是常數，但有一個更大的因素），所以 1/8 似乎是一個糟糕的選擇。我的猜測是每次分配少量將增加能夠重新分配到位的機會。這是正確的推理嗎？這個 CPython 實作在實踐中運行良好嗎？
注意：在洗掉元素后減少串列的分配記憶體時，當串列已下降到原始大小的一半時會發生這種情況，從這部分代碼可以看出：
/* 當先前的過度分配大到足以容納新大小時，繞過 realloc()。如果 newsize 低于分配大小的一半，則繼續執行 realloc() 以縮小串列。*/
if (allocated >= newsize && newsize >= (allocated >> 1)) {
uj5u.com熱心網友回復：
那么，基于對21歲的人犯該實施這種行為的原因是“因為它提高添彼得斯的Win98的箱子記憶體行為”。從下面的提交中復制蒂姆的評論。
在我的 Win98SE 機器上準確計時是不可能的，但是對于合理的 list.append() 情況，即使在這個機器上這顯然更快。我認為這不是調整大小策略，而是在計算四舍五入大小時擺脫整數乘法和除法（有利于移位）。
對于不合理的 list.append() 情況，Win98SE 現在顯示線性行為，將一次添加到大約 3500 萬個元素的串列中。然后它因 記憶體錯誤而死，由于致命的碎片化地址空間（有很多可用的 VM，但此時 Win9X 已將用戶空間分成許多不同的堆，其中沒有一個有足夠的連續空間來調整串列的大小，無論出于何種原因Win9x 不會合并死堆）。在補丁之前，出于同樣的原因，它出現了 MemoryError，但是一旦串列達到大約 200 萬個元素。
還沒有在 Win2K 上嘗試過，但寄予厚望，極端 list.append() 現在會表現得更好（NT 和 Win2K 沒有對地址空間進行碎片化，但在串列變大之前遭受了明顯的二次時間行為）。
對于其他系統，我依賴于常識：用 << 和 >> 替換整數 * 和 / 似乎不會受到傷害，函式呼叫的數量沒有改變，并且相當小的串列的總操作計數大約是相同（雖然現在操作更便宜）。
...
這與串列大小成比例地過度分配，為額外增長留出空間。過度分配是輕微的，但足以在存在性能不佳的系統 realloc() 的情況下在很長的 appends() 序列上提供線性時間攤銷行為（這是一個現實，例如，在所有版本的 Windows ，Win9x 的行為特別糟糕——即使使用這種方案，我們在 Win9x 上仍然存在地址空間碎片問題，盡管它需要比以前長得多的串列來激發它們）。
Raymond Hettinger 在此提交中進一步調整了這些值：
Py2.3 方法將小串列過度分配了多達 8 個元素。最后一次簽入將其限制為一個，但減慢了（20% 到 30%）3 到 8 個元素之間的小串列的創建。
這種調整平衡了兩者，將過度分配限制為 3 個元素（顯著減少了 Py2.3 的空間消耗）并且運行速度比之前的簽入更快。
增長模式的第一部分 (0, 4, 8, 16) 與僅在跨越 2 次冪邊界時觸發資料移動的分配器緊密結合。此外，偶數與常見的資料對齊方式很好地融合。
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/339440.html