16ビットのデータが、たとえば1000個、配列で与えられているとします。
unsigned short data[1000];
このデータをしらべて、重複するものを除いて何種類の値があるかを数える場合、一番素朴な方法だと、次のようにやると思います。
int i, j;
int count = 0;
for(i = 0; i < 1000; i++) {
for(j = 0; j < i; j++) {
if(data[j] == data[i]) {
break;
}
}
if(i == j) {
count++;
}
}
この方法だと、２重のループがあって処理に時間がかかります。そこで、メモリに余裕があれば内側のループをやめて、
int i;
int count = 0;
int flag[0x10000];
int n;
for(i = 0; i < 0x10000; i++) {
flag[i] = 0;
}
count = 0;
for(i = 0; i < 1000; i++) {
n = data[i];
if(flag[n] == 0) {
flag[n] = 1;
count++;
}
}
これだと、２重のループを使うものよりは速くなりますが、データが1000個しかないのに、65536個のflagをクリアするのに時間がかかり、今ひとつです。
ところが、次のような賢い方法があり、２重のループも配列のクリアも無くすことができます。
int i;
int count = 0;
unsigned short flag[0x10000];
unsigned short link[0x10000];
int n;
for(i = 0; i < 1000; i++) {
n = data[i];
if(flag[n] >= count || link[flag[n]] != n) {
flag[n] = count;
link[count] = n;
count++;
}
}
私がこのアルゴリズムを知ったのはかなり昔なので、どこで知ったのか思い出せないのですが、これほど賢いアルゴリズムだから何か名前がついていると思うのですが、それがわかりません。
名前がわからないので、人に頼んだりする時、上のような長い説明をしなくてはなりませんが、名前がわかっていれば「？？法でやっといて」、と言えばいいのですけど。
投稿日時 - 2007-02-04 05:03:11
6人が「このQ&Aが役に立った」と投票しています
回答（3件中 1～3件目)
面白いアルゴリズムですね：）
すぐには理解できず，「本当に初期化しなくても動くの？」と懐疑的だったので，
flag[] と link[] にイジワルな (つもりの) 初期値を入れて動かしてみたところ，
ちゃんと動いたので，落ち着いて考え直して理解しました．
そのアルゴリズムは初めて見るので，当然作者にも心当たりがないのですが，
ついさっき「ひょっとしたら…」ということを思い出したのでコメントしました．
昔，LIFEBOAT の機関誌 (？) に載っていた超高速ソートライブラリ LSORT の話です．
(今，「LSORT LIFEBOAT」で検索してみたところ，
「The Lifeboat PERSPECTIVE 1984.4」と出ました．)
http://www.geocities.jp/oldbig_ancient/KodaiHP3.htm
「LSORT」とは線形時間 (linear time) つまり Ｏ(n) のソートという意味で，
一種の基数ソートです．記事によると (うろ覚えですが)，例えば16ビット
無符号整数をソートするのに上下の１バイトずつに分け，それぞれを配列の
添字として使うことにより，各バイトの値ごとに出現回数を数えたり，ソート
したりするのがポイントです．
もっともこれだけでは，基数ソートやビンソートを知っている人にとっては
目新しいことは何もありません．
(しかし私は当時知らなかったので，これだけでも感心しました．
その後，1989年に買ったアルゴリズムの教科書で基数ソート，ビンソートを知りました．)
LSORT は確か Lattice C 用ライブラリとして販売されており，私もこの記事を
読んで会社の費用で購入しました．ご質問のアルゴリズムと同様に，ビンソートも
大きな作業メモリを必要とします．そこで LSORT にはほとんど作業メモリを使わない
バージョンも提供されており，私が一番驚いたのはそのメモリ管理アルゴリズムです．
残念ながらこれもほとんど忘れてしまい，断片的なことしか覚えていませんが，
・元データの各バイトを配列の添字として使って，各バイト値の出現回数を調べる．
・元データをソートすると，(最)上位バイトはそのバイト値の昇順に並ぶので，
バイト値の順に，その出現回数だけを覚えておけばよい．
… その他色々あるのですが，かなり忘れてしまってその巧妙さを伝えられないのが
残念です．このアルゴリズムを理解したとき，大量の元データが，出現回数やアドレス
範囲といった，全然別の形態のデータに変換されていくやり方に本当に驚嘆しました．
LSORT がご質問のアルゴリズムと通ずるところがあると思った点は次のとおりです．
(もちろんこれだけでは同一犯という証拠にはほど遠いですが．)
・元データ (の一部のビット列) を配列の添字に使う．(ビンソート的手法)
・非常に巧妙でトリッキーなメモリ管理．
非常に面白い記事だったので，上記の Lifeboat PERSPECTIVE を
しばらく保存していたのですが，いつの間にか紛失…．(ToT)
(大掃除すれば出てくるかもしれませんが．(笑))
作者名も忘れてしまいましたが，確か長野県の有限会社だったような気が…．
ご興味がおありなら，「The Lifeboat PERSPECTIVE 1984.4」が
どこかに埋もれてないか，探してみられるといいかもしれません．
(もし大掃除で出てくれば，私も自分のホームページで LSORT について書こうかな．(笑))
基数ソート
http://ja.wikipedia.org/wiki/%E5%9F%BA%E6%95%B0%E3%82%BD%E3%83%BC%E3%83%88
バケットソート (ビンソート)
http://ja.wikipedia.org/wiki/%E3%83%90%E3%82%B1%E3%83%83%E3%83%88%E3%82%BD%E3%83%BC%E3%83%88
投稿日時 - 2007-02-05 00:14:24
補足
ご回答ではありませんね。でも懐かしい単語を聞いたので思わずコメントさせていただきます。
LSORTというのは初めて聞いた名前ですが、私はヒストグラムソートと読んでいました。いまなら、16ビットの値でヒストグラムを作り一気にソートしますね。昔なので65536個のヒストグラムを作るメモリがないので上下の8ビットづつ２回に分けてやってたんでしょうね。
昔の雑誌には今では作者がわからない、名称も分からない(名前がもともとない？)優れたアルゴリズムがあったような気がしますね。私は1970年代の終わりごろからIOとかアスキーとかためていたんですが、何年か前に全部処分してしまいました。Lifeboatの広告はトラ技とかインターフェースにのっていましたね。これも今はもうありません。
投稿日時 - 2007-02-05 01:31:52
★『ハッシュ』というキーワードで検索してみたらどうでしょうか？
・『名前のわからない賢いアルゴリズム』が約２倍くらい高速でしたか。→お勉強になります。
『私のアルゴリズム』では 約3000 回のループ処理を行っていますので、1000 回で済む
『名前のわからない賢いアルゴリズム』の方が早いのですね。
・今、ちょっと思い出しましたが『ハッシュ』に関連したアルゴリズムに似たような方法が
過去にあった気がします。→私もよくは覚えていませんが、『ハッシュ』や『テーブル』
などのキーワードで検索するか、質問者さんの持っている書物で調べてみてはどうでしょう。
・これ以上はアドバイスできません。ごめんなさい。→他の回答者さんを！
投稿日時 - 2007-02-04 18:34:09
お礼
たびたびのお答えありがとうございます。
> 『私のアルゴリズム』では 約3000 回のループ処理を行っていますので、1000 回で済む
> 『名前のわからない賢いアルゴリズム』の方が早いのですね。
問題の本質は、ワークエリアの初期化が必要かどうかという事だと思います。データの処理そのものより、ワークエリアの初期化の方が時間がかかるようだと、結局高速化には障害になるわけです。回答者様のアルゴリズムだと初期化のためのループは2048回と少なくなっていますが、データの範囲が20ビットになったら32768回になってしまいます。この「名前のわからない賢いアルゴリズム」の優れた所は、ワークエリアの初期化を省略できるので、データの範囲が20ビットになろうが、もっと増えようがメモリさえ許せば同じ速度で処理ができるということです。（キャッシュのことを考えると範囲が小さいほうが速いかもしれませんが、それは本質的な問題ではありません。）
なお、メモリに余裕があって
unsigned flag[65536];
をスタティックに確保できれば、flagがONになる時の値を毎回変化させれば、初期化は１回だけですみます。１順するまで約43億回、１秒間に60回やったとして、１順には数年かかります。でもゲーム機の悲しさ(私はゲーム屋です)スタティックな256Kのメモリなんてワークに使ったら、他のスタッフから苦情がでます。ワークエリアは毎フレーム確保しているので、その都度不定になっています。
ハッシュを使えば、処理対象のデータの範囲が限定されていなくても処理できるようになりますが、結局ハッシュテーブルの初期化という問題が出てきます。
いずれにしろハッシュとこのアルゴリズムは独立していて、別の部分に働くので、直接の関連は無いし、独立しているからハッシュを使う場合でもこのアルゴリズムは利用できます。ですから、ハッシュで検索しても答えは出てこないような気がします。
投稿日時 - 2007-02-04 20:14:14
★私は聞いた事がありませんね。
・『賢いアルゴリズム』は人それぞれです。
有名ならば『google』で『重複排除 アルゴリズム』と検索すれば見つかるのでは？
・for文中で『data』のスキャンを１回で行っているようですね。
・質問さんの『アルゴリズムの名前は？』というのは、誰かが考え出した独自のもので
『？？法』と名前が付いていないのかもしれませんね。
『昔知った』とありますが、本、Webサイト、他人から聞いたなども思い出せないのですか？
・ちょっと調べてみましたが分かりませんでした。→他の回答者さんの情報を！
おまけ:私のアルゴリズム
int i, lo, hi, count = 0;
unsigned long flag[0x10000 / 32]; // 8Kバイト(128Kバイトよりもメモリが節約)
for ( i = 0 ; i < (0x10000 / 32) ; i++ ){
flag[ i ] = 0xFFFFFFFF; // ビットONで初期化
}
for ( i = 0 ; i < 1000 ; i++ ){
lo = (data[i] & 0x1F); // 下位5ビット
hi = (data[i] >> 5); // 上位11ビット
if ( flag[hi] & (1 << lo) ){ // ビットONならば
flag[hi] &= ~(1 << lo); // ビットのリセット
count++; // カウント
}
}
最後に:
・上記のアルゴリズムで『if』の判定の数を減らせます。
多分、こちらの方法がループの『if』判定が少ないので高速になりませんか？
・以上。おわり。
投稿日時 - 2007-02-04 12:49:31
補足
Googleで[重複排除 アルゴリズム]で検索してみましたが、「名前のわからない賢いアルゴリズム」に相当するものは見つかりませんでした。
値の範囲が16ビットとかに限定されているというのは、特殊すぎるのかもしれませんね。
投稿日時 - 2007-02-04 17:11:04
お礼
ご回答ありがとうございます。
> 上記のアルゴリズムで『if』の判定の数を減らせます。
> 多分、こちらの方法がループの『if』判定が少ないので高速になりませんか？
残念ながら、テストしてみたところ、お示しの方法では「名前のわからない賢いアルゴリズム」の方が約２倍くらい高速でした。
アルゴリズムではなく、コーディングテクニックの改良により性能を上げるという事は現場では当然考えます。フラグをビットでやるというのは、この例では、メモリの使用効率にも影響しますから。しかし、アルゴリズムの改良とはレベルがちがいます。
今回の例ようにデータが16ビットの場合は確かにそれほどの大差はありませんでしたが、データが20ビットになったら、10倍以上の差になります。(実験してみました)
> 『昔知った』とありますが、本、Webサイト、他人から聞いたなども思い出せないのですか？
当時はとくかく性能がアップしていれば問題なかったので、アルゴリズムの名前なんて気にもしていませんでした。また、当時はインターネットが一般に普及にする前の17、8年くらい前なので、本か雑誌で知ったのだと思います。もしかしたら、本屋で立ち読みだったかもしれません。でも、本か雑誌に書いてあったことは間違いないので、それなりに世の中に知られているアルゴリズムだと思います。それなら、名前がついていても不思議ではないのですが。
投稿日時 - 2007-02-04 16:21:47
