c++ - STL::Map - リストをウォークスルーするか、検索を使用しますか?

Question

100 個の要素を含むマップから 8 つの値を取得する必要があるメソッドがあるとします。どちらが望ましいと思いますか:

for ループを最初から最後まで 1 回歩き、キーをオンにして要素を引き出しますか?

または、find 8 回を使用してそれらの値を取得しますか?

score 9 · Accepted Answer

リストを歩くと、ランダムな要素を見つけるのにO（n）時間がかかります。

マップは平衡二分木であるため、検索を行うのはO（log n）です。

したがって、8を実行すると、結果は8 * log2（n）になり、リストをたどると（n）になります。リストが大きいほど、ゲインは大きくなりますが、すべてのランダムなケースで、反復を実行するよりも検索を実行する方が高速になります。

ランダムでない場合、必要なアイテムがツリー内で互いに近くにあるか、「開始」（左側）の近くにあることに理由がある場合は、ウォーキング/反復が速くなります。しかし、それはありそうもないようです。

score 5 · Accepted Answer

私はこのfindオプションを選択しますが、人々は漸近的なパフォーマンスを重視しすぎます。

実際、漸近的なパフォーマンスは、かなり大きな入力を受け取ることができるアルゴリズムの便利なガイドですが、それでも絶対確実というわけではありません。漸近性能が他のアルゴリズムよりも悪いアルゴリズムが、妥当な入力に対してより高速になる可能性は十分にあります。

また、入力サイズがかなり小さい (または固定されている) ことがわかっている場合もあります。このような場合、漸近的なパフォーマンスはほとんど意味がありません。

score 3 · Accepted Answer

私は8回検索を使用します。それはより少ない（そしてより明白な）コードになります。

（a）このサイズではどちらの方法でもパフォーマンスのボトルネックになる可能性は低く、（b）数値は将来変更される可能性があるため、小さい数値に基づいてパフォーマンスを判断しないようにしてください。最適な漸近的なアルゴリズムを選択してください。パフォーマンス。

注：キーの「切り替え」について言及しています...これはあなたの場合に当てはまるかもしれませんが、一般的にはマップのキー値を切り替えることはできません。これを許可すると、反復によってマップ内のM個のアイテムを検索するコードがさらに複雑になります。

score 1 · Accepted Answer

他の人が指摘したように、私はおそらく、マップ上で find() を 8 回使用するだけで完了します。ただし、ニーズに応じて検討する別の方法があります。マップの構築後にマップ内のアイテムがあまり変更されない場合、またはルックアップで挿入をインターリーブする必要がない場合は、キーと値のペアを並べ替えられたベクトルに保持してみてください。これを行うと、lower_bound() 関数を使用して、対数時間でバイナリ検索を実行できます。これには、探しているキーを順序付けできる場合 (そしてそれらが常に存在することがわかっている場合)、前のルックアップから返された反復子を次の下限として使用できるという利点があります。例えば、

vector::iterator a = my_map.lower_bound( my_map.begin(), my_map.end(), "a" );
vector::iterator b = my_map.lower_bound( a + 1, my_map.end(), "b" );
vector::iterator c = my_map.lower_bound( b + 1, my_map.end(), "c" );
// ...

どちらのアプローチにも対数ルックアップがありますが、これは定数をいくらか減らすのに役立ちます。

score 1 · Accepted Answer

コードがよりシンプルで明確になるため、8 つの検索結果が最適です。

でも、パフォーマンスを考えるほうが楽しいので、それもやります。

この回答を書いているときにアルテリウスが言ったように、複雑さは無視してください。n=100 とわかっているので関係ありません。たとえば、挿入ソートは (少なくとも平均的なケースでは) クイックソートよりもアルゴリズムの複雑さが劣りますが、ほとんどすべての実装では、n が小さい場合は挿入ソートの方がクイックソートよりも高速であるため、クイックソートは最後に挿入ソートに分岐します。あなたの n も小さいので、 n -> 無限大という制限は重要ではありません。

両方のオプションのコードは簡単に記述できるので、プロファイリングすることをお勧めします。これは、(a) どちらが速いかを示し、(b) 両方が非常に高速であるため、どちらを実行しても問題がないことを証明します (ただし、それがプログラムで実行される唯一のことであり、頻繁に実行される場合を除きます)。特にキーの切り替えについて話しているので、キーが整数型の場合、制限要因は実際の処理よりもメモリキャッシュの問題である可能性が高くなります。

ただし、それができない場合、通常、検索アルゴリズムを比較する方法は、構造をトラバースするよりもはるかに遅いと仮定して、比較をカウントすることです。何よりも、各比較はメモリにアクセスし、予測不可能な分岐です。これは、CPU が最も苦手とする 2 つの点です。

提案するスイッチの代わりに、開始前に 8 つの要素を並べ替えると (24 回程度の比較が必要になります)、マップも並べ替えられるため、トラバースする各ノードで 1 回の比較と、アイテムごとに 1 回の比較を行うだけで済みます。を探しています (各「サイド」から 1 つのノードを比較します。一致する場合は、両方のサイドをインクリメントします。一致しない場合は、小さい方の要素でサイドをインクリメントします)。つまり、最悪の場合は 8+100 であり、最後にたどり着く前に 8 つすべてを見つけた場合はそれ以下になります。しかし、最後の 8 人の平均位置は、それらがマップ内でランダムに配置されている場合でも、8/9 のようなものです。したがって、これを 8+88+24 = 120 回の比較と呼び、132 回を最悪のケースとします。最良のケースは 8 (探しているものがすべて先頭にある場合) +24 (最初の並べ替えの場合) = 32 回の比較です。

赤黒木 (マップは通常) のノードの平均深さは、log2(n) をわずかに上回ります。2^7 は 128 であるため、この場合は 7 と呼びます。したがって、8 つの要素を見つけるには 56 回の比較が必要です。IIRC 赤黒木のバランス特性は、最も深いノードが最も浅いノードの深さの 2 倍以下であることです。したがって、最悪の場合の深さは floor(2*log2(n)) で、これを 15 と呼び、合計で 120 になります。最高の深さは ceil(1/2 log2(n)) で、これは 4 です。これも 32 回の比較です。

したがって、比較が速度に影響を与える唯一のものであると仮定すると、8 つの検索は、線形トラバーサルの 4 倍速く、4 倍遅く、平均で 2 倍優れています。

ただし、線形トラバーサルはおそらくより多くのメモリに触れるため、そのために遅くなる可能性があります。しかし、最終的に n=100 の場合、ミリ秒単位で話しているので、最も単純なコード (おそらく 8 つの検索結果) を実行してください。そして、予測できない速度を本当に知りたい場合は、それをプロファイリングする必要があると言いましたか?

score 0 · Accepted Answer

これらの時間計算量の分析は次のとおりです（nはマップ内のアイテム数です）。これは、対数以上の時間計算量で検索を検索することが保証されています。

8 * log2n8回検索
nすべてを反復する

最初のものは数値が小さいほど大きくなりますが（たとえば、n = 2の場合は8）、43前後で、最初のものは2番目のものよりも良くなり、そのままになります。したがって、コーディングの方が便利であるため、最初の方法を使用することをお勧めします。

score 0 · Accepted Answer

findを8回使用する必要があります。

スイッチアプローチは、各ノードを8回比較するものと考えてください。これは800の比較であり、キーが設定されているマップのすべての利点が失われます。リストである可能性もあります。

検索アプローチでは、マップの利点を使用してリストをトラバースします。std :: マップはバイナリツリーとして実装されていると思います。つまり、キーを検索するには、キーをツリーの深さまで比較するだけで済みます。これは、100要素のバイナリツリーの場合は8〜になります。これで、8 * 8の比較、または64の比較だけで8つの要素すべてを見つけることができます。

score 0 · Accepted Answer

それほど重要な場合は、両方を実装してパフォーマンスをベンチマークします。

理論的には

8 * lg(100) >?< 100

その他の考慮事項は、これらの数のいずれかが変更されるかどうかです。100 要素を超えることはありますか。8 回以上検索することはありますか?

score -1 · Accepted Answer

キーを見つけたときに「見つける」ベイルを想定しましょう。

さらに、「スイッチ」を賢明にコーディングし、一致が見つかった後にチェックを終了すると仮定しましょう。また、8 つすべてが見つかったら、プロセス全体を救済するためにわざわざコーディングしないと仮定します(コーディングするのはおそらく面倒です)。

「8 個の検索」アプローチでは、(iow: 平均で) 50 * 8 = 400 回の比較を実行することが期待できます。

「切り替え」アプローチでは、(iow: 平均) が (8 * 100) - 28 = 772 回の比較を実行することが期待できます。

したがって、比較に関しては、8 つの検索結果のアプローチの方が優れています。ただし、比較の数は十分に少ないため、理解しやすいオプションを選択した方がよいでしょう。それもおそらく8つの検索アプローチになるでしょう。

c++ - STL::Map - リストをウォークスルーするか、検索を使用しますか?

9 に答える 9

Related

Reference