ArrayListとLinkedListのパフォーマンスの違い

StackOverflow https://stackoverflow.com//questions/10656471

質問

はい、これは古いトピックですが、私はまだいくつかの混乱を持っています。

Javaでは、人々は言う:

  1. その要素にランダムにアクセスすると、ArrayListはLinkedListよりも高速です。ランダムアクセスは「n番目の要素を与える」という意味だと思います。なぜArrayListが速いのですか？

  2. LinkedListは、削除のためにArrayListよりも高速です。私はこれを理解しています。内部バックアップ配列を再割り当てする必要があるため、ArrayListは遅くなります。コードの説明:

    List<String> list = new ArrayList<String>();
list.add("a");
list.add("b");
list.add("c");
list.remove("b");
System.out.println(list.get(1)); //output "c"

  3. LinkedListは、挿入のためにArrayListよりも高速です。ここで挿入とはどういう意味ですか？いくつかの要素を元に戻してから、その要素を中央の空の場所に置くことを意味する場合、ArrayListはLinkedListよりも遅くなるはずです。挿入がadd（Object）操作のみを意味する場合、これはどのように遅くなるのでしょうか？

役に立ちましたか？

解決

その要素にランダムにアクセスすると、ArrayListはLinkedListよりも高速です。ランダムアクセスは「n番目の要素を与える」という意味だと思います。なぜArrayListが速いのですか？

ArrayList リスト内のすべての要素への直接参照を持っているので、一定の時間でn番目の要素を取得できます。 LinkedList n番目の要素に到達するには、最初からリストをトラバースする必要があります。

LinkedListは、削除のためにArrayListよりも高速です。私はこれを理解しています。内部バックアップ配列を再割り当てする必要があるため、ArrayListは遅くなります。

ArrayList それは自由になっているスロットを削除するために配列の一部をコピーする必要があるため、遅くなります。を使用して削除が行われた場合、 ListIterator.remove() API, LinkedList いくつかの参照を操作するだけです;削除が値またはインデックスによって行われた場合, LinkedList 削除する要素を見つけるために、最初にリスト全体をスキャンする必要があります。

いくつかの要素を元に戻してから、その要素を中央の空の場所に置くことを意味する場合、ArrayListは遅くなるはずです。

はい、これはそれが意味するものです。 ArrayList 実際にはより遅いです LinkedList それは配列の真ん中にスロットを解放する必要があるからです。これには、いくつかの参照を移動し、最悪の場合は配列全体を再割り当てすることが含まれます。 LinkedList いくつかの参照を操作するだけです。

他のヒント

今のところこの答えを無視してください。他の回答、特に AIX のそれは大部分が正しいです。長期にわたって彼らは賭ける方法です。また、1つのマシンで十分なデータがある場合（1つのマシンでは約100万エントリのようです）ArrayListとLinkedListは現在宣伝されているように機能します。しかし、21世紀初頭に適用されるいくつかの細かい点があります。

現代のコンピュータ技術は、私のテストによって、アレイに膨大なエッジを与えるために現代的なものです。アレイの要素をシフトさせて緊張速度でコピーすることができます。結果として、アレイとArrayListは、ほとんどの実用的な状況では、挿入と削除に関するLinkedListが劇的に伸びていることがよくあります。言い換えれば、ArrayListはそれ自身のゲームでLinkedListをビートします。

ArrayListの下側は、削除後にメモリ容量に掛かる傾向があります。

アレイとアレイリストのより大きな下側は、それらがフリーメモリをフラグメント化し、ガベージコレクタを過労しています。 ArrayListが展開されると、新しい大きさの配列を作成し、古い配列を新しいものにコピーし、古いものを解放します。メモリは、次の割り当てに十分な大きさではないフリーメモリの大きな連続的なチャンクを埋めます。最終的にその割り当てに適したスペースはありません。メモリの90％が無料であっても、個々の作品は仕事をするのに十分な大きさではありません。 GCは、物事を動かすために不思議に働きますが、スペースを並べ替えるのに時間がかかりすぎると、それはOutofMemoryExceptionをスローします。それがあきらめない場合は、プログラムの方法を遅くすることができます。

