16

ソートされていない配列と連結リストがあるとします。両方のデータ構造の要素を検索する場合の最悪のケースは O( n ) ですが、私の質問は次のとおりです。

キャッシュ内の空間的局所性を使用するため、配列はさらに高速になりますか、それともキャッシュは分岐局所性を使用して、リンクされたリストを任意の配列と同じくらい高速にすることができますか?

配列についての私の理解では、要素がアクセスされると、そのメモリのブロックと周囲のブロックの多くがキャッシュに取り込まれ、メモリアクセスがはるかに高速になります。

リンクされたリストについての私の理解は、リストをトラバースするために取られるパスは予測可能であるため、リストのノードがヒープ内で遠く離れている場合でも、キャッシュはそれを利用して適切なメモリブロックを保存するということです.

4

1 に答える 1