どの list<Object> 実装が、書き込み、読み取り、破棄の 1 つのパスで最も高速になるでしょうか?

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

  •  02-07-2019
  •  | 
  •  

質問

リストが一度に 1 要素ずつ作成され、その後で一度に 1 要素ずつ読み取られるシナリオでの (Java での) 最速のリスト実装は何ですか?読み取りはイテレータを使用して行われ、リストは破棄されます。
ArrayList の Big O 表記は get が O(1)、add が O(1) であるのに対し、LinkedList は get が O(n)、add が O(1) であることはわかっています。イテレータは同じ Big O 表記法で動作しますか?

役に立ちましたか？

解決

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

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

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

考慮すべきもう 1 つの点は、時空のトレードオフが明確ではないということです。各 Java オブジェクトにはかなりのオーバーヘッドがあります。ながら ArrayList 各スロットはわずか 4 バイト (64 ビット JVM では 8 バイト) なので、余剰スロットでスペースを無駄にする可能性があります。の各要素 LinkedList おそらく約 50 バイト (64 ビット JVM ではおそらく 100 バイト) です。したがって、かなりの数の無駄なスロットが必要になります。 ArrayList の前に LinkedList 実際、推定されるスペース上の利点を勝ち取ります。参照の場所も要因です。 ArrayList そこでも好ましいです。

実際には、私はほぼ常に使用します ArrayList.

他のヒント

最初の考え:

  • リストが不要になるようにコードをリファクタリングします。
  • データをスカラー データ型に単純化し、次を使用します。 int[]
  • または、手持ちのオブジェクトの配列を使用することもできます。 物体[] - ジョン・ガードナー
  • リストをフルサイズに初期化します。 新しい配列リスト(123);

もちろん、他の人も言っているように、パフォーマンス テストを行って、新しいソリューションが改善されていることを証明してください。

リンク リストの反復処理は要素ごとに O(1) です。

各オプションの Big O ランタイムは同じです。おそらく ArrayList はメモリの局所性が向上するため高速になるでしょうが、確実に知るには測定する必要があります。コードが最も明確になるものを選択してください。

のインスタンスを反復処理することに注意してください。 LinkedList 単純に実行すると O(n^2) になる可能性があります。具体的には：

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

これは、リストを次の位置までたどる必要があるため、効率の点でまったくひどいものです。 i 二度 反復ごとに。使用する場合 LinkedList, 、必ずいずれかを使用してください。 Iterator または Java 5 の強化版 for-ループ：

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

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

上記の面倒な作業をすべて回避するには、次のようにしてください。 ArrayList. 。これは常に最良の選択であるとは限りません (特にスペース効率の観点から) が、通常は安全な選択です。

ベンチマークを行うことをお勧めします。API を読むのは別のことですが、実際に試してみるまでは学術的なものになります。

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

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

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

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

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

という新しい List 実装があります。 接着剤リスト これは、すべての従来の List 実装よりも高速です。

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

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

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

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