それの最悪の事態はこの問題を予測するのが難しいかもしれません。あなたのプログラムは大丈夫です。その後、警告なしで、もう少しメモリが利用可能な場合は、遅く、または停止します。

LinkedListはメモリの小さな、卑劣なビットを使用し、GCが大好きです。それはあなたの利用可能なメモリの99％を使っているときそれはまだ素晴らしいです。

SO一般的に、それらの内容が削除されたほとんどのデータセットのセットの配列リストは、または作成と成長を厳しく管理している場合に使用します。 （たとえば、メモリの90％を使用してプログラムの持ち込みなしで使用する1つのArrayListを作成する1つのArrayListの作成は大丈夫です。メモリの10％を使用するArrayListインスタンスを継続的に作成して解放することはあなたを殺します。 （またはランダムなアクセスが必要な場合は、ある種の地図）。あなたが非常に大きなコレクションを持っている（10万人以上の要素を超えて）、GCについての懸念、そしてたくさんの挿入と削除を計画し、ランダムアクセスなしで、いくつかのベンチマークを実行して最速のものを見るためにいくつかのベンチマークを実行してください。

の ArrayList クラスはラッパークラスの配列になります。が含まれる内部配列の型になります。

public ArrayList<T> {
    private Object[] array;
    private int size;
}

A LinkedList であるラッパークラスのためのリンク先のリスト内のノードの管理データです。

public LinkedList<T> {
    class Node<T> {
        T data;
        Node next;
        Node prev;
    }
    private Node<T> first;
    private Node<T> last;
    private int size;
}

次に、現在のコードを使ってどのように、クラスの場合ではなく、実際の実装です。これらの実施がってしまうの更なる解析:

ArrayListによLinkedListればランダムにアクセスす。と思いランダムアクセスの手段"give me n番目の要素"なぜArrayListはが早い？

アクセス時間のためのArrayList:O(1)です。アクセス時間のためのLinkedList:O(n)

配列アクセスできる任意の要素を使用 array[index], がリンクされたリスト内のすり抜けてすべてのリストから first までの要素があります。

LinkedListによArrayListて削除します。理解しています。ArrayListの鈍化以降、内部バックアップ配列が必要再配分.

削除の時間をArrayList:アクセス時間+O(n)削除の時間をLinkedList:アクセス時間+O(1)です。

のArrayListらなければならなすべての要素から array[index] へ array[index-1] これらの項目を削除。のLinkedListはナビゲートでアイテムを消去するノードによるデカップリングでクリックします。

LinkedListによArrayListて削除します。理解しています。ArrayListの鈍化以降、内部バックアップ配列が必要再配分.

挿入時間ArrayList:O(n)挿入時間LinkedList:O(1)です。

そのArrayListきにはO(n)?で挿入する場合は、新しい要素の配列は、新しい配列を作成しますサイズを計算できる新しいサイズ数式のように2※サイズは3*サイズ/2).のLinkedListだけで新しいノードにします。

この分析はJavaでの他のプログラミング言語のようにC、C++、C#.

詳細情報はこちら

remove（）と挿入（）の両方に、ArrayListsとLinkedListの両方のo（n）の実行時効率があります。しかし、線形処理時間の背後にある理由は、2つの非常に異なる理由から来ています：

o（1）の要素に取得しますが、実際には、次の要素を変更する必要があるため、実際には挿入または挿入を行います。

LinkedListでは、所望のインデックスに到達するまで、最初の要素に実際に取得するようにo（n）が必要です。削除または挿入が一定されたら、remove（）の参照（）および2参照（）の参照（）の参照（）の参照（）。

