クイックソートはどのようにキャッシュに関連していますか？

Question

私はまた、クイックソートのシーケンシャルおよびローカライズされたメモリ参照がキャッシュ

でうまく動作

ウィキに言ったような、多くの場所は、それがキャッシュ関連のものにフィットするので、クイックソートが良いと言って見てきましたhttp://en.wikipedia.org/wiki/Quicksort

誰も私にこの主張についていくつかの洞察を与えることができますか？ quicksortはどのようにキャッシュに関係していますか？通常、この文のキャッシュは何ですか？なぜクイックソートがキャッシュに適しているのですか？キャッシュに入って何

おかげ

Answer 1

quicksortは、配列を変更します - [マージソートとは異なります。それに対して別の配列を作成する]。したがって、それはlocality of referenceの原則を適用します。

キャッシュは、実際にメモリから最初にアクセスする必要があるだけなので、メモリ内の同じ場所に複数回アクセスすることでメリットがあります。残りのアクセスはキャッシュから取得されます。

たとえば、マージソート - あなたが作成するすべてのアクセサリアレイがRAMに再度アクセスしているので、より多くのメモリ[RAM]アクセスが必要です。

ツリーの2つの連続したアクセスがお互いに近くなることはないため、ツリーはさらに悪化します。 [キャッシュはブロックで塗りつぶされているため、シーケンシャルアクセスの場合、ブロックの最初のバイトだけが「ミス」で、他は「ヒット」です。

Answer 2

は、あなたはすぐにあなたが現在要求しているものに基づいて使用しようとしているもので、アルゴリズムはかなりの推測によって決定されます。これは、通常、配列のようにお互いに近いメモリブロックを意味します。

繰り返しを数回実行すると、quicksortは完全にキャッシュに収まるブロックで動作し、パフォーマンスが大幅に向上します。 （ソートを選択すると、大部分の操作で離れているメモリ位置にアクセスしている可能性があります）。

Answer 3

クイックソートは、インプレースソートアルゴリズムです。スワップを使用して要素をピボットの左右に移動します。スワップが発生するたびに、キャッシュラインがロードされ、後続のスワップが同じキャッシュラインから発生する可能性が高い。