java - 連続していないコンテナのイテレータの方が速いのはなぜですか?

Question

スタック オーバーフローに関するこの別のトピック「従来の for ループと Java のイテレータ」では、インデックスの使用とイテレータの使用のパフォーマンスの違いについて説明しています。一番上の回答は、LinkedList.

これはキャッシングと関係があると思います。もしそうなら、イテレータはこの問題をどのように回避しますか? キャッシュ ミスとは何の関係もないのなら、連続していないコンテナのイテレータがこれほど高速になるのはなぜでしょうか?

Answer 1

リンクされたリストの違いは、一定の要因ではありません.O（1）またはO（N）を取る「ステップ」の違いです。(したがって、リストが大きいほど、差は大きくなります。)

イテレータは、「次のステップに進む」ために必要な状態を保持します。リンクされたリストの場合、次のステップを実行するということは、あるノードから次のノードへの参照をたどることを意味します... 一方、インデックスによって要素にアクセスすることは、先頭から開始して同じ「次へ移動」ステップを何度も実行することを意味します。

これを と比較するとArrayList、イテレータは現在のインデックスを記憶するだけでよく、「ランダム アクセス」と「シーケンシャル」アクセスの両方で、配列の正しい要素に直接移動するだけです。

したがって、それ自体は実際にはキャッシュではなく、状態を保持しています。イテレータがインデックスによるアクセスよりも高速かどうかは、インデックスによるアクセスが何をしなければならないかによって異なります。の場合、ArrayList安いです。の場合はそうではありLinkedListません。