プログラミングの作業に何の価値も見出せなくなってしまったd金魚による日記 このページをアンテナに追加 RSSフィード

 iTunes Music Store(Japan) なかのひと あわせて読みたいブログパーツ
|

0001 | 00 |
2004 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2005 | 01 | 02 | 03 | 04 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2006 | 00 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2007 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 |
2008 | 01 | 02 | 03 | 05 | 07 | 08 | 09 | 10 | 11 | 12 |
2009 | 01 | 02 | 03 |
2010 | 03 | 04 | 06 | 07 | 09 | 10 | 11 |
2011 | 01 | 02 | 10 |
2012 | 04 |
2013 | 01 | 05 | 06 | 07 | 08 | 10 |
2014 | 02 | 03 | 05 | 09 |
2015 | 04 |
2016 | 09 | 11 | 12 |
はてな一覧
アンテナに追加
私のアンテナ
私のダイアリー
私のアーカイブ
私のアイデア
私のブックマーク
私のグループ
私のキーワード
ニュース系、今まで続いているシリーズモノの読み物
dKingyo Utility Toolkit Projectのリリース情報
やっぱり暗号化は大人の味(笑)
プログラムのパッキング方法を調べよ
ココが厳しいよMinGW
ライブラリアン通信
ゲームプログラミングどうしよう
CRCについて
ビット演算練習
d金魚の今更Ajax
Windows Tips
VC6 Tips
Win32 WTL Tips
Ruby for C++ User
Ruby Tips
今日のRubyで嵌った事
正規表現PIECE
書きかけ
続く・・・

私のダイアリーの人気記事
新しくブックマークされた記事


あまり、役に立たなそうな個人的に調べた情報や妄想に耽った事、今 勉強している事ヒソヒソと公開していたりします。 | 登録してくれている方々 | d金魚にメール | 当サイトは640x480の画面解像度に対応しています。
日記へのリンク、アンリンクはフリーですが、selfタグのついている部分のコンテンツの引用はご遠慮願います。ご協力よろしくお願いします。


 | 

2006-02-24 sort algorithm part2

[][][]Block Sort Algorithm (BWT) Block Sort Algorithm (BWT)を含むブックマーク Block Sort Algorithm (BWT)のブックマークコメント

http://d.hatena.ne.jp/moceanstar/20060220/1140433699

より、BWT、いわいるBlock sortの話題を扱っていた。

私も2年程前、コーディングを行ってみたのだが、全くできなかった。

詳しくはhttp://d.hatena.ne.jp/studiokingyo/20041011http://d.hatena.ne.jp/studiokingyo/20041022dkutil_cのdkcBlockSort.cを参照してもらうとして・・・


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


で、昔々からDaisuke Okanohara氏のDO++の実装って興味深いなと思っているのです。

google:bsEncoder.hppとかgoogle:bsDecoder.hppとか。

これを見た限り、

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

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


で、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倍遅いのだ。私の実装は・・・おrz!!!

トラックバック - http://d.hatena.ne.jp/studiokingyo/20060224
 | 
Program | Debug | dKingyo Utility Toolkit | library | D言語 | 御本とか | 備忘録 | テクニック | WayBack | 格言 | 英語 | 他力本願 | news | software |

デースケドガー