データの参照方法について

質問

以下のようなファイルがあります。
（区切り文字は半角スペースです）
001 aa sse
546 bbyf thfnff
214 wwr fyhbgf

例えば「546」と入力した時に、
「bbyf」と「thfnff」を引っ張ってくる
処理をしたいのですが
そういうことは出来ますか？

Ｅｘｃｅｌなどで言えば
lookupのような感じです。

よろしくお願いします。

回答No.3

Kenichi31980 · ベストアンサー

実装方法は、いろいろあるとおもいます。
ここで問題なのは、
１．どの程度のアクセス頻度か？
２．どの程度のデータ量か？
３．どの程度のレスポンスがほしいか？
です。

Nを要素の数とします。

アクセス頻度が少ない（１回とれれば十分)であれば、
線形探索法が有効です。
ファイルを順に読んでいってヒットしたら返す方法。
この方法だと平均 N/2回探索するとヒットします。

もう一つ簡単な実装方法ですが、二分探索法
要素分の箱をまず用意して、あらかじめ数字でソートして、入れておきます。
リクエストがきたら
まず真ん中を調べます。(start,middle0,end)
真ん中の値より大きければ、(middle0,end)の中間をみます。(middle0,middle1,end)
これを繰り返していけば、平均logN回で、探索することができます。

アクセス頻度が多く何度も利用し、速いレスポンスが要求されるのであれば、B-treeを構築するのがよいと思います。
C++であれば、STL mapを利用すると素直にtreeでの実装ができます。
この方法もlogN回で実現できます。

あと、ハッシュ法を利用するのもいいと思います。
この方法だと、1発でヒットしているか判定できます。

Webで引くとアルゴリズムの紹介があるとおもいます。

回答No.2

ddnp009

>そういうことは出来ますか？
出来ます。
ただその方法は唯一ではありません。いくつもある。
従ってどの手法を採るかは、要求仕様を把握しているあなた次第。

暗中模索、せめてヒントが欲しいのなら、
最低次の点を明らかにしましょう。
きっと誰かがサンプルを無償で提供してくれますよ。

loopupのキーとなる先頭の3桁について
　これは必ず3桁で構成されるか。
　重複した場合どうなるか。

抽出対象の文字列について
　トークンは必ず2つなのか。
　(可変個数をサポートする必要があるか)

補足

ご返事有り難うございました。
説明不足で申し訳ありません。

＞loopupのキーとなる先頭の3桁について
＞これは必ず3桁で構成されるか。
必ず３桁で構成されています。

＞重複した場合どうなるか。
重複はありません。

＞抽出対象の文字列について
＞トークンは必ず2つなのか。
＞　(可変個数をサポートする必要があるか)
必ず２つずつです。

よろしくお願いします。

回答No.1

episteme_at_goo

できます。

ファイルを逐次読み込みながら、あるいは一旦配列の類に格納してから、どちらでも。
要はループで回りながら条件に合致するものを見つけるだけですから。