キャッシュの不自由なクイックソートはどのようにですか？

Question

Burst sort紙の著者は、クイックソートは非常にキャッシュ効率的なソートアルゴリズムではないと主張しています。著者は

を述べたようしかし、クイックソートの欠点のいくつかはまだpresent.Eachあり、それは同じで にピボットpartition.Each列が毎回文字に再アクセスされるまで文字は、複数回検査されます が検査され、最初の分割後にこれらのアクセスは実質的にランダムに になります。大量の文字列の場合、キャッシュの割合は、高い可能性があります（ ）。

は、私はまた、クイックソートを言うと、ソートキャッシュ紛失アルゴリズムが、Wikipediaやクイックソートは非常にキャッシュが効率的であることを主張している few paperマージ pptを見つけました。

クイックソートでは整数データの強制ミスと別にキャッシュミスが発生するケースを理解することはできません。

Answer 1

あなたが引用した文章は、主に文字列を並べ替えるときの問題について話しています。 quicksort中の文字列の配列がポインタとして配列として格納されている場合（これは基本的に簡単な方法です）、quicksortの最初のパスのあと、配列の近くの位置に格納されているポインタがメモリを指し示す可能性があります文字列の元の配列が連続したメモリに割り当てられていても、離れた位置に格納されます。文字列の並べ替えは特別な問題として扱うことができ、そのための特殊なアルゴリズムはキャッシュ効率が向上する可能性があります。

代わりに整数の配列を並べ替えるのであれば、実際にはクイックソート中に配列内のデータを比較して交換しているので、配列の近くの場所にアクセスするとキャッシュの利点が得られます。この場合、私の理解は、あなたがウィキペディアなどで見つけたものと同じです。つまり、quicksortはかなり効率的です。基本的にこれは、クイックソートの各パスが非常にローカルな方法で配列のその部分を処理するためです。