2つのうちどれが挿入と除去が速くなるのが速くなります。私たちが最初に近い場合、LinkedListは比較的少数の要素を通過しなければならないので、より速くなります。最後に近い場合、ArrayListは常にそこに着くので、それに続くいくつかの残りの要素を変更する必要があるため、ArrayListが速くなります。

ボーナス：これら2つのメソッドをアレイリストのための2つの方法で作成する方法はありませんが、実際にはLinkedListでこれを行う方法です。私たちは私たちが私たちの方法で要素を削除して挿入するリスト全体を通過したいとしましょう。通常、LinkedListを使用して各要素の最初から始めます。現在の要素を「保存」しています。イテレータの助けを借りて、LinkedListで作業するときは、remove（）とinsert（）の効率が得られます。唯一のパフォーマンス上の利点を実現するのリンクリストが常に優れている場所に注意しています。

arraylist

  • ArrayListは、頻繁な操作が検索操作である場合に最適です。
  • ArrayListは、中央の挿入と削除が内部でいくつかのシフト操作が実行されているため、最悪の選択です。
  • ArrayList要素の連続メモリ位置に格納されます。したがって検索操作は簡単になります。

    リンクリスト： -

    • LinkedListは、頻繁な操作が中央の挿入と削除の場合、最良の選択です。
    • LinkedListは最悪の選択です。頻繁な操作は検索操作です。
    • LinkedListでは、要素は連続したメモリ位置に格納されず、検索操作は複雑になります。

      あなたの質問に今やってくる： -

      1）ArrayListはインデックスに従ってデータを保存し、ArrayListへのランダムな検索の機能を提供するマーカーインタフェースであるが、LinkedListはRandomAccessインタフェースを実装していない。

      2 linkedListの基礎となるデータ構造は2倍にリンクされていますので、登録リストがLinkedListで挿入と削除はLinkedListで非常に簡単です。 （内部的に複数のシフト操作が実行されているため、中央の操作が挿入と削除の場合はお勧めできません）。
      ソース

1：ArrayListはフードの下の配列を使用します。ArrayListオブジェクトのメンバーへのアクセスは、インデックスがバッキング配列の範囲内にあると仮定して、提供されたインデックスの配列にアクセスするのと同じくらい簡単です。LinkedListは、そのメンバーを挿入するために繰り返す必要があります。これは、LinkedListのo（n）です。

linkedList内の

要素はその前後の要素への参照を持ちます。ArrayListでは、データ構造は単なる配列です。

  1. LinkedListはn個の要素を取得するためにn個の要素を繰り返す必要があります。ArrayListは、バッキングアレイの要素Nを返すだけです。

  2. バッキングアレイは、削除された要素を移動させて空のスペースを埋めるために移動する必要がある後に、新しいサイズとアレイがコピーされた配列またはすべての要素を再割り当てする必要があります。LinkedListは、削除された要素以降の要素の中に削除された後、除去された要素の要素の前の要素上の次の参照の後に、要素上の次の参照を除去された要素の前後の要素に設定する必要があります。説明するのが長いが、やるのが速い。

  3. ここでの削除と同じ理由。

arraylist ：ArrayListは配列のような構造をしています、それはすべての要素を直接参照しています。そのため、Rendom AccessはArrayListで高速です。

linkedList ：NTHを取得するためのLinkedListでは、リスト全体を通過する必要があります.ArrayListと比較して時間がかかります。すべての要素には以前の＆nest要素へのリンクがあるため、削除は速いです。

arraylist： ArrayListクラスは抽象リストを拡張し、リストインタフェースとRandomAccess（マーカーインタフェース）を実装します。ArrayListは必要に応じて成長できる動的配列をサポートしています。それは私達に要素上の最初の反復を与えます。

linkedList： LinkedListは、要素が互いに二重リンクされていることを除いて、ArrayListのように、インデックス位置によって順序付けされています。このリンケージは、最初または終了から追加して削除するために、新しいメソッド（リストインタフェースから取得するものを超えて）新しいメソッドを提供します。これにより、スタックまたはキューを実装するための簡単な選択です。LinkedListがArrayList、よりもゆっくり繰り返すことができることに注意してください。 Java 5以降、LinkedListクラスはJavaを実装するように拡張されました。util.queueインターフェース。そのように、それは現在、一般的なキューメソッドをサポートしています.peek（）、poll（）、およびoffer（）。

パフォーマンスの違いについて、彼女に追加の情報を追加したいです。

ArrayListの実装がObject[]によってバックアップされているという事実がすでに、ランダムアクセスをサポートし、動的なサイズ変更とLinkedListの実装はそれをナビゲートするためにヘッドとテールへの参照を使用します。ランダムなアクセス機能はありませんが、動的なサイズ変更もサポートしています。

最初のことは、ArrayListを使用して、すぐにインデックスにアクセスすることができますが、LinkedListを使用すると、オブジェクトチェーンを繰り返します。

第2に、ArrayListへの挿入は一般的に遅くなります。新しい大きな配列を作成し、元のものからデータをコピーする必要があります。

しかし興味深いものは、 の登録のすべての挿入物に合わせて、アレイコピー操作を扱うことはありません。 LinkedListはそのポインタに対処しなければならないため、LinkedListとさらに高速になりますが、巨大なArrayListは指定されたインデックスで値を設定します。

画像の説明が入力されています

詳細 ArrayListとLinkedListの違い。

同一（同じ実装されたインターフィースリスト - 非スレッドセーフ）でさえ、それらは追加/削除および検索時間およびメモリの消費時間の性能に関して異なる結果を与える（LinkedListを消費する）。

Performance O（1）で非常に挿入/削除を使用する場合は、LinkedListを使用できます。 Performance O（1）で直接アクセス操作を使用する場合は、ArrayListを使用できます。

このコードはこれらのコメントを明確にすることができ、あなたはパフォーマンス結果を理解しようとすることができます。（ボイラープレートコードで申し訳ありません） 

public class Test {

    private static Random rnd;


    static {
        rnd = new Random();
    }


    static List<String> testArrayList;
    static List<String> testLinkedList;
    public static final int COUNT_OBJ = 2000000;

    public static void main(String[] args) {
        testArrayList = new ArrayList<>();
        testLinkedList = new LinkedList<>();

        insertSomeDummyData(testLinkedList);
        insertSomeDummyData(testArrayList);

        checkInsertionPerformance(testLinkedList);  //O(1)
        checkInsertionPerformance(testArrayList);   //O(1) -> O(n)

        checkPerformanceForFinding(testArrayList);  // O(1)
        checkPerformanceForFinding(testLinkedList); // O(n)

    }


    public static void insertSomeDummyData(List<String> list) {
        for (int i = COUNT_OBJ; i-- > 0; ) {
            list.add(new String("" + i));
        }
    }

    public static void checkInsertionPerformance(List<String> list) {

        long startTime, finishedTime;
        startTime = System.currentTimeMillis();
        int rndIndex;
        for (int i = 200; i-- > 0; ) {
            rndIndex = rnd.nextInt(100000);
            list.add(rndIndex, "test");
        }
        finishedTime = System.currentTimeMillis();
        System.out.println(String.format("%s time passed at insertion:%d", list.getClass().getSimpleName(), (finishedTime - startTime)));
    }

    public static void checkPerformanceForFinding(List<String> list) {

        long startTime, finishedTime;
        startTime = System.currentTimeMillis();
        int rndIndex;
        for (int i = 200; i-- > 0; ) {
            rndIndex = rnd.nextInt(100000);
            list.get(rndIndex);
        }
        finishedTime = System.currentTimeMillis();
        System.out.println(String.format("%s time passed at searching:%d", list.getClass().getSimpleName(), (finishedTime - startTime)));

    }

}
.

ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top