アルゴリズムのご相談

質問

はじめまして
DHCPのような動作をするアルゴリズムを考えている最中なのですが…
その案の中でどうしてもクリア出来ない課題があります。

「配列で作られたテーブルにユーザ名の一覧があり、
そのユーザ名をキーワードとして配列のインデックスを抽出したい」

というもので、これだけなら簡単なのですが、以下３つの条件の提示により、無理ではないかと思えて仕方がないです。
・ユーザ名は何らかのルールに則って作られた文字列ではない。
・キーワードを頭から順に比較して探していく方法を使ってはいけない。
・ユーザの追加・削除がある度にソートし直さなければならないような構造にしてはいけない。

２分探索法などの検索回数を減らす方法はソートされてることが前提条件ですし、
ユーザ名から配列のインデックスに使える数値に変換できるような都合のいい関数なんて存在しないように思えるのですが、いかがでしょう？

ちなみに開発言語はCです。

回答No.1

mikaemi · ベストアンサー

どうしてそのような制約があるのか理解できませんが、
ユーザ名をキーワードとした配列があるとして、
それとは別にユーザ名から配列のインデクスが引ける
ハッシュ表を用意すればできますね（領域の無駄ですけど）。

ユーザ名の削除はあり、既登録のユーザ名のインデクスは
変えたくなく、削除であいた配列要素の再利用をしたい場合には、
フリーインデクスのフリーリストを作っておけばいいですね（これにも
また無駄に領域を使わないとなりませんが）。
もちろん、配列がいっぱいになったら、realloc() しないと
いけませんが、インデクスで管理しているから更新部分は
配列のみでOKでしょう。

しかし、そもそも、掲出の制約がなぜあるのか。。。
ダメなデータ構造をテクニックでカバーしようとしないで、
データ構造とアルゴリズムを同時に設計したほうがいいのではないですか？^^;

お礼

ハッシュ表という概念を初めて知りました。
ありがとうございます。

回答No.5

mikaemi

こんな感じでいいのかしら？ハッシュ表やフリーリスト操作が面倒だったので、C++の map(バランス木だけど^^)やstackを使っちゃってますが、
ほかのところは、C言語っぽく書いてます（笑）

レコードの構造体は、プログラマが勝手にいじれないと仮定しました。

登録レコードは name が NULL でないので、レコードの配列を
直接たどって、登録レコードか空きレコードかがわかるようにしてます。レコードの構造体とフリーリストのためのリンクとを共用体にしてやれば、フリー領域管理のためのメモリは節約できるでしょうね。
＝＝＝＝
#include <stddef.h>
#include <stdlib.h>
#include <string.h>

/* ユーザのレコード: 今は名前のポインタのみ */
struct Record { char *name; };

#include <stack>

struct Table
{
struct Record *prec; /* レコードの配列 */
size_t nrec; /* 登録レコード数 */
size_t sz; /* 配列の大きさ */
std::stack<size_t> flist; /* 空いているレコードのインデクスのリスト */
} table;

void iniTable()
{
const size_t init_size = 3;
size_t i;

table.prec = (struct Record *)malloc(sizeof(Record) * init_size);
table.nrec = 0;
table.sz = init_size;
for (i = 0; i < table.sz; ++i) {
table.prec[i].name = NULL;
table.flist.push(i); /* インデクスをフリーリストへ登録 */
}
}

/* 配列を m だけ大きくする */
void growTable(size_t m)
{
size_t i;
table.prec =
(struct Record *)realloc(table.prec, sizeof(Record) * (table.sz + m));
for (i = table.sz; i < table.sz + m; ++i) {
table.prec[i].name = NULL;
table.flist.push(i); /* インデクスをフリーリストへ登録 */
}
table.sz += m;
}

#include <map>
#include <string>

typedef std::map<std::string, size_t> map_t;
map_t indexMap; /* 配列のインデクス管理マップ */

void finTable()
{
map_t::iterator i;
for (i = indexMap.begin(); i != indexMap.end(); ++i)
free(table.prec[i->second].name);
free(table.prec);
while (!table.flist.empty()) table.flist.pop();
indexMap.clear();
}

const size_t errSz = (size_t)-1; /* エラー報告用インデクス値 */

size_t put(const char *user)
{
const int grow_size = 3;
size_t idx;
map_t::iterator iter = indexMap.find(user);

/* user のレコードがすでにあれば何もしない */
if (iter != indexMap.end()) return iter->second;

/*... user は存在しないのでレコードを作る ...*/

/* フリーリストが空なら配列を大きくする */
if (table.flist.empty()) growTable(grow_size);

/* フリーリストから空きインデクスをもらう */
idx = table.flist.top(); table.flist.pop();

/* user のレコード設定 */
table.prec[idx].name = strcpy((char *)malloc(strlen(user) + 1), user);
indexMap[user] = idx; /* インデクスをマップに登録 */
++table.nrec;

return idx;
}

size_t get(const char *user)
{
map_t::iterator iter = indexMap.find(user);
if (iter == indexMap.end()) return errSz;
else return iter->second;
}

size_t del(const char *user)
{
size_t idx = errSz;
map_t::iterator iter = indexMap.find(user);
if (iter != indexMap.end()) {
/* user は存在した */

idx = iter->second; /* user のインデクスを得る */

/* user のレコードを消去 */
indexMap.erase(iter);
table.flist.push(idx);
free(table.prec[idx].name);
table.prec[idx].name = NULL;
--table.nrec;
}
return idx;
}

#include <stdio.h>

int main()
{
size_t idx;

iniTable();

idx = put("saito");
printf("%d %s\n", (int)idx, table.prec[idx].name);
idx = put("yamada");
printf("%d %s\n", (int)idx, table.prec[idx].name);
idx = put("tanaka");
printf("%d %s\n", (int)idx, table.prec[idx].name);
idx = put("suzuki");
printf("%d %s\n", (int)idx, table.prec[idx].name);
idx = del("tanaka");
if ((idx = get("takana")) == errSz) printf("OK\n");
idx = put("sato");
printf("%d %s\n", (int)idx, table.prec[idx].name);
idx = put("takahashi");
printf("%d %s\n", (int)idx, table.prec[idx].name);

finTable();
}
＝＝＝＝＝＝＝
% ./a.out
2 saito
1 yamada
0 tanaka
5 suzuki
OK
0 sato
4 takahashi

お礼

ここまで丁寧にサンプルを作って下さるなんて…。
がんばって解読してみます

回答No.4

noname#140971

服飾デザイナでプログラマではありませんが・・・。

どんなアルゴリズムを構想するにしろ、データの件数という量は無視できないと思います。
対象が１０００レコードと１０万レコードじゃ話が違ってくるのじゃないですかね。

実テーブルの制約が絶対条件であれば、仮想テーブルを用意して解決するしかないでしょう。
が、これも量次第では、ユーザ名を仮想テーブル管理アプリーケーションに投げる策も考えることに。
量次第では、構造体変数をバイナリで記録しておいてセーブとロードを繰り返しても良いような気がします。

いずれにしろ、アルゴリズムの問題というよりも、データ量と逃げの関係だと思いますが・・・。

お礼

おっしゃる通りです。
どこかの優先度を妥協しないといけないと思ってました。

回答No.3

noname#39970

2分探索または探索用の独自インデックスを作ったら良いんじゃない？
配列をアドレスとして置き換え表現して　インデックスにアドレスがかかれてれば値を挿入するときに探索インデックスに適合するようにしたら良いのでは？

・・・要するに他の人と言ってる事が同じかな

回答No.2

jacta

3条件を言葉通りに受け止めれば、配列の最後から逆順にたどることで実現が可能です。
あるいは、配列の添え字を二分木などに登録しておく方法もありです。