在google guava庫中的newArrayList（E ...元素）的好奇心

這段代碼是番石榴庫的簡單代碼。在google guava庫中的newArrayList（E ...元素）的好奇心

我並簡化爲方便閱讀，原單代碼看到=>link

// Case A 
public static <E> ArrayList<E> newArrayList(E... elements) { 
    int capacity = computeArrayListCapacity(elements.length); 
    ArrayList<E> list = new ArrayList<E>(capacity); 
    Collections.addAll(list, elements); 
    return list; 
} 

static int computeArrayListCapacity(int arraySize) { 
    long value = 5L + arraySize + (arraySize/10); 
    if (value > Integer.MAX_VALUE) { 
     return Integer.MAX_VALUE; 
    } 
    if (value < Integer.MIN_VALUE) { 
     return Integer.MIN_VALUE; 
    } 
    return (int) value; 
}

爲什麼組容量5L + ARRAYSIZE +（ARRAYSIZE/10）？

3例（A，B，C）有什麼不同？

//Case B 
public static <E> ArrayList<E> newArrayList(E... elements) { 
    ArrayList<E> list = new ArrayList<E>(elements.length); 
    Collections.addAll(list, elements); 
    return list; 
} 

//Case C 
public static <E> ArrayList<E> newArrayList(E... elements) { 
    ArrayList<E> list = new ArrayList<E>(); 
    Collections.addAll(list, elements); 
    return list; 
}

來源

2013-09-26 ChangUZ

那麼它會創建一個具有一點額外容量的新ArrayList。由於通常在使用動態計數的數據時使用列表，因此具有這樣的好處，即在添加下一個元素（情況b）時，列表不需要進行昂貴的調整大小。調整大小是很昂貴的，因爲它是通過創建一個新的（更大的）數組並將所有現有元素複製到該新數組中完成的。 – Matthias

你用'Integer.MIN_VALUE'提問的部分是誤導性的，我建議刪除它（不是確切的，無論如何，因爲'saturatedCast'從來沒有做過兩個測試。 – maaartinus

@maaartinus是的，我沒有使用computeArrayListCapacity方法。你可以看到'5L + arraySize +（arraySize/10）'有一個「TODO：找出正確的行爲，並記錄下來」，這是代碼在guava-Ints.java中。 – ChangUZ

沒有太多增加馬蒂亞斯註釋：

案例A是最優的當列表後的增長，但數量不多：小於10％，加上5個要素。如果它永遠不會增長，那麼你正在浪費一些記憶。如果它增長得更多，會發生一些調整，但總的來說，沒有人能夠做到。

案例B在不可能的情況下是最優的，列表不會增長。但這是不可能的，因爲通常可以使用ImmutableList。案例C首先分配一個由10個元素組成的數組，然後可以在Collections.addAll中多次替換這些數組。 IIUIC發生兩次elements.length==16（即10 -> 15 -> 22，因爲ArrayList的增長因子是1.5）。

來源

2013-09-26 08:26:08 maaartinus

註釋旁邊的註釋基本上意味着該表達式不受嚴格的研究支持，它意味着允許對列表進行一些添加，它很可能是經驗性的（隨機的），'5'表示小列表（帶有「長度」大約10，因爲他們不會從'length/10'中得到任何東西），「長度/ 10」用於大列表（長度爲幾百或幾千，因爲對於他們來說，5沒有任何東西） –

同意一切我還補充說沒有通過使用'arraySize >> 3'來代替分割（或者'arraySize >> 4'，無論是1/8還是1/16都足夠接近1/10），都不會節省大約40個週期的原因。 – maaartinus

在google guava庫中的newArrayList（E ...元素）的好奇心

回答

相關問題