C++有std :: vector，Java有ArrayList，許多其他語言都有自己的動態分配數組形式。當動態數組空間不足時，它將被重新分配到更大的區域，並將舊值複製到新數組中。這種陣列性能的核心問題是陣列的大小有多快。如果你總是變得足夠大以適應當前的推動，那麼你最終每次都會重新分配。因此，將數組大小加倍或將其乘以1.5倍是有意義的。動態分配數組的理想增長率是多少？
是否有理想的生長因子？ 2倍？ 1.5倍？理想情況下，我的意思是數學上合理的，最佳平衡性能和浪費的內存。我意識到理論上，考慮到你的應用程序可能有任何潛在的推送分佈，這在某種程度上取決於應用程序。但我很想知道是否存在「通常」最好的價值，或者在一些嚴格的限制內被認爲是最好的。
我聽說這裏有一篇論文，但我一直無法找到它。
這完全取決於用例。你是否更關心浪費時間複製數據（並重新分配數組）或額外的內存？陣列持續多久？如果它不會持續很長時間，那麼使用更大的緩衝區可能是一個好主意 - 懲罰只是短暫的。如果它會停滯不前（例如用Java，進入老一代和老一代），那顯然更多的是懲罰。
沒有這樣的「理想增長因素」。這不僅僅是理論上應用程序依賴，它的絕對應用程序相關。
2是一個非常常見的增長因素 - 我很確定這就是.NET中使用的ArrayList和List<T>。 Java中的ArrayList<T>使用1.5。
編輯：正如Erich指出的那樣，.NET中的Dictionary<,>使用「大小增加一倍然後增加到下一個素數」，以便散列值可以在存儲桶之間合理分配。 （我相信我最近看到過文檔暗示質數對於散列散列桶並不是那麼好，但這是另一個答案的一個參數。）
我同意Jon Skeet，即使我的theorycrafter朋友堅持認爲當將係數設置爲2x時，可以證明這是O（1）。
cpu時間和內存之間的比率在每臺機器上都不相同，因此這個因子也會變化很多。如果你有一臺內存爲千兆字節RAM和CPU速度較慢的機器，將這些元素複製到一個新陣列比在一臺快速機器上要昂貴得多，而這可能會減少內存。這是一個理論上可以回答的問題，對於一臺統一的計算機來說，在實際的情況下它根本不會對你有所幫助。
我記得很多年前爲什麼1.5比2更適合使用，至少應用於C++（這可能不適用於運行時系統可以隨意重定位對象的託管語言）。
原因是這樣的：
這個想法是，在2倍擴展的情況下，沒有時間點產生的空洞將會足夠大以便重新用於下一個分配。使用1.5x分配，我們可以改爲：
我發現一個隨機論壇帖子（http://objectmix.com/c/129049-can-array-allocation-cause-memory-fragmentation.html）的原因類似。海報聲稱（1 + sqrt（5））/ 2是重用的上限。 – Naaff 2009-07-08 21:05:25
如果這個說法是正確的，那麼phi（==（1 + sqrt（5））/ 2）確實是最佳使用的數字。 – 2009-07-08 21:07:25
我喜歡這個答案，因爲它揭示了1.5倍與2倍的基本原理，但是Jon的技術上在我說的方式上是最正確的。我應該問過去爲什麼1.5被推薦：p – 2010-04-15 15:00:03
這真的取決於。有些人分析了常見的使用情況以找到最佳的數字。
我見過1.5x 2.0x phi x，之前使用過2次冪。回答這樣的問題時
一種方法是隻是「欺騙」，看看哪些流行庫做的假設下，一個廣泛使用的庫，起碼，不是做一些可怕的事情。因此，只要檢查得非常快，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，所以帶有bitshifts和三元運算符的表達式實際上只是計算過度分配。
如果你有超過數組的長度分佈，和你有一個效用函數，說你喜歡多大的浪費空間與浪費時間，那麼你可以毫不猶豫地選擇最佳的調整大小（與初始大小）的策略。
簡單常量倍數使用的原因，顯然是每個附加有攤分常量時間。但這並不意味着你不能爲小尺寸使用不同的（較大的）比例。
在Scala中，您可以使用查看當前大小的函數來覆蓋標準庫散列表的loadFactor。奇怪的是，可調整大小的陣列只有兩倍，這是大多數人在實踐中所做的。
我不知道任何加倍（或1.5 *荷蘭國際集團），實際趕上內存不足的錯誤，並生長在這種情況下，少列。看起來，如果你有一個巨大的單一陣列，你會想這樣做。
我想進一步補充說，如果你將可調整大小的數組保持足夠長的時間，並且隨着時間的推移你喜歡空間，那麼最初可以大幅度地置位（對於大多數情況），然後重新分配到合適的大小當你完成。
假設您將陣列大小增加x。因此，假設你從尺寸T開始。下一次增長陣列時，其大小將爲T*x。那麼它將是T*x^2等等。
如果你的目標是能夠重新使用之前已經建立的內存，那麼你要確保你分配新的內存小於以前的記憶，你釋放的總和。因此，我們有這樣的不等式：
T*x^n <= T + T*x + T*x^2 + ... + T*x^(n-2)
我們可以從兩邊刪除T.因此，我們得到這個：
x^n <= 1 + x + x^2 + ... + x^(n-2)
非正式的，我們說的是，在nth分配，我們希望所有的先前釋放的內存爲大於或等於第n分配，使我們可以重新使用的內存需求先前釋放內存。
舉例來說，如果我們希望能夠在第三步（即n=3），那麼我們就必須做到這一點
x^3 <= 1 + x
這個公式是對所有的x，使得0 < x <= 1.3（大致）
看看x我們得到不同的n是下面：
n maximum-x (roughly)
3 1.3
4 1.4
5 1.53
6 1.57
7 1.59
22 1.61
需要注意的是不斷增長的因素必須小於2罪ce x^n > x^(n-2) + ... + x^2 + x + 1 for all x>=2。
理想的情況下（在極限ñ→∞），it's the golden ratio：φ= 1.618 ...
在實踐中，你想要的東西密切，像1.5。
其理由在上面的說明鏈接 - 它涉及求解等式XN - 1 = Xn + 1個 - XÑ，其正解是x = φ。
我知道這是一個古老的問題，但有幾件事似乎每個人都失蹤了。
首先，這是乘以2：尺寸< < 1.這是通過1和2之間的任何乘法：INT（浮動（大小）* x），其中x是數量，*是浮點數學，並且處理器必須在float和int之間運行額外的指令。換句話說，在機器級別，加倍需要一個非常快速的指令來查找新的大小。通過1和2之間的東西乘以要求至少一個指令投尺寸爲浮點數，一個指令乘以（這是浮動乘法，所以它可能需要至少兩倍的週期，如果不是4或甚至8倍很多），以及一個指令投退爲int，並假定你的平臺可以對通用寄存器執行，而不需要使用特殊寄存器浮點運算。總之，您應該期望每次分配的數學計算至少需要十次，只要簡單的左移。如果您在重新分配期間複製大量數據，這可能沒有多大區別。
其次，也許是最大的踢球者：每個人似乎都認爲正在被釋放的內存既與自身連續，又與新分配的內存連續。除非您自己預先分配所有內存，然後將它用作池，否則幾乎肯定不是這種情況。操作系統可能偶爾會在這樣做，但大多數情況下，將會有足夠的空閒空間碎片，任何一半體面的內存管理系統都能夠找到一個小小的空間，您的內存將適合您。一旦你真的有點大塊，你很可能會結束連續的片斷，但是到那時，你的分配足夠大，以至於你沒有足夠頻繁地進行分配，因爲它不再那麼重要。簡而言之，設想使用一些理想的數字可以最有效地使用可用內存空間是很有趣的，但事實上，除非您的程序在裸機上運行，否則不會發生這種情況（因爲沒有OS在它下面做出所有決定）。
我對問題的回答是？不，沒有理想的數字。這是特定應用程序，甚至沒有人真正嘗試。如果你的目標是理想的內存使用情況，那麼你幾乎沒有運氣。對於性能而言，分配的頻率越低越好，但如果我們這樣做，我們可以乘以4甚至8！當然，當Firefox一次性使用1GB跳到8GB時，人們會抱怨，所以甚至沒有意義。這裏有一些經驗法則，我會去：
如果你不能優化內存使用，至少不要浪費處理器週期。乘以2至少比做浮點數學運算快一個數量級。它可能沒有太大的區別，但至少會有所作爲（特別是在更頻繁和更小的分配期間）。
不要過時。如果你花了4個小時試圖弄清楚如何完成已經完成的工作，那麼你就浪費了時間。完全誠實地說，如果有一個比* 2更好的選擇，它將在幾十年前的C++向量類（以及許多其他地方）中完成。
最後，如果你真的想優化，不要汗流small背的東西。現在，沒有人關心浪費4KB內存，除非他們在嵌入式系統上工作。當你獲得1GB到1MB到10MB之間的對象時，加倍可能太多了（我的意思是，這是100到1,000個對象）。如果您可以估計預期的擴張速度，那麼您可以在某個點將其平穩增長至線性增長率。如果您期望每分鐘大約10個物體，那麼每個步驟以5到10個物體大小（每30秒到一分鐘一次）增長可能沒問題。
這一切都歸結爲，不要過多考慮，優化可以使用的內容，並在必要時自定義到您的應用程序（和平臺）。
另兩分錢
old*3/2來計算，所以不需要浮點運算。 （我說/2，因爲如果編譯器認爲合適，編譯器會用生成的彙編代碼中的位移代替它）。正如某人所說的2感覺比8好。而且2感覺好於1.1。
我的感覺是1.5是一個很好的默認值。除此之外，這取決於具體情況。
詳細說明，將數組大小加倍意味着您可以獲得** amotized ** O（1）個插入。 這個想法是，每當你插入一個元素，你也複製舊數組中的一個元素。 假設你有一個大小爲_m_的數組，其中有_m_個元素。添加元素_m + 1_時，沒有空格，因此您分配了一個尺寸爲_2m_的新數組。每次插入新元素時，不要複製所有第一個_m_元素，而是複製一個元素。這將最小化差異（除了內存分配），並且一旦你插入了2m元素，你將複製舊數組中的所有元素。 – hvidgaard 2014-11-04 10:06:38