【海外記事】海外ブロガーattractivechaosの基数ソートradixのアップグレードバージョンに関するコードコメント

原文の住所.著者らの修正により,ソート速度は確かに非常に速い.最下位最適化に基づいたソート方法です.主な方法は、ソートされた数字をバイナリに変え、256バレルを設置することです.著者らもこのアルゴリズムを彼のオープンソース作品klib(c言語の標準ライブラリ)に書いた.githubアドレス.
私は余暇に資料を探しながら、コードを翻訳して、半月ぐらいかかりました.だから好きな友達はコレクションしておきましょう^^;
作者の言葉

私が書いたコードのソート速度がボトルネックになったとき、私はこの文章を参考にしました.その後の速度は私の元のバージョンより約40%でした.STLのstd::sortより2.5倍速い.大きな整数配列をソートするには、基数ソートこそ効率的な鉄棒です.他の標準アルゴリズムよりもずっと速くて簡単です.

二コードの注釈と解読
1.コードの主要部分マップ

// sort between [$beg, $end); take radix from ">>$s&((1<b = k->e = beg;
  for (i = beg; i != end; ++i) ++b[rskey(*i)>>s&m].e; // count radix
  for (k = b + 1; k != be; ++k) // set start and end of each bucket
    k->e += (k-1)->e - beg, k->b = (k-1)->e;
  for (k = b; k != be;) { // in-place classification based on radix
    if (k->b != k->e) { // the bucket is not full
      rsbucket_t *l;
      if ((l = b + (rskey(*k->b)>>s&m)) != k) { // different bucket
        rstype_t tmp = *k->b, swap;
        do { // swap until we find an element in bucket $k
          swap = tmp; tmp = *l->b; *l->b++ = swap;
          l = b + (rskey(tmp)>>s&m);
        } while (l != k);
        *k->b++ = tmp; // push the found element to $k
      } else ++k->b; // move to the next element in the bucket
    } else ++k; // move to the next bucket
  }
  for (b->b = beg, k = b + 1; k != be; ++k) k->b = (k-1)->e; // reset k->b
  if (s) { // if $s is non-zero, we need to sort buckets
    s = s > n_bits? s - n_bits : 0;
    for (k = b; k != be; ++k)
      if (k->e - k->b > RS_MIN_SIZE) rs_sort(k->b, k->e, n_bits, s);
      else if (k->e - k->b > 1) rs_insertsort(k->b, k->e);
  }
}

コードを分析するとrs_sortはs=0のときまで再帰的に遍歴する.
バケツのソートは10進数で、言い換えれば10バケツを置くが、著者はcpuの下部構造に基づいて数字を256進数に変換し、言い換えれば256バケツを置く.
2.コード逐行解析コメント

// sort between [$beg, $end); take radix from ">>$s&((1<

1.先頭アドレスが$begと$endの配列をソートする最初の行のコメント.基数は現在の数字の右シフトsビットと(演算)2のn次方-1を選択する

for (k = b; k != be; ++k) k->b = k->e = beg;

2.各バケツのbegポインタは、循環によって、並べ替えられる配列の最初の数字のアドレス(すなわちbeg)に向けられる

for (i = beg; i != end; ++i) ++b[rskey(*i)>>s&m].e; 

3.著者らはここで、数字を256進数とし、この数字をsビット&mだけ右にシフトすることにより、この数字をsビットだけ右にシフトした後の値(右にシフトした後に0になったことが判明した場合は0)を取得し、対応する番号のバケツの格納量を1つ加算する.例えば、この数字をsビットだけ取得した後の値が132であれば、132バケツの格納量を1つ加算する.
この目的は、高方向低遍歴方式で、まず数字を256進数に変換し、その後、この数字の右シフトsビットの値を取得することである.バケツに入れます.
十進法の例を用いて、これは十進法に相当して、私たちはまず万位の数字を取得して、それぞれ彼らを1-10のバケツの中に置いて、それから千位を取得して順番に入れて、それから百位、十位、個位を取得します.

for (k = b + 1; k != be; ++k) // set start and end of each bucket
    k->e += (k-1)->e - beg, k->b = (k-1)->e;

4.各バケツの中にはいくつか入っていますが、各バケツの開始位置はbegを指しています.今、彼らをつなぐ必要があります.b[x+1]の開始ポインタはb[x]の終了ポインタを指しています.
[原句]並べ替えが始まったよ黒板を叩いて!!.前のステップでは対応するバケツの格納量+1だけを並べ替えていたので!!!ということでここでソート開始!!!

for (k = b; k != be;) { //       
    if (k->b != k->e) { //           ，                
      rsbucket_t *l;
      if ((l = b + (rskey(*k->b)>>s&m)) != k) { //         
        rstype_t tmp = *k->b, swap;
        do { //                      
          swap = tmp; tmp = *l->b; *l->b++ = swap;
          l = b + (rskey(tmp)>>s&m);
        } while (l != k);
        *k->b++ = tmp; //         
      } else ++k->b; //             
    } else ++k; //        
  }

3.まとめ
100万件のデータをシミュレーションしてソートしたところ,他のソート速度よりも確かに速度が2.5倍ほど速いことが分かった.普段市販されているradixソートは10進数で、アルゴリズムが実現されていることが多いが、ソート速度は確かに速くない.
もし何か問題があったら、皆さんのメッセージを歓迎します.