確保列表的容量

我正在瀏覽如何創建自己的列表並登錄在此網站http://www.vogella.com/tutorials/JavaDatastructureList/article.html他們有以下方法。確保列表的容量

private void ensureCapa() { 
    int newSize = elements.length * 2; 
    elements = Arrays.copyOf(elements, newSize); 
}

我發現了許多其他網站類似的方法和明白的ensureCapacity一樣。但我不明白爲什麼長度乘以2（elements.length * 2）。是否有特定的原因或者是否因數據類型而異？

在此先感謝。

來源

2016-02-05 SDJ

這是爲了使'add（）'操作的平均成本爲O（1）'：'1 + 2 + 4 + ... + 2^n = 2 * 2^n - 1' - > n個插入成本〜O（n） –

由於幾個原因，完成列表的容量加倍會導致容量翻倍。

正如@jheimbouch和@ user3437460所說，它有點直觀。您希望以與當前列表大小成比例的數量增加它。每次在最後添加一些固定的元素可能最終成爲一個大胖子列表非常糟糕。

一般來說它更有效率。如果你不清楚列表的大小是多少（就像設計自己的基於數組的列表類一般用時一樣），如果每次將列表的大小加倍，那麼平均每個列表的大小大量的插入，每個插入將持續時間爲O(1)（這稱爲「攤銷恆定時間」操作）。

想一想，調整數組大小的代價是n。所以我們唯一可以調整的是我們多頻繁地這樣做。我們做得越頻繁，我們的數組就越緊密地與我們的實際數據大小相關聯，所以我們使用的內存更少。我們做這件事的次數越少，我們就節省CPU週期。

有證據比比皆是關於時間複雜度，但這裏有一個我發現很快http://anh.cs.luc.edu/363/notes/06A_Amortizing.html

長話短說，這是數學的聲音在一般情況下，和罷工內存消耗和處理時間之間的很好的平衡。

來源

2016-02-05 15:08:16 CollinD

這是一種常用的做法，以便不必一直複製陣列。例如，如果是elements.length + 1，則每次添加元素時都會複製到新數組。

簡而言之，這是任意的，你可以通過你選擇的任何東西來增加尺寸。

來源

2016-02-05 14:58:09 jheimbouch

特別是，通過增加列表大小的因子'c> = 2'，您可以實現攤銷不變的插入時間。所以它不完全是任意的。 – CollinD

@CollinD，你有這方面的資料嗎？ – jheimbouch

這裏有大約十億個不同的證據，我的特殊來源是幾年前在大學裏的一門課，但這裏有一個我很快找到的課程http://anh.cs.luc.edu/363/notes/06A_Amortizing.html基本上（1）插入時間，因爲第一個'n'插入需要O（1），然後需要'2n e O（n）'時間。沖洗並重復，平均來說，它是'2n/n = 2 e O（1）'用於插入。 – CollinD

但我不明白爲什麼長度乘以2（elements.length * 2）。是否有特定的原因或者是否因數據類型而異？

你不會想要一個固定的值，以增加大小說5.通過加倍容量根據當前的元素，一定程度上的數量，確保效率（這樣你就不必執行數組一直都在複製）。

假設你有1000個元素，它現在是滿的，這是必然的，因爲它可能有另外1000元進來加倍。但是，如果你有一個固定的值增加的能力，你很可能會添加過多容量太大或太少。

當你添加太多時，你正在浪費內存，但是如果你添加的很少，你很可能需要頻繁地執行另一個數組拷貝，因爲這意味着你更有可能調整當前的數組添加新元素時。

來源

2016-02-05 15:02:54 user3437460

確保列表的容量

回答

相關問題