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

Question

sakusaker7 · Accepted Answer

Baranced-Tree (平衡木)を使えば良いのではないでしょうか?

平衡木 - Security Akademeia
http://akademeia.info/index.php?%CA%BF%B9%D5%CC%DA

don_go · Answer

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

mikaemi · Answer

蛇足ですけど^^

uya_15 さんは何度か質問を投げていらっしゃいますが、仕事としてプログラミングされているのなら、一度、アルゴリズム・データ構造の良書で勉強なさるのが、結局、早道で今後のためにもなるように思います^^

わたしは、古いテキストしか知りませんが、

・A.V.エイホ 他 著、大野義夫 訳『データ構造とアルゴリズム』培風館
・石畑清 著『アルゴリズムとデータ構造 (岩波講座 ソフトウェア科学）』岩波書店

などはいかがでしょう。A.V.エイホの『アルゴリズムの設計と解析』などもいいですが多少難しいですし、D.E.クヌースの『The Art of Computer Programming』はさらに難しいので、わたしはお薦めしません^^

mikaemi · Answer

すみません。参考にあげた URL では、＜クローズドハッシュ＞と呼んでいます^^;

>『オープンハッシュ表（呼び方はいろいろ錯綜してるようですが）で持ってもいいと思います。』

mikaemi · Answer

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

mikaemi · Answer

ご参考：

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/2 …

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

＝＝＝（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

mikaemi · Answer

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

Tacosan · Answer

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

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

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

＞現在高速検索のアルゴリズムを考えておりますが、

蛇足ですけど^^

すみません。

ご参考：

ソートしている目的が単に検索のためだけであれば、検索項目毎のハッシュ表を持つのもいいと思いますよ。

普通は平衡木かなと思いますが場合によってはハッシュもあり?

似たような質問が見つかりました

関連するカテゴリからQ&Aを探す

デイリーランキングこのカテゴリの人気デイリーQ&Aランキング

マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング