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

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

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

Re[6]: STL　Algorithm　の検索メソッドについて

(過去ログ 68 を表示中)

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

■39356 / inTopicNo.1)

　STL　Algorithm　の検索メソッドについて

▼■

□投稿者/ ふくちゃん (43回)-(2009/08/06(Thu) 13:13:59)

分類:[C/C++]　

STL　Algorithm　の検索メソッドについてお伺いします。

■線形検索　　　　std::find
■二分探索　　　　std::lower_bound
■ハッシュ探索　　std::map

と理解していたのですが、
std:mapも二分探索という情報もあり、何が正しいのかわからなくなってしまいました。

またstd::lower_boundとstd::mapですと、mapのほうが圧倒的に早いです。

同じ二分探索だとすると、このスピードの差はなんなのでしょうか？

以上よろしくお願いします。

引用返信 編集キー/

■39358 / inTopicNo.2)

　Re[1]: STL　Algorithm　の検索メソッドについて

▲▼■

□投稿者/ επιστημη (2084回)-(2009/08/06(Thu) 13:24:28)

> ■線形検索　　　　std::find
> ■二分探索　　　　std::lower_bound
> ■ハッシュ探索　　std::map

std::mapは二分木です。

> またstd::lower_boundとstd::mapですと、mapのほうが圧倒的に早いです。
> 同じ二分探索だとすると、このスピードの差はなんなのでしょうか？

std::lower_boundは二つのイテレータによるはさみうち、
std::map::find は二分木を根から辿ります

std::lower_boundのスピードは「何に対して」適用したかで大きく変わるでしょう。
イテレータの移動速度に依存しますから。

引用返信 編集キー/

■39360 / inTopicNo.3)

　Re[2]: STL　Algorithm　の検索メソッドについて

▲▼■

□投稿者/ ふくちゃん (45回)-(2009/08/06(Thu) 13:27:25)

あ！
もしかしてmapってデータを入れていくときに、
すでに2分探索用のツリー型で格納されていってるのですか？

左と右の枝を見て自分より大きければ右の枝小さければ左の枝
枝が端末ならそこに格納～みたいなやりかたで？

■No39358 (επιστημη さん) に返信
>>■線形検索　　　　std::find
>>■二分探索　　　　std::lower_bound
>>■ハッシュ探索　　std::map
>
> std::mapは二分木です。
>
>>またstd::lower_boundとstd::mapですと、mapのほうが圧倒的に早いです。
>>同じ二分探索だとすると、このスピードの差はなんなのでしょうか？
>
> std::lower_boundは二つのイテレータによるはさみうち、
> std::map::find は二分木を根から辿ります
>
> std::lower_boundのスピードは「何に対して」適用したかで大きく変わるでしょう。
> イテレータの移動速度に依存しますから。
>

引用返信 編集キー/

■39361 / inTopicNo.4)

　Re[3]: STL　Algorithm　の検索メソッドについて

▲▼■

□投稿者/ επιστημη (2085回)-(2009/08/06(Thu) 13:30:36)

> もしかしてmapってデータを入れていくときに、
> すでに2分探索用のツリー型で格納されていってるのですか？
>
> 左と右の枝を見て自分より大きければ右の枝小さければ左の枝
> 枝が端末ならそこに格納～みたいなやりかたで？

そです。言語規格書には実装については一言も言及していませんが、
事実上mapは二分木(赤黒木)で実装されたものがほとんどです。

引用返信 編集キー/

■39362 / inTopicNo.5)

　Re[4]: STL　Algorithm　の検索メソッドについて

▲▼■

□投稿者/ ふくちゃん (46回)-(2009/08/06(Thu) 13:44:03)

■No39361 (επιστημη さん) に返信
>>もしかしてmapってデータを入れていくときに、
>>すでに2分探索用のツリー型で格納されていってるのですか？
>>
>>左と右の枝を見て自分より大きければ右の枝小さければ左の枝
>>枝が端末ならそこに格納～みたいなやりかたで？
>
> そです。言語規格書には実装については一言も言及していませんが、
> 事実上mapは二分木(赤黒木)で実装されたものがほとんどです。
>

なるほど！
2分探索木より高性能な赤黒木をつかってるんですか。

すごく理解しました。
ということはですね。
同じ2分探索という概念は使っているものの、

std::lower_bound は 2分探索
http://ja.wikipedia.org/wiki/%E4%BA%8C%E5%88%86%E6%8E%A2%E7%B4%A2

std::map　は　赤黒木
http://ja.wikipedia.org/wiki/%E8%B5%A4%E9%BB%92%E6%9C%A8

という分類が厳密で、
>>言語規格書には実装については一言も言及していません
ということなので正確かどうかはさておき

std::lower_boundは木の作成がいらないのでvector構造のままで扱えて、
std::map　は赤黒木用にデータを持つ必要があるので、vector構造のままでは扱えないんですね。

ただ赤黒木を作ること自体にそれなりに時間がかかるので、
何でもかんでもstd::map型で定義するのではなく、
事前に検索の頻度を考えて、どんなデータ型で持っておくかが重要ですね。?

引用返信 編集キー/

■39364 / inTopicNo.6)

　Re[5]: STL　Algorithm　の検索メソッドについて

▲▼■

□投稿者/ επιστημη (2086回)-(2009/08/06(Thu) 14:42:20)

> 2分探索木より高性能な赤黒木をつかってるんですか。

赤黒木は二分探索木の一種(バリエーション)です。
葉の深さがなるべく浅くなるように調整されます。

> std::lower_boundは木の作成がいらないのでvector構造のままで扱えて、
> std::map　は赤黒木用にデータを持つ必要があるので、vector構造のままでは扱えないんですね。

ですね。mapの腹ん中にあるのはvectorではありません。

> ただ赤黒木を作ること自体にそれなりに時間がかかるので、
> 何でもかんでもstd::map型で定義するのではなく、
> 事前に検索の頻度を考えて、どんなデータ型で持っておくかが重要ですね。?

ですね。C++0x(TR1)ではハッシュ表 unordered_set/unordered_map/etc. も提供されます。

引用返信 編集キー/

■39501 / inTopicNo.7)

　Re[6]: STL　Algorithm　の検索メソッドについて

▲▼■

□投稿者/ ふくちゃん (47回)-(2009/08/10(Mon) 09:35:00)

ばっちり理解できました。

土日を挟んでしまい申し訳ございません。

最後の確認まで付き合っていただき、ありがとうございました。

■No39364 (επιστημη さん) に返信
>>2分探索木より高性能な赤黒木をつかってるんですか。
>
> 赤黒木は二分探索木の一種(バリエーション)です。
> 葉の深さがなるべく浅くなるように調整されます。
>
>>std::lower_boundは木の作成がいらないのでvector構造のままで扱えて、
>>std::map　は赤黒木用にデータを持つ必要があるので、vector構造のままでは扱えないんですね。
>
> ですね。mapの腹ん中にあるのはvectorではありません。
>
>>ただ赤黒木を作ること自体にそれなりに時間がかかるので、
>>何でもかんでもstd::map型で定義するのではなく、
>>事前に検索の頻度を考えて、どんなデータ型で持っておくかが重要ですね。?
>
> ですね。C++0x(TR1)ではハッシュ表 unordered_set/unordered_map/etc. も提供されます。
>

解決済み

引用返信 編集キー/

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

このトピックに書きこむ

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

- Child Tree -

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

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

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

Re[6]: STL Algorithm の検索メソッドについて

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

Re[6]: STL　Algorithm　の検索メソッドについて