式キャッシュの忘却の意味を理解しています。しかし、キャッシュのサイズを知らなくても、キャッシュを最適に使用できるデータ構造を設計する方法について簡単な説明があるかどうか疑問に思いました。
できれば（簡単な）例を挙げて、そのような説明をお願いします。
2 に答える
7
クイックソートのように馴染みのあるアルゴリズムでさえ、キャッシュを気にしない（しかし最適ではない）。配列をパーティション化してから、パーティションの両側で再帰することで機能することを思い出してください。最終的には、キャッシュに収まるサブアレイで動作するため、そのサブアレイが終了して別のサブアレイに移動するまで、キャッシュミスは発生しません。それが私たちが探している物件です。
これを挿入ソートと比較してください。挿入ソートは（専門用語を使用すると）常にあらゆる場所で飛躍します。したがって、挿入ソートでO（n ^ 2）アイテムを移動する必要があることは別として、大きな配列で使用するとキャッシュが大幅に失われます。
ただし、クイックソートは最適からは程遠いものです。個々のパーティションフェーズは分割および再帰しません。キャッシュをかき回すメモリを長時間シーケンシャルに実行します。サブアレイのサイズが小さくなり、勝ち始める前に、これが数回発生する可能性があるため、キャッシュミスの数を最小限に抑えていません。
于 2010-09-22T21:52:36.337 に答える
3
主な直感は、作業するデータセットを再帰的に分割すると、ある時点で（通常はかなり速く）、1）キャッシュに収まり、2）キャッシュの少なくとも半分を埋めるサイズに達することです（各分割を想定）データセットの（少なくとも約）半分です）。
于 2010-09-22T20:49:11.630 に答える