java - どのリスト

Question

What is the fastest list implementation (in java) in a scenario where the list will be created one element at a time then at a later point be read one element at a time? The reads will be done with an iterator and then the list will then be destroyed.
I know that the Big O notation for get is O(1) and add is O(1) for an ArrayList, while LinkedList is O(n) for get and O(1) for add. Does the iterator behave with the same Big O notation?

score 29 · Accepted Answer

各リストの最大サイズを事前に知っているかどうかに大きく依存します。

その場合は、ArrayList;を使用します。確かに速くなります。

それ以外の場合は、おそらくプロファイルを作成する必要があります。へのアクセスArrayListは O(1) ですが、動的なサイズ変更のため、作成は簡単ではありません。

考慮すべきもう 1 つの点は、時空間のトレードオフが明確ではないということです。各 Java オブジェクトにはかなりのオーバーヘッドがあります。余剰スロットでいくらかのスペースを浪費するArrayList場合がありますが、各スロットはわずか 4 バイト (または 64 ビット JVM では 8 バイト) です。a の各要素は、LinkedListおそらく約 50 バイト (64 ビット JVM ではおそらく 100 バイト) です。そのため、が実際に想定されるスペースの優位性を獲得するArrayList前に、かなりの数の無駄なスロットをに持たなければなりません。LinkedList参照の局所性も要因であり、ArrayListそこでも望ましいです。

実際には、ほとんどの場合、を使用しますArrayList。

score 10 · Accepted Answer

First Thoughts:

Refactor your code to not need the list.
Simplify the data down to a scalar data type, then use: int[]
Or even just use an array of whatever object you have: Object[] - John Gardner
Initialize the list to the full size: new ArrayList(123);

Of course, as everyone else is mentioning, do performance testing, prove your new solution is an improvement.

score 7 · Accepted Answer

Iterating through a linked list is O(1) per element.

The Big O runtime for each option is the same. Probably the ArrayList will be faster because of better memory locality, but you'd have to measure it to know for sure. Pick whatever makes the code clearest.

score 7 · Accepted Answer

素朴に行われた場合、インスタンスの反復処理はLinkedListO(n^2) になる可能性があることに注意してください。具体的には：

List<Object> list = new LinkedList<Object>();
for (int i = 0; i < list.size(); i++) {
    list.get(i);
}

これは、反復ごとにリストを最大i 2 回トラバースする必要があるため、効率の点で絶対に恐ろしいことです。を使用する場合は、または Java 5 の拡張ループLinkedListを必ず使用してください。Iteratorfor

for (Object o : list) {
    // ...
}

上記のコードは O(n) です。これは、リストがステートフルインプレースで走査されるためです。

上記の手間をすべて回避するには、ArrayList. これは常に最良の選択であるとは限りませんが (特にスペース効率の点で)、通常は安全な方法です。

score 4 · Accepted Answer

すべての従来の List 実装よりも高速なGlueListと呼ばれる新しい List 実装があります。

免責事項: 私はこのライブラリの作成者です

score 3 · Accepted Answer

ほぼ確実にArrayListが必要です。追加と読み取りはどちらも、ドキュメントで指定されている「償却定数時間」（つまり、O（1））です（リストのサイズを大きくする必要がある場合でも、これは当てはまります。http：//java.sunを参照してください。 .com / j2se / 1.5.0 / docs / api / java / util / ArrayList.html）。保存するオブジェクトの数がおおよそわかっている場合は、ArrayListのサイズの増加も排除されます。

リンクリストの最後に追加されるのはO（1）ですが、定数乗数はArrayListよりも大きくなります（通常は毎回ノードオブジェクトを作成するため）。イテレータを使用している場合、読み取りは実質的にArrayListと同じです。

正当な理由がない限り、常に可能な限り単純な構造を使用することをお勧めします。ここではそのような理由はありません。

ArrayListのドキュメントからの正確な引用は、次のとおりです。「add操作は償却された一定時間で実行されます。つまり、n個の要素を追加するにはO（n）時間が必要です。他のすべての操作は線形時間で実行されます（大まかに言えば）。定数係数LinkedList実装の場合と比較して低いです。」

score 2 · Accepted Answer

ベンチマークすることをお勧めします。API を読むのは 1 つのことですが、自分で試してみるまでは学術的です。

テストするのはかなり簡単なはずです。意味のある操作を行っていることを確認してください。そうしないと、ホットスポットがあなたを出し抜いて、すべてを NO-OP に最適化します :)

score -1 · Accepted Answer

ArrayList や HashMap などの非決定論的な動作を伴うデータ構造の使用は避けるべきだと実際に考え始めたので、そのサイズを制限できる場合にのみ ArrayList を使用すると言います。無制限のリストは LinkedList を使用します。それは、私が主にほぼリアルタイムの要件を持つシステムをコーディングしているためです。

主な問題は、メモリの割り当て (追加操作でランダムに発生する可能性があります) によってもガベージコレクションが発生する可能性があり、ガベージコレクションによってターゲットを見逃す可能性があることです。割り当てが大きいほど、これが発生する可能性が高くなり、CMS コレクターを使用している場合はさらに悪化します。CMS は非圧縮であるため、通常、新しいリンクリストノード用のスペースを見つける方が、新しい 10,000 要素配列用のスペースを見つけるよりも簡単です。

コーディングへのアプローチが厳密であればあるほど、標準の JVM でリアルタイムに近づけることができます。ただし、決定論的な動作を持つデータ構造のみを選択することは、最初に実行する必要がある手順の 1 つです。

8 に答える 8

Related

Reference