sorting - パーティション関数は、参照の局所性をすばやくソートしますか?

Question

パーティション関数は、その参照の局所性をすばやくソートしますか? もしそうなら、どのように？

マージソートやヒープソートなどの他のアルゴリズムと比較して、参照の局所性を与えるクイックソートには何がありますか?

私もそれを読みました

「クイックソートのパーティショニングステップは、前後にある連続した配列要素にアクセスするため、通常、優れた局所性を持っています」.

よくわからなかった ？

Answer 1

一般に、コードが行うメモリアクセスがメモリの少数の領域の周りに順番に配置される傾向がある場合、コードの参照の局所性は良好です。たとえば、配列の線形検索では、すべての要素がメモリ内で隣接して表示されるため、参照の局所性が高くなりますが、連結リストの線形検索では、連結リストのセルがメモリ内で連続して出現するとは限らないため、局所性が低くなります。

クイックソートを見てみましょう。クイックソート アルゴリズムの「要」は、要素がピボットの周りに再配置される分割ステップです。分割アルゴリズムを実装するための戦略はいくつかありますが、そのほとんどは優れた局所性を備えています。一般的なアプローチの 1 つは、配列の端から中央に向かって内側にスキャンし、要素が相対的にずれている場合はいつでも要素を交換することによって機能します。このアルゴリズムは、ほとんどの配列アクセスを 2 つの領域 (配列の末尾) に限定し、要素に順次アクセスするため、優れた局所性を備えています。

別の分割戦略は、配列の左から右にスキャンし、小さい値と大きい値を保持する領域を区切る 2 つのポインターを格納することによって機能します。ここでも、配列へのアクセスはすべてシーケンシャルであるため、局所性は非常に優れています。

さて、それをヒープソートと対比してください。ヒープソートでは、ヒープ操作で、ある位置にある要素と、その要素のインデックスの 2 倍または半分のインデックスを持つ要素を繰り返し比較する必要があります。これは、配列アクセスがシーケンシャルではなく配列全体に分散していることを意味するため、全体的な局所性が大幅に低下します。

Mergesort は実際には、マージ ステップがどのように機能するかにより、ある程度適切な局所性を持っています。ただし、入力配列と同じ大きさの補助バッファー配列を維持するため、余分なメモリのコストを支払う必要があり、そのアクセスはクイックソートのアクセスよりも少し散らばっています。