Block Sort Algorithm (BWT)

Program 備忘録 ProgramIdiom

http://d.hatena.ne.jp/moceanstar/20060220/1140433699
より、BWT、いわいるBlock sortの話題を扱っていた。
私も2年程前、コーディングを行ってみたのだが、全くできなかった。
詳しくはhttp://d.hatena.ne.jp/studiokingyo/20041011やhttp://d.hatena.ne.jp/studiokingyo/20041022やdkutil_cのdkcBlockSort.cを参照してもらうとして･･･


今、やっとC言語によるクイックソートアルゴリズムによるブロックソートの実装ができた所だ。でも、ブロックソートはクイックソートでも遅いアルゴリズムである。なのでO(n)のソートアルゴリズムが必要だったりする。伏線記事：http://d.hatena.ne.jp/studiokingyo/20060223


で、昔々からDaisuke Okanohara氏のDO++の実装って興味深いなと思っているのです。
google:bsEncoder.hpp]とか[google:bsDecoder.hppとか。
これを見た限り、

  • １：先頭2byteで分布数えソート　
  • ２：その時先頭2byteで重複していた要素 (例：先頭 ab ab ab bc bc cdならabは3つ bcは2つ cdは1つなのでソートしない)同士で分割してソート
  • ３：その時の状況によって次の2byteの要素を使って１に戻ったり、クイックソートしたり、挿入ソートしたりである。

今これ系のアルゴリズムを実装中である。


で、Blocksortを実装する時、挿入ソートとクイックソートどちらが速いのかテスト

1024byte random data
1 / bs insertion sort / 14834639
2 / bs quick sort / 27418567

なんか、クイックソート負けてるんですけど

6k byte random data
1 / bs insertion sort / 647528702
2 / bs quick sort / 814268104

データの長さを変えても変わらず･･･

56kbyte random data
測定不能･･･　遅すぎ･･･

多分、私のクイックソートの実装が良くないんだと思う。

1 / bsEncoder sort / 8876325
2 / bs insertion sort / 1312993091
3 / bs quick sort / 1353318909

google:bsEncoder.hppと比べて見ても147倍遅いのだ。私の実装は･･･おｒｚ!!!