C# と VB.NET の質問掲示板

ASP.NET、C++/CLI、Java 何でもどうぞ

C# と VB.NET の入門サイト

Re[10]: 検索処理

(過去ログ 37 を表示中)

[トピック内 14 記事 (1 - 14 表示)]　 << 0 >>

■18791 / inTopicNo.1)

　検索処理

▼■

□投稿者/ セイン (84回)-(2008/05/16(Fri) 11:53:34)

分類:[C/C++]　

.NET 2005
C++

で開発しております。

CData {
public
CString name;
int no;
}

std::vector<CData> data;

上記のdataからnoの一致する物を検索する方法で高速な方法を考えていますが、思いつきません。
std::sortをつかってno順に並び替えた後、2分検索木で探すのが良いかと考えているのですが、
std::findなど、既に存在する検索アルゴリズムでできないものかと悩んでおります。

std::findは完全一致の構造体を探すので、名前がわからないと検索できませんし・・・。

何か別の良い手段はありますでしょうか？

引用返信 編集キー/

■18794 / inTopicNo.2)

　Re[1]: 検索処理

▲▼■

□投稿者/ επιστημη (1011回)-(2008/05/16(Fri) 11:59:13)

> std::sortをつかってno順に並び替えた後、2分検索木で探すのが良いかと考えているのですが、
> std::findなど、既に存在する検索アルゴリズムでできないものかと悩んでおります。

sortののちlower_bound/upper_bound/equal_rangeの類使うんじゃダメすか?

引用返信 編集キー/

■18795 / inTopicNo.3)

　Re[1]: 検索処理

▲▼■

□投稿者/ アキラ (39回)-(2008/05/16(Fri) 12:04:52)

私が作ったこれでも使いますか

http://d.hatena.ne.jp/faith_and_brave/20070707/1183744138
http://d.hatena.ne.jp/faith_and_brave/20070709/1183826627

引用返信 編集キー/

■18796 / inTopicNo.4)

　Re[2]: 検索処理

▲▼■

□投稿者/ επιστημη (1012回)-(2008/05/16(Fri) 12:13:23)

> 私が作ったこれでも使いますか

いやいや、O(N)以上に高速な検索をご所望のようですよ。

引用返信 編集キー/

■18801 / inTopicNo.5)

　Re[3]: 検索処理

▲▼■

□投稿者/ セイン (85回)-(2008/05/16(Fri) 13:07:40)

■No18796 (επιστημη さん) に返信
>>私が作ったこれでも使いますか
>
> いやいや、O(N)以上に高速な検索をご所望のようですよ。
>

皆さんありがとうございます。

アキラさんのプログラム非常に使いやすいと思うのですが、頭から最後まで検索するタイプなので、
バブルソートですとか？？ソートと名のつく、ちょっといい検索方法を使えないかなと考えています。

επιστημηさんの教えていただいた関数調べてみますね。

引用返信 編集キー/

■18821 / inTopicNo.6)

　Re[4]: 検索処理

▲▼■

□投稿者/ セイン (86回)-(2008/05/16(Fri) 15:29:05)

自己解決できました。

std::findでやる場合は、比較演算子==をクラスに追加
std::find_ifでやる場合は、比較用の関数を用意し、設定してあげることによって
実現できました。ありがとうございます。

解決済み

引用返信 編集キー/

■18832 / inTopicNo.7)

　Re[5]: 検索処理

▲▼■

□投稿者/ επιστημη (1015回)-(2008/05/16(Fri) 16:43:45)

なんぢゃそらー!?

「高速な方法を考えています」やなかったんかい!?

引用返信 編集キー/

■18851 / inTopicNo.8)

　Re[6]: 検索処理

▲▼■

□投稿者/ セイン (87回)-(2008/05/16(Fri) 18:04:45)

2008/05/16(Fri) 18:11:47 編集(投稿者)

■No18832 (επιστημη さん) に返信
> なんぢゃそらー!?
>
> 「高速な方法を考えています」やなかったんかい!?
>

すいません。勉強不足かもしれないです。
アキラさんがされているのは、ファイルの最初から最後までチェックする方法ですよね？
std::find_ifは2分検索かと思っていたのですが、ちがいますでしょうか？

以下の例題３を参考に、比較用関数を作成し、クラスの一部を比較できるようにして、
std::find_ifを呼ぶようにしてみましたが、いかがでしょうか？
http://www.interq.or.jp/jazz/iijima/stl/contents/find_exam01.html

引用返信 編集キー/

■18859 / inTopicNo.9)

　Re[7]: 検索処理

▲▼■

□投稿者/ επιστημη (1016回)-(2008/05/16(Fri) 19:47:20)

> std::find_ifは2分検索かと思っていたのですが、ちがいますでしょうか？

ちがいます。Predicateがtrueとなる要素を頭からケツまで順に探します。

引用返信 編集キー/

■18862 / inTopicNo.10)

　Re[7]: 検索処理

▲▼■

□投稿者/ アキラ (40回)-(2008/05/16(Fri) 20:58:03)

■No18851 (セインさん) に返信

二分探索は binary_search かな
http://www.geocities.jp/ky_webid/cpp/library/020.html

引用返信 編集キー/

■18863 / inTopicNo.11)

　Re[8]: 検索処理

▲▼■

□投稿者/ 出水 (60回)-(2008/05/16(Fri) 20:58:23)

バブルソートではなく、バイナリーサーチです
そのものずばりのbinary_searchという関数があります

二分検索ことバイナリーサーチってのは、
真ん中を取ってそれより上か下かを判別してある側を探していく、って仕組みです
つまり、大小を比較する物を実装しないとバイナリーサーチは使えないんです

故に、==だけ実装すれば動くfind_ifは、バイナリーサーチではないわけです

引用返信 編集キー/

■18867 / inTopicNo.12)

　Re[8]: 検索処理

▲▼■

□投稿者/ επιστημη (1017回)-(2008/05/16(Fri) 21:22:48)

> 二分探索は binary_search かな

なんだけどぉ、binary_searchは該当要素の有無しか返してくれません。

引用返信 編集キー/

■18957 / inTopicNo.13)

　Re[9]: 検索処理

▲▼■

□投稿者/ セイン (88回)-(2008/05/19(Mon) 08:56:12)

＞出水さん

その通りですね。
==だけだと、大小の比較を行っていませんよね。
考え不足でした。

■No18867 (επιστημη さん) に返信
>>二分探索は binary_search かな
>
> なんだけどぉ、binary_searchは該当要素の有無しか返してくれません。
>

おおおぉ。ご指摘の通り、
binary_searchは有無だけですねぇ＾＾；

こういう検索系を自分で作成すると、デバッグに時間がかかるので、stl系であればうれしかったのですが、
まさか有無しか返していただけないとは・・・。

やはり自分で二分探索書かないとだめなんですかねぇ。

引用返信 編集キー/

■18959 / inTopicNo.14)

　Re[10]: 検索処理

▲▼■

□投稿者/ επιστημη (1022回)-(2008/05/19(Mon) 09:00:16)

2008/05/19(Mon) 09:01:04 編集(投稿者)

> やはり自分で二分探索書かないとだめなんですかねぇ。

だから lower_bound / upper_bound / equal_range だってば

http://episteme.wankuma.com/stlprog/algorithm.html#lower_bound

引用返信 編集キー/

トピック内ページ移動 / << 0 >>

このトピックに書きこむ

過去ログには書き込み不可

- Child Tree -