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)
επιστημη さんの Web サイト
> ■線形検索    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)
επιστημη さんの Web サイト
> もしかして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)
επιστημη さんの Web サイト
> 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 -