radix sortのこと

radix sortは一般にはunsigned intのみに使えるアルゴリズムでした。
Pierre Terdimanが2000年に公開した手法によってfloatにも使えるようになりました。
http://codercorner.com/RadixSortRevisited.htm

しかしこのアルゴリズムはちっと遅いのよね。値を参照する度に、数の正負を確認して、負の場合には特殊な処理をするし、計数ソートのためのテーブルを作る際に要素数*1.5の処理が必要になるし。

で、Michael Herfが2001年に改良策を公開しています。
http://www.stereopsis.com/radix.html

負の値を正の値よりも大きく見えるようにちょっと変換するわけです。

uint32 FloatFlip(uint32 f) {
  uint32 mask = (int32(f) >> 31) | 0x80000000;
  return f ^ mask;
}

uint32 IFloatFlip(uint32 f) {
  uint32 mask = ((f >> 31) - 1) | 0x80000000;
  return f ^ mask;
} 

uint32はfloatを変換したものです。
符号bitが1の場合には、符号bitを0にして、他のbitを反転させます。
符号bitが0の場合には、符号bitを1にするのみとします。

Michael HerfはCPUのキャッシュサイズを考えて11bitごとにradix sortすることを提案してますけど、どうも眉唾です。
4bit(radix8), 8bit(radix4), 11bit(radix3)のradix sortを実装して、qsortとの比較をしてみました。

おおっqsortよりも速いぞ。やっぱりradix sortは8bitが速いなぁ。4bitもそこそこ速いね。11bitは危惧した通り遅いですね。
32個とか要素数が少ない場合はqsortの方が速いですが、無茶苦茶差があるわけではありません。むしろその以上の要素数(128個とか)になった時のメリットの方が多いです。
ということでradix sort(8bit)を使うことに決定。はやくsweep and pruneを実装して、衝突判定を高速化しないとなぁ。
今週末に実装したかった。