6

ArrayListとLinkedListの違いは理論的にはかなりよく理解できたと思いました。しかし、初めて、ちょっとしたテストをしてみたところ、予想とはかなり違うテストが出ました。

期待：

  1. Arraylistは、最初に挿入するときにLinkedListよりも遅くなります。これは、linkedlistの場合、2つの参照を更新するだけで、要素を「シフト」する必要があるためです。

    現実：ほとんどの反復で同じであることが判明しました。選択した数回の反復では、速度が遅くなりました。

  2. Arraylistは、最初に削除するときにLinkedListよりも遅くなります。これは、Linkedlistの場合、要素を「シフト」する必要があるため、1つの要素を無効にするだけです。

    現実：物乞いから削除したときのパフォーマンスは同じでした。

テストケース：1,000,000要素

public static void main(String[] args) {
    int n = 1000000;

    List arrayList = new ArrayList(n+10);
    long milis = System.currentTimeMillis();
    for(int i= 0 ;i<n;i++){
        arrayList.add(i);
    }
    System.out.println("insert arraylist takes "+(System.currentTimeMillis()-milis)+" ms");

    List linkedList = new LinkedList();
    milis = System.currentTimeMillis();
    for(int i= 0 ;i<n;i++){
        linkedList.add(i);
    }
    System.out.println("insert linkedlist takes "+(System.currentTimeMillis()-milis)+" ms");

    //System.out.println("Adding at end");
    milis = System.currentTimeMillis();
    arrayList.add(n-5,n+1);
    System.out.println("APPEND arraylist takes "+(System.currentTimeMillis()-milis)+" ms");

    milis = System.currentTimeMillis();
    linkedList.add(n-5,n+1);
    System.out.println("APPEND linkedlist takes "+(System.currentTimeMillis()-milis)+" ms");

    //add at front
    milis = System.currentTimeMillis();
    arrayList.add(0,0);
    System.out.println("INSERT BEG arraylist takes "+(System.currentTimeMillis()-milis)+" ms");

    milis = System.currentTimeMillis();
    linkedList.add(0,0);
    System.out.println("INSERT BEG linkedlist takes "+(System.currentTimeMillis()-milis)+" ms");

    //add at middle
    milis = System.currentTimeMillis();
    arrayList.add(n/2,n/2);
    System.out.println("INSERT MIDDLE arraylist takes "+(System.currentTimeMillis()-milis)+" ms");

    milis = System.currentTimeMillis();
    linkedList.add(n/2,n/2);
    System.out.println("INSERT MIDDLE linkedlist takes "+(System.currentTimeMillis()-milis)+" ms");

    //get from front, mid, end
    milis = System.currentTimeMillis();
    arrayList.get(0);
    System.out.println("get front arraylist takes "+(System.currentTimeMillis()-milis)+" ms");

    milis = System.currentTimeMillis();
    linkedList.get(0);
    System.out.println("get front linkedlist takes "+(System.currentTimeMillis()-milis)+" ms");

    milis = System.currentTimeMillis();
    arrayList.get(n/2);
    System.out.println("get MIDDLE arraylist takes "+(System.currentTimeMillis()-milis)+" ms");

    milis = System.currentTimeMillis();
    linkedList.get(n/2);
    System.out.println("get MIDDLE linkedlist takes "+(System.currentTimeMillis()-milis)+" ms");

    milis = System.currentTimeMillis();
    arrayList.get(n-4);
    System.out.println("get last arraylist takes "+(System.currentTimeMillis()-milis)+" ms");

    milis = System.currentTimeMillis();
    linkedList.get(n-4);
    System.out.println("get last linkedlist takes "+(System.currentTimeMillis()-milis)+" ms");

    //delete from front, mid, end.
    milis = System.currentTimeMillis();
    arrayList.remove(0);
    System.out.println("del front arraylist takes "+(System.currentTimeMillis()-milis)+" ms");

    milis = System.currentTimeMillis();
    linkedList.remove(0);
    System.out.println("del front linkedlist takes "+(System.currentTimeMillis()-milis)+" ms");

    milis = System.currentTimeMillis();
    arrayList.remove(n/2);
    System.out.println("del mid arraylist takes "+(System.currentTimeMillis()-milis)+" ms");

    milis = System.currentTimeMillis();
    linkedList.remove(n/2);
    System.out.println("del mid linkedlist takes "+(System.currentTimeMillis()-milis)+" ms");

    milis = System.currentTimeMillis();
    arrayList.remove(n-4);
    System.out.println("del end arraylist takes "+(System.currentTimeMillis()-milis)+" ms");

    milis = System.currentTimeMillis();
    linkedList.remove(n-4);
    System.out.println("del end linkedlist takes "+(System.currentTimeMillis()-milis)+" ms");

}

出力ログ

insert arraylist takes 141 ms
insert linkedlist takes 312 ms
APPEND arraylist takes 0 ms
APPEND linkedlist takes 0 ms
INSERT BEG arraylist takes 0 ms
INSERT BEG linkedlist takes 0 ms
INSERT MIDDLE arraylist takes 0 ms
INSERT MIDDLE linkedlist takes 0 ms
get front arraylist takes 0 ms
get front linkedlist takes 0 ms
get MIDDLE arraylist takes 0 ms
get MIDDLE linkedlist takes 16 ms
get last arraylist takes 0 ms
get last linkedlist takes 0 ms
del front arraylist takes 0 ms
del front linkedlist takes 0 ms
del mid arraylist takes 0 ms
del mid linkedlist takes 15 ms
del end arraylist takes 0 ms
del end linkedlist takes 0 ms

それで、理由は何ですか？JDK1.6を使用しました。

編集：System.nanotime（）を使用した後、期待どおりに回答が得られました。同意しました。これは1回の試行であり、平均化する必要があります。

insert arraylist takes 137076082 ns
insert linkdlist takes 318985917 ns
APPEND arraylist takes 69751 ns
APPEND linkdlist takes 98126 ns
**INSERT BEG arraylist takes 2027764 ns
INSERT BEG linkdlist takes 53522 ns**
INSERT MIDDLE arraylist takes 1008253 ns
INSERT MIDDLE linkdlist takes 10395846 ns
get front arraylist takes 42364 ns
get front linkdlist takes 77473 ns
get MIDDLE arraylist takes 39499 ns
get MIDDLE linkdlist takes 9645996 ns
get last arraylist takes 46165 ns
get last linkdlist takes 43446 ns
**del front arraylist takes 1720329 ns
del front linkdlist takes 108063 ns**
del mid arraylist takes 1157398 ns
del mid linkdlist takes 11845077 ns
del end arraylist takes 54149 ns
del end linkdlist takes 49744 ns
4

3 に答える 3

6

最初の2つの（奇妙な）テスト番号の説明は次のとおりです。

ArrayListへの挿入は、境界に達すると大きくなる必要があるため、通常は遅くなります。新しい大きな配列を作成し、元の配列からデータをコピーする必要があります。

しかし、すべての挿入を収めるのに十分なnew ArrayList(n+10)大きさのArrayListを作成する場合（これは、実行しているためです）、明らかに配列のコピー操作は含まれません。LinkedListはその「リンク」（ポインター）を処理する必要があるため、LinkedListを追加するよりもさらに高速になりますが、巨大なArrayListは指定された（最後の）インデックスに値を設定するだけです。

また、各反復には自動ボクシング（intからIntegerへの変換）が含まれるため、テストは適切ではありません。これを行うには追加の時間がかかり、最初のパスでIntegersキャッシュがいっぱいになるため、結果が台無しになります。

于 2013-03-01T03:53:06.750 に答える
2

int n = 1000000;小さすぎる。0 ms挿入または削除を完了するのに時間がかからないという意味ではありません。経過時間が 1ms 未満であることを意味します。の数を増やしてみてくださいint n = 1000000;。そうすれば違いがわかります。

編集:私はあなたのコードを読み違えました。n配列リストの前に要素を挿入していると思いました。1 つだけ挿入するのではなく、必ず複数の項目を挿入する必要があります。

別の編集:n要素を挿入する場合、の値を上げる必要はありませんn。逆に、ArrayList の前に挿入すると処理が遅くなるため、おそらくこれを減らしたいと思うでしょう。

于 2013-03-01T03:43:21.897 に答える