C ++具有std :: vector，而Java具有ArrayList，許多其他語言都有其自己的動態分配數組形式。當動態數組空間不足時，它將重新分配到更大的區域中，并將舊值復制到新數組中。這種陣列性能的核心問題是陣列大小增長的速度。如果您總是只增長到足以容納當前推送的大小，則最終每次都會重新分配。因此，將數組大小加倍或乘以1.5倍是有意義的。有理想的成長因素嗎？2倍？1.5倍？理想情況下，我的意思是數學上合理的，最佳的平衡性能和浪費的內存。我意識到從理論上講，鑒于您的應用程序可能具有任何潛在的推送分布，因此這在某種程度上取決于應用程序。但是我很想知道是否有一個值“通?！笔亲詈玫?，或者在某些嚴格的約束條件下被認為是最好的。我聽說某處有一篇論文，但我一直找不到。
3 回答
侃侃無極
TA貢獻2051條經驗 獲得超10個贊
在回答這樣的問題時，一種方法是僅“欺騙”并查看流行的庫所做的事情，前提是假定廣泛使用的庫至少沒有做任何可怕的事情。
因此，只需快速檢查一下，Ruby（1.9.1-p129）在追加到數組時似乎使用1.5x，而Python（2.6.2）使用1.125x加一個常量（在中Objects/listobject.c）：
/* This over-allocates proportional to the list size, making room
* for additional growth. The over-allocation is mild, but is
* enough to give linear-time amortized behavior over a long
* sequence of appends() in the presence of a poorly-performing
* system realloc().
* The growth pattern is: 0, 4, 8, 16, 25, 35, 46, 58, 72, 88, ...
*/
new_allocated = (newsize >> 3) + (newsize < 9 ? 3 : 6);
/* check for integer overflow */
if (new_allocated > PY_SIZE_MAX - newsize) {
PyErr_NoMemory();
return -1;
} else {
new_allocated += newsize;
}
newsize以上是數組中元素的數量。請注意，它newsize已添加到new_allocated，因此具有位移和三元運算符的表達式實際上只是在計算超額分配。
添加回答
舉報
0/150
提交
取消