Python中list的內存增長模型有何理論依據？

python中list的所佔用的內存 增長是按照這個順序：

0, 4, 8, 16, 25, 35, 46, 58, 72, 88

實現方式為：

new_allocated = (newsize &>&> 3) + (newsize &< 9 ? 3 : 6);

有什麼好處嗎？

---

Python的list的數據結構，內存增長要求保證達到性能和空間利用率上的一個平衡。

一般都是一個係數乘上原有的長度得到新的長度，問題在於這個值選擇多少合適。但實際上這個值很大程度上是一個經驗值。絕大多數使用2或者1.5。比如：.NET使用2,、Java和C++使用1.5。在這裡Python使用的是1.125加上一個常數 (3或者6) 。至於為什麼要選擇這個數字應該有相關的實驗作支持，但是我沒能夠找到相關的論文。

更新，我找到一個為什麼係數小於1.5比較好（來源：math - What is the ideal growth rate for a dynamically allocated array?）。

設我們的係數是初始的數組大小為，為了確保我新申請的內存的大小小於我之前釋放的內存的總和（以便於能夠重用之前釋放的內存），所以有：

兩邊去掉於是

當時：

如果要所有的都成立的話那麼要求

依次類推：

所以取1.5。

---

Python作者喜歡這樣子做而已，沒什麼科學依據。

對係數有要求的人，會自己想辦法改進這個環節。

對係數沒要求的人，只要能正常使用，這數字到底是多少，他們都無所謂。。

---

推薦閱讀：