ArrayListからの削除で初期容量が重要なのはなぜですか？

Question

私の仕事のために、私はタイムチャートのテストをいくつか行っています。 私は私を驚かせ、理解を助ける必要がある何かに来ました。

私はキューとしてデータ構造をほとんど使用せず、アイテムの数に応じて削除がどのように高速であるかを知りたいと考えました。また、初期の容量を設定していない場合は、初期容量を設定しないで、フロントから削除して10個の項目を持つarraylistは、初期容量を設定しても（15まで）はるかに遅くなります。どうして？そしてなぜそれが100の項目で同じであるか。

データ構造：

ここでグラフの コードの関連部分をアペンド：Lは - リスト、C実装 - 設定された初期容量を、B - - 背面から除去、Qは、キュー

編集を実装します

new Thread(new Runnable() { 
@Override 
public void run() 
{ 
    long time; 
    final int[] arr = {10, 100, 1000, 10000, 100000, 1000000}; 
    for (int anArr : arr) 
    { 
    final List<Word> temp = new ArrayList<>(); 
    while (temp.size() < anArr) temp.add(new Item()); 

    final int top = (int) Math.sqrt(anArr); 

    final List<Word> first = new ArrayList<>(); 
    final List<Word> second = new ArrayList<>(anArr); 
    ... 
    first.addAll(temp); 
    second.addAll(temp); 
    ... 

    SystemClock.sleep(5000); 

    time = System.nanoTime(); 
    for (int i = 0; i < top; ++i) first.remove(0); 
    Log.d("al_l", "rem: " + (System.nanoTime() - time)); 

    time = System.nanoTime(); 
    for (int i = 0; i < top; ++i) second.remove(0); 
    Log.d("al_lc", "rem: " + (System.nanoTime() - time)); 

    ... 
    } 
    } 
}).start(); 

Answer 1

この記事をAvoiding Benchmarking Pitfalls on the JVMでお読みください。ホットスポットVMがテスト結果に及ぼす影響について説明します。それに気をつけなければ、あなたの測定値は正しくありません。あなた自身のテストで見つけたように。

信頼できるベンチマークを使用したい場合は、JMHを使用してください。

Answer 2

私も以下のコードを作成することでそれを複製することができました。しかし、私は最初に実行されたもの（設定された容量と設定されていない容量）が最も長くかかることに気付きました。私はこれが何らかの最適化、おそらくJVM、または何らかのキャッシュのようなものだと思いますか？

public class Test { 



public static void main(String[] args) { 
     measure(-1, 10); // switch with line below 
     measure(15, 10); // switch with line above 
     measure(-1, 100); 
     measure(15, 100); 
    } 

    public static void measure(int capacity, long numItems) { 
     ArrayList<String> arr = new ArrayList<>(); 

     if (capacity >= 1) { 
      arr.ensureCapacity(capacity); 
     } 

     for (int i = 0; i <= numItems; i++) { 
      arr.add("T"); 
     } 
     long start = System.nanoTime(); 

     for (int i = 0; i <= numItems; i++) { 
      arr.remove(0); 
     } 

     long end = System.nanoTime(); 
     System.out.println("Capacity: " + capacity + ", " + "Runtime: " 
       + (end - start)); 
    } 
}