リストの高速検索アルゴリズム

質問

1.　Aを使用→Aを登録→（A=1）
2.　Bを使用→Bを登録→（B=1,A=2)
3.　Cを使用→Cを登録→（C=1,B=2,A=3)
4.　Dを使用→Dを登録→（D=1,C=2,B=3,A=4)
5.　Bを使用→順序のみ更新→(B=1,D=2,C=3,A=4)
6. 一番古いのを削除　→Aを削除→(B=1,D=2,C=3)

上記のような１０００個のデータ(A,B…)を使用したら、使用履歴に登録していくプログラムを作るとして
高速に検索するには、どうすればよろしいでしょうか。
検索したいのは以下の２つです。
・一番古いデータの検索（削除するため）
・データが登録有無の検索

汎用的な手法があればその名称をお教え願えないでしょうか。ちなみに二分木はちょっと違うような気がしました。

回答No.5

Tacosan · ベストアンサー

登録・検索のためのハッシュ (など) と削除のための双方向リストを併用するのがベストかなぁ?

・登録や検索のときにはハッシュを調べ, リストの中の当該データを最後尾に移動させる
・削除のときにはリストの先頭の要素を取り出し, それと対応するハッシュの要素を消す

ハッシュとリストのどちらからでもたどれるようにする必要はありますが, 全ての操作が (ほぼ) 定数時間になるはずです.

お礼

ハッシュと双方向リストの併用ですね。
ありがとうございます。

回答No.6

nucomewl

そのルーチンは秒間何回呼ばれますか?

もしも、秒間10回程度ならば配列でやってしまうのがエンバグの可能性が低くて確実だと思いますよ。

マイコンのように遅いか、処理時間にクリティカルに影響するほど呼ばれ続けるならば、オープンハッシュと双方向リストの併用で片付くと思います。

とりあえず、配列でやってみてあまりに遅いと思うようならば書き変えたらどうでしょうか。

お礼

なるほどです。
実際の遅延時間を考慮して、問題なければ確かに配列でやったほうが手っ取り早いですよね。
勉強になりました。

回答No.4

bender

No.3 です。
[ ... 高速に検索するためには、最も最近登録された ...] は、[... 高速に登録、削除するためには、...] の間違いです。検索は、配列 i を直接参照すればよいので、No.2 の方が書かれたハッシュテーブルと(ほぼ)同じ効率です。

回答No.3

bender

データの種類が１０００個と前もって分かっているのであれば 、サイズが１０００の配列を利用するのが最も速いのではないでしょうか。

配列の i 番目には、データ i (0<=i<=999) の登録有無を記録するとし、例えば、データ i が登録無(未登録、削除済)の場合、配列要素 i に 1000 を、登録有の場合、データ i が最も最近登録されたデータであれば -1 を、それ以外の場合は、データ i の次に登録されたデータのデータ番号を配列 i に記録しておけばよいと思います。高速に検索するためには、最も最近登録されたデータのデータ番号と、最も初めに登録された(一番古い)データのデータ番号の 2 数も記録する必要があります。

各配列要素、また、最も最近登録されたデータのデータ番号、最も初めに登録された(一番古い)データのデータ番号を初め 1000 に初期化し、あとは、登録、削除に応じて、しかるべく配列要素とこの 2 数の情報を更新すればよいと思います。

お礼

ありがとうございます。
今回メモリを節減したいので、双方向リストを使用します。

回答No.2

cherry_moon

高速に検索がしたいならハッシュテーブルはどうですか？
ハッシュ値が同じものを双方向リストで管理すれば、mtsedさんのしたいことはどちらも満たせると思います。

参考URL：

http://ja.wikipedia.org/wiki/ハッシュテーブル

お礼

ありがとうございます。
ハッシュですね。
やってみます。

回答No.1

mats_may

双方向リストなどはどうでしょうか?
双方向リストとは正順にも逆順にもたどれる
リスト構造のことなんですが,
mtsedさんの例の5においてはB,D,C,Aが正順で,
B,A,C,Dが逆順になります.
双方向リストのアルゴリズム自体はネットや本に
詳しく書かれていると思いますが,簡単に言うと
各要素に対して次の要素へのポインタと前の要素へのポインタをつけておくことによって,どちらの方向へもたどれる様にするというものです.
一番古いものを正順の一番最後,つまり逆順の2番目に
来るようにしておけば,リストを一回たどれば一番古い
要素にたどり着くことができ,削除することが出来ます.いかがでしょうか?

お礼

ありがとうございます。
双方向リストですね。
うまくいきました。