高速検索アルゴリズムとデータの追加・削除

質問

現在高速検索のアルゴリズムを考えておりますが、
そこにデータの追加・削除が絡むと、
どのようにデータをまとめればいいのでしょうか？

例えば
------------ ------------ -------------
|data1|DATA1| |data2|DATA2| |data3|DATA3|　・・・
------------ ------------ -------------

と要素を２つ持ったデータが複数存在した場合、

dataの昇順リスト
----------------------------
|Index|各データの先頭アドレス|
----------------------------
|・
|・
|・

DATAの昇順リスト
----------------------------
|Index|各データの先頭アドレス|
----------------------------
|・
|・
|・

というそれぞれのリストを持たせれば、
dataで検索したい場合、DATAで検索したい場合、
各リストのIndex値を用いて2分探索すれば高速だと考えました。

しかしデータの追加・削除があればそれぞれのリストを
その度にソートし直さなければなりません。
もちろん追加・削除の度にデータ１つ分ずつずらしてやればいいだけですが、
基本的に使わない領域は解放したいですから、データ数の上限値が決まってない以上は
領域も確保されているとは限らないですから安易にデータをずらすことも出来ません。
データのずらしかたもどうでしょう？
リストに加えるor削除する箇所からその時の最大値までをコピーして
データ１つ分のサイズをずらして貼り付けるといった動作は、
連続した処理や排他的処理を考えると好ましくないのでしょうか？

もし根本的に高速検索と追加・削除の相性が良い手法があればご教授願います。

回答No.1

sakusaker7 · ベストアンサー

Baranced-Tree (平衡木)を使えば良いのではないでしょうか?

平衡木 - Security Akademeia
http://akademeia.info/index.php?%CA%BF%B9%D5%CC%DA

お礼

なるほど参考になりました。
構造が分かりやすくて、有効だと感じました。

回答No.8

don_go

＞現在高速検索のアルゴリズムを考えておりますが、
何と比べて「高速」なアルゴリズムを考えておられる
のでしょうか？
目標をはっきりさせておかないと、既存の物より遅い
のか速いのかさえ判別できないと思いますが？
＃高速検索にアセンブラを使用するという方法も一応
＃ありますが....

回答No.7

mikaemi

蛇足ですけど^^

uya_15 さんは何度か質問を投げていらっしゃいますが、仕事としてプログラミングされているのなら、一度、アルゴリズム・データ構造の良書で勉強なさるのが、結局、早道で今後のためにもなるように思います^^

わたしは、古いテキストしか知りませんが、

・A.V.エイホ 他 著、大野義夫 訳『データ構造とアルゴリズム』培風館
・石畑清 著『アルゴリズムとデータ構造 (岩波講座 ソフトウェア科学）』岩波書店

などはいかがでしょう。A.V.エイホの『アルゴリズムの設計と解析』などもいいですが多少難しいですし、D.E.クヌースの『The Art of Computer Programming』はさらに難しいので、わたしはお薦めしません^^

お礼

いくつかの高速検索のためのアルゴリズムには目を通しまして、
ただしっかり勉強だけを出来る時間の余裕もなかったので、しっかり理解できたのは2分木探索くらいでした。
またこのアルゴリズムはこういう時に最適だ！というところまで読みきれなかったので、
調べながらその傍らで質問させてもらいました。

回答No.6

mikaemi

すみません。参考にあげた URL では、＜クローズドハッシュ＞と呼んでいます^^;

>『オープンハッシュ表（呼び方はいろいろ錯綜してるようですが）で持ってもいいと思います。』

回答No.5

mikaemi

あと、「基本的に使わない領域は解放したいですから…」とありますが、ちなみに、標準的な Unix 系のＯＳの malloc・free・realloc を使った実装は、free しても、システム自体に不要なメモリを返すわけではなく（プロセス自体の大きさは減少しない）、malloc・realloc で不要メモリの再利用ができるようにしているだけだと思います。brk・sbrk などを使えば、システムにメモリを返す（プロセス自体の大きさが減少する）ことができると思いますが、そうするとたぶん、malloc・free・realloc （これらが内部で sbrk を使っていると思うので）は使えなくなるのでやめたほうがいいと思います。windows は知りませんけど^^;

回答No.4

mikaemi

ご参考：

0. レコードを配列の要素として持つ必要がない。
1. レコードの記憶管理は別にする。
2. key、KEY 毎に一意にレコードが決まる。
3. key、KEY 毎に、ソート順に表示できたほうがいい。
とすると、以下のサンプルコードのようなやり方もあると思います。

1 で記憶管理も一緒にするとすれば insert・erase で new・delete するとか、2 でレコードが複数ある可能性があれば multimap にするとか、3 でソート順に表示しなくてもいい（ほとんど表示処理しないなら表示の際にソートして表示もいいですが）ならハッシュ表で実装してもいいですし。。まぁいろいろあると思いますけど^^

また、ソートされている必要がなく、レコードを配列要素として持つ必要がある（ただし、管理のためのメンバをレコードに追加できる場合）のなら、オープンハッシュ表（呼び方はいろいろ錯綜してるようですが）で持ってもいいと思います。
http://www-ui.is.s.u-tokyo.ac.jp/~takeo/course/2002/algorithm/note4.pdf

ただ、すべて、主記憶に格納できる場合の話で、レコード・レコード数が巨大で外部記憶に格納しないとならない場合はまた別の方法によるのがいいと思います^^

＝＝＝（key==data、KEY==DATA なら map でなくて set でいい）
#include <iostream>
#include <string>
#include <map>
#include <utility>

struct Record
{
std::string key;
double data;
int KEY;
std::string DATA;
};

std::map<std::string, Record *> map1;
std::map<int, Record *> map2;

Record *find(const std::string &k)
{
std::map<std::string, Record *>::iterator i = map1.find(k);
if (i == map1.end()) return 0;
return i->second;
}

Record *find(int k)
{
std::map<int, Record *>::iterator i = map2.find(k);
if (i == map2.end()) return 0;
return i->second;
}

bool insert(Record *r)
{
if (find(r->key) || find(r->KEY)) return false;
map1.insert(std::make_pair(r->key, r));
map2.insert(std::make_pair(r->KEY, r));
return true;
}

template<typename T> bool erase(const T &k)
{
Record *r = find(k);

if (!r) return false;
map1.erase(r->key);
map2.erase(r->KEY);
return true;
}

void print(const Record *r)
{
std::cout << r->key << '\t' <<
r->data << '\t' << r->KEY << '\t' << r->DATA << '\n';
}

void print1()
{
std::map<std::string, Record *>::iterator i = map1.begin();
while (i != map1.end()) {
print(i->second);
++i;
}
std::cout << '\n';
}

void print2()
{
std::map<int, Record *>::iterator i = map2.begin();
while (i != map2.end()) {
print(i->second);
++i;
}
std::cout << '\n';
}

#include <iostream>

int main()
{
Record recs[] = {
{ "yamada", 0.0, 0, "taro" },
{ "tanaka", 1.0, 1, "jiro" },
{ "sato", 2.0, 2, "saburo" },
{ "fujita", 3.0, 3, "taira" },
{ "suzuki", 4.0, 4, "muneo" },
};
std::size_t nrec = sizeof recs / sizeof recs[0];
for (int i = 0; i < nrec; ++i) insert(recs + i);
print1();
erase("fujita"); erase(1);
print2();
}
＝＝＝
% ./a.out
fujita 3 3 taira
sato 2 2 saburo
suzuki 4 4 muneo
tanaka 1 1 jiro
yamada 0 0 taro

yamada 0 0 taro
sato 2 2 saburo
suzuki 4 4 muneo

回答No.3

mikaemi

ソートしている目的が単に検索のためだけであれば、検索項目毎のハッシュ表を持つのもいいと思いますよ。ほかの用途に必要なのでソートされている必要があるのなら、検索項目毎にバランス木にするのがいいんじゃないでしょうか。

回答No.2

Tacosan

普通は平衡木かなと思いますが場合によってはハッシュもあり?
平衡木といっても 2色木とか 2-3木とか 2-3-4木とかあって, プログラミングの難易度が違うので注意してください. 2-3木は組みやすい方かな. 2色木は図がないと苦労しそうな気がします.

お礼

平衡木にもいろいろあるんですね。
時間のある時にでも、それぞれの長所を調べてみたいです。