サンプルソート

以下のリストは、上述の3ステップアルゴリズムを擬似コードとして示し、アルゴリズムが原理的にどのように動作するかを示しています。^{[ 5 ]}以下では、Aはソートされていないデータ、kは後述するオーバーサンプリング係数、pはスプリッターの数です。

function sampleSort(A[1..n], k , p ) // 平均バケットサイズがしきい値を下回る場合は、例えばクイックソートに切り替える n / k < しきい値の場合、 smallSort(A)を実行します。 /* ステップ 1 */ select S = [ S 1 , ..., S ( p −1) k ] randomly from // サンプルを選択 ソートS // ソート例 [ s 0 , s 1 , ..., s p −1 , s p ] <- [-∞, S k , S 2 k , ..., S ( p −1) k , ∞] // スプリッタを選択 /* ステップ 2 */ Aの各aについて、 s j −1 < a <= s jを満たすjを 見つけ、 a をバケットb jに 入れる。 /* ステップ 3 と連結 */ return concatenate(sampleSort( b 1 ), ..., sampleSort( b k ))

擬似コードは、元の Frazer と McKellar のアルゴリズムとは異なります。^{[ 3 ]}擬似コードでは、samplesort が再帰的に呼び出されます。Frazer と McKellar は samplesort を一度だけ呼び出し、以降のすべての反復でquicksort を使用しました。

並列化された実装の複雑さは、ビッグオー記法で表され、${\displaystyle p}$プロセッサ:

スプリッターを見つけてください。

${\displaystyle O\left({\frac {n}{p}}+\log(p)\right)}$

バケットに送信する。

${\displaystyle O(p)}$すべてのノードを読み取る

${\displaystyle O(\log(p))}$放送用

${\displaystyle O\left({\frac {n}{p}}\log(p)\right)}$すべてのキーに対するバイナリーサーチ

${\displaystyle O\left({\frac {n}{p}}\right)}$キーをバケットに送信する

ソートバケット。

${\displaystyle O\left(c\left({\frac {n}{p}}\right)\right)}$どこ${\displaystyle c(n)}$これは、基となる逐次ソート方法の複雑さです。^{[ 1 ]}多くの場合${\displaystyle c(n)=n\log(n)}$。

このアルゴリズムによって実行される比較回数は、情報理論上の最適値に近づく。${\displaystyle \log _{2}(n!)}$大きな入力シーケンスの場合、このアルゴリズムはクイックソートよりも比較回数が15%少ない。フレイザーとマッケラーが行った実験では、クイックソートよりも15%少ない比較回数で済むことが示された。

オーバーサンプリング比率は、スプリッターを決定する前に、サンプルとして取得するデータ要素の数を決定します。目標は、データの分布を適切に表現することです。データ値が広く分布していて、重複値が少ない場合は、小さなサンプリング比率で十分です。分布に重複が多い場合は、より大きなオーバーサンプリング比率が必要になります。理想的な場合、ステップ2の後、各バケットには${\displaystyle n/p}$要素。この場合、すべてのバケットのサイズが同じであるため、どのバケットも他のバケットよりもソートに時間がかかることはありません。

引っ張った後${\displaystyle k}$必要以上に多くのサンプルが処理され、サンプルはソートされます。その後、バケット境界として使用されるスプリッターは、位置にあるサンプルです。${\displaystyle k,2k,3k,\dots ,(p-1)k}$サンプル配列の（${\displaystyle -\infty }$そして${\displaystyle \infty }$（それぞれ左端と右端のバケットの左境界と右境界として）。これは、単に選択するよりも優れたスプリッターのためのより良いヒューリスティックを提供する。${\displaystyle p}$スプリッターはランダムに動作します。

得られたサンプルサイズから、期待されるバケットサイズ、特にバケットが特定のサイズを超える確率を推定できます。以下では、オーバーサンプリング係数の場合、${\displaystyle S\in \Theta \left({\dfrac {\log n}{\epsilon ^{2}}}\right)}$どのバケツにもそれ以上のものが入らない確率${\displaystyle (1+\epsilon )\cdot {\dfrac {n}{p}}}$要素はより大きい${\displaystyle 1-{\dfrac {1}{n}}}$。

これを示すために${\displaystyle \langle e_{1},\dots ,e_{n}\rangle }$入力はソートされたシーケンスとして扱われます。プロセッサがそれ以上のものを処理するためには${\displaystyle (1+\epsilon )\cdot n/p}$要素、入力の長さの部分列が存在する必要がある${\displaystyle (1+\epsilon )\cdot n/p}$そのうち最大S個のサンプルが選ばれる。これらのケースは確率を構成する。${\displaystyle P_{\text{fail}}}$これは、次の確率変数として表すことができます。 $${\displaystyle X_{i}:={\begin{cases}1,&{\text{if }}s_{i}\in \left\langle e_{j},\dots ,e_{j}+(1+\epsilon )\cdot {\dfrac {n}{p}}\right\rangle \\0,&{\text{otherwise}}\end{cases}},X:=\sum _{i=0}^{S\cdot p-1}X_{i}}$$

期待値については${\displaystyle X_{i}}$保持する: $${\displaystyle E(X_{i})=P(X_{i}=1)={\dfrac {1+\epsilon }{p}}}$$

これは推定に使用されます${\displaystyle P_{\text{fail}}}$: $${\displaystyle P(X<S)\approx P(X<(1-\epsilon ^{2})S)=P(X<(1-\epsilon )E(X))}$$

チェルノフ限界を用いると、次のことが示される。 $${\displaystyle P_{\text{fail}}=n\cdot P(X<S)\leq n\cdot \exp \left({\dfrac {-\epsilon ^{2}\cdot S}{2}}\right)\leq n\cdot {\dfrac {1}{n^{2}}}{\text{ for }}S\geq {\dfrac {4}{\epsilon ^{2}}}\ln n}$$

比較ベースのソートアルゴリズムでは、比較演算がパフォーマンス上最も重要な部分です。Samplesortでは、これは各要素のバケットを決定することに相当します。これには${\displaystyle \log k}$各要素にかかる時間。

スーパースカラーサンプルソートは、配列tに暗黙的に格納されるバランスのとれた探索木を使用します。ルートは 0 に格納され、左の次の要素は${\displaystyle t_{i}}$保存場所${\displaystyle t_{2i}}$そして、正しい後継者は次の場所に保存されます。${\displaystyle t_{2i+1}}$探索木tが与えられた場合、アルゴリズムは要素のバケット番号jを計算します。${\displaystyle a_{i}}$以下のように（${\displaystyle a_{i}>t_{j}}$（真であれば1 、そうでなければ0と評価される）：

j := 1 log 2 ( p ) を 繰り返すj := 2j + ( a > tj ) j := j − p + 1

バケット数kはコンパイル時に既知であるため、このループはコンパイラによって展開できます。比較演算は述語付き命令で実装されています。そのため、比較演算を著しく遅くする分岐予測の誤りは発生しません。

要素を効率的に分割するには、アルゴリズムはバケットのサイズを事前に知っておく必要があります。シーケンスの要素を分割して配列に格納するには、バケットのサイズを事前に知っておく必要があります。単純なアルゴリズムでは、各バケットの要素数を数えることができます。その後、要素を適切な場所に別の配列に挿入できます。この方法では、各要素のバケットを2回決定する必要があります（1回はバケット内の要素数を数えるため、もう1回は要素を挿入するため）。

比較回数の重複を避けるため、スーパースカラーサンプルソートは追加の配列を使用します。${\displaystyle o}$（オラクルと呼ばれる）は、要素の各インデックスをバケットに割り当てます。まず、アルゴリズムは、${\displaystyle o}$各要素のバケットとバケットのサイズを決定し、次に要素を決定されたバケットに配置することによって${\displaystyle o}$配列${\displaystyle o}$保管スペースにもコストがかかりますが、保管する必要があるのは${\displaystyle n\cdot \log k}$ビット単位の場合、これらのコストは入力配列のスペースに比べて小さい。

最初のステップでは、入力配列を分割します。${\displaystyle p}$同じサイズのブロックのストライプが、プロセッサごとに1つずつ割り当てられます。各プロセッサはさらに${\displaystyle k}$ブロックと同じサイズのバッファが、バケットごとに1つずつ用意されます。その後、各プロセッサは自身のストライプをスキャンし、要素を対応するバケットのバッファに移動します。バッファがいっぱいの場合、バッファの内容は先頭からプロセッサのストライプに書き込まれます。バッファに書き込む（つまりバッファがいっぱいになる）には、書き戻される要素よりも少なくともバッファサイズ分の要素をスキャンする必要があるため、常に少なくとも1つのバッファサイズの空きメモリが存在します。したがって、すべての満杯のブロックには、同じバケットの要素が含まれます。スキャン中は、各バケットのサイズが追跡されます。

まず、バケットの境界を計算するプレフィックス和演算が実行されます。ただし、このフェーズでは完全なブロックのみが移動するため、境界はブロックサイズの倍数に切り上げられ、単一のオーバーフローバッファが割り当てられます。ブロック順列を開始する前に、いくつかの空のブロックをバケットの末尾に移動する必要がある場合があります。その後、書き込みポインタが${\displaystyle w_{i}}$バケットの開始位置に設定されます${\displaystyle b_{i}}$各バケットのサブ配列と読み取りポインタ${\displaystyle r_{i}}$バケット内の最後の空でないブロックに設定されます${\displaystyle b_{i}}$各バケットに対応するサブ配列。

作業の競合を制限するため、各プロセッサには異なるプライマリバケットが割り当てられます。${\displaystyle b_{prim}}$そして、それぞれ1ブロックを格納できる2つのスワップバッファがある。各ステップで、両方のスワップバッファが空の場合、プロセッサは読み取りポインタをデクリメントする。${\displaystyle r_{prim}}$プライマリバケットのブロックを読み取ります。${\displaystyle r_{prim-1}}$そして、それをスワップバッファの1つに配置します。宛先バケットを決定した後${\displaystyle b_{dest}}$ブロックの最初の要素を分類することで、書き込みポインタが増加します。${\displaystyle w_{dest}}$ブロックを読み取ります${\displaystyle w_{dest-1}}$別のスワップバッファにブロックを書き込み、その宛先バケットにブロックを書き込みます。${\displaystyle w_{dest}>r_{dest}}$スワップバッファは再び空になります。そうでない場合は、スワップバッファに残っているブロックを宛先バケットに挿入する必要があります。

プロセッサのプライマリバケットのサブアレイ内のすべてのブロックが正しいバケットにある場合、次のバケットがプライマリバケットとして選択されます。プロセッサがすべてのバケットを一度プライマリバケットとして選択した場合、そのプロセッサの処理は終了します。

ブロック順列フェーズではブロック全体のみが移動されるため、一部の要素がバケット境界付近に誤って配置される可能性があります。配列には各要素のための十分なスペースが必要であるため、これらの誤って配置された要素は、オーバーフローバッファを考慮した上で、左から右へと空きスペースに移動されます。