125

ADTリストのJavaドキュメントを読むと次のようになっています。

Listインターフェイスは、リスト要素への位置（インデックス付き）アクセスのための4つのメソッドを提供します。リスト（Java配列など）はゼロベースです。これらの操作は、一部の実装（たとえば、LinkedListクラス）のインデックス値に比例して時間内に実行される場合があることに注意してください。したがって、呼び出し元が実装を知らない場合は、通常、リスト内の要素を反復処理する方が、リストを介してインデックスを作成するよりも望ましい方法です。

これは正確にはどういう意味ですか？引き出された結論がわかりません。

4

5 に答える 5

210

リンクリストでは、各要素に次の要素へのポインタがあります。

head -> item1 -> item2 -> item3 -> etc.

にアクセスするitem3には、直接ジャンプできないため、アイテム3に到達するまで、頭からすべてのノードを歩く必要があることがはっきりとわかります。

したがって、各要素の値を出力したい場合は、次のように記述します。

for(int i = 0; i < 4; i++) {
    System.out.println(list.get(i));
}

何が起こるかこれは：

head -> print head
head -> item1 -> print item1
head -> item1 -> item2 -> print item2
head -> item1 -> item2 -> item3 print item3

これは、インデックスを作成するたびにリストの最初から再開され、すべてのアイテムを通過するため、ひどく非効率的です。これは、あなたの複雑さが事実上O(N^2)リストをトラバースすることであることを意味します！

代わりに私がこれをした場合：

for(String s: list) {
    System.out.println(s);
}

次に何が起こるかはこれです：

head -> print head -> item1 -> print item1 -> item2 -> print item2 etc.

すべてを1回の走査で、つまりO(N)。

さて、他の実装に行きましょう。その実装はList単純ArrayListな配列に支えられています。その場合、配列は連続しているため、上記のトラバーサルは両方とも同等であり、任意の位置にランダムにジャンプできます。

于 2012-05-07T17:44:35.490 に答える
35

答えはここに暗示されています：

これらの操作は、一部の実装（LinkedListクラスなど）のインデックス値に比例して時間内に実行される場合があることに注意してください。

リンクリストには固有のインデックスはありません。呼び出す.get(x)には、リストの実装で最初のエントリを見つけて.next()x-1回呼び出す必要があります（O（n）または線形時間アクセスの場合）。配列に基づくリストはbackingarray[x]、O（1）または定数時間でインデックスを作成できます。

JavaDoc forLinkedListを見ると、コメントが表示されます。

すべての操作は、二重リンクリストで期待できるとおりに実行されます。リストにインデックスを付ける操作は、リストの最初または最後のどちらか、指定されたインデックスに近い方からトラバースします。

一方、JavaDocforにArrayListは対応するものがあります

Listインターフェースのサイズ変更可能な配列の実装。すべてのオプションのリスト操作を実装し、nullを含むすべての要素を許可します。このクラスは、Listインターフェイスの実装に加えて、リストを格納するために内部的に使用される配列のサイズを操作するためのメソッドを提供します。（このクラスは、同期されていないことを除いて、Vectorとほぼ同等です。）

、、、、、、および操作は一定時間で実行さsizeれisEmptyますget。追加操作は、償却された一定時間で実行されます。つまり、n個の要素を追加するにはO（n）時間が必要です。他のすべての操作は線形時間で実行されます（大まかに言えば）。定数係数は、実装の場合と比較して低くなっています。setiteratorlistIteratorLinkedList

「JavaCollectionsFrameworkのBig-OSummary」というタイトルの関連する質問には、このリソース「JavaCollectionsJDK6」を指す回答があります。

于 2012-05-07T17:41:16.113 に答える
8

のようなルックアップのオフセットを使用してリストを反復処理することは、画家のアルゴリズムであるShlemielにi類似しています。

シュレミエルは通りの画家としての仕事に就き、道路の真ん中に点線を描きます。初日、彼はペンキの缶を道路に持ち出し、300ヤードの道路を終えました。「それはかなりいいです！」上司は「あなたは速い労働者だ！」と言います。そして彼にコペイカを支払います。

翌日、シュレミエルは150ヤードしか完成しません。「まあ、それは昨日ほど良くはありませんが、あなたはまだ速い労働者です。150ヤードは立派です」と彼にコペイカを支払います。

翌日、シュレミエルは道路の30ヤードをペイントします。「たった30！」上司が叫ぶ。「それは受け入れられない！初日にあなたはその10倍の仕事をした！何が起こっているのか？」

「私はそれを助けることはできません」とシュレミエルは言います。「毎日、ペンキ缶からどんどん遠ざかっていきます！」

ソース。

この小さな話は、内部で何が起こっているのか、そしてなぜそれがそれほど非効率的であるのかを理解しやすくするかもしれません。

于 2012-05-09T03:26:16.230 に答える
7

受け入れられた答えは間違いなく正しいですが、私は小さな欠陥を指摘するかもしれません。チューダーの引用：

次に、Listのもう1つの実装であるArrayListに移動します。この実装は、単純な配列に支えられています。その場合、配列は連続しているため、上記のトラバーサルは両方とも同等であり、任意の位置へのランダムなジャンプが可能です。

これは完全には真実ではありません。真実は、それです

ArrayListを使用すると、手書きのカウントループが約3倍高速になります

出典：Designing for Performance、GoogleのAndroidドキュメント

手書きのループは、インデックス付きの反復を参照していることに注意してください。拡張されたforループで使用されるイテレータが原因だと思います。隣接するアレイに裏打ちされた構造では、ペナルティのパフォーマンスがわずかに低下します。また、これはVectorクラスにも当てはまるのではないかと思います。

私のルールは、可能な限り拡張forループを使用し、パフォーマンスを本当に気にする場合は、ArrayListsまたはVectorsのいずれかにのみインデックス付き反復を使用することです。ほとんどの場合、これを無視することもできます。コンパイラがバックグラウンドでこれを最適化している可能性があります。

Androidでの開発のコンテキストでは、ArrayListsの両方のトラバーサルが必ずしも同等ではないことを指摘したいだけです。ただ考えるための食べ物。

于 2012-05-08T18:54:50.533 に答える
4

LinkedList実装のi番目の要素を見つけるには、i番目までのすべての要素を調べます。

それで

for(int i = 0; i < list.length ; i++ ) {
    Object something = list.get(i); //Slow for LinkedList
}
于 2012-05-07T17:41:55.723 に答える