7

パラメータ位置に適切な値を指定することにより、の効率をmap::insert(iterator position, const value& k)劇的に向上させることができます。

キーとして整数を使用し、すべての挿入が以前に挿入されたすべてのキーよりも大きい数で行われる場合、マップのイテレーターを指定::insertするときに操作を高速化できますか？::end()

何かのようなもの：

myMap.insert( myMap.end() , make_pair( next_number , myValue ) );

ここmyMapで、はタイプmap<uint64_t,MyType>でnext_numberあり、すべて増分する大きな整数です。

編集：

この質問に対する答えは、に格納されているデータmapが密集しているかどうかによって異なる場合があります（以下の説明を参照）。それでは、両方の方法で質問してみましょう。密度が高い場合は密度が高くない場合です。まだ好奇心が強い。おそらく測定はそれに答えるでしょう。

4

4 に答える 4

4

尋ねられた質問に直接答えるために、C++の仕様は次のように述べています。

  • C ++ 03では、の直後に挿入する場合a.insert(p,t)、マップへの挿入は（対数ではなく）一定の複雑さで償却する必要があります。t p
  • C ++ 11では、がの直前に挿入されたa.insert(p,t)場合、マップへの挿入は一定の複雑さで償却する必要があります。t p

どちらの場合も、p参照解除可能である必要はありません。したがって、あなたの場合、a.end()C ++ 11では最良のヒントになる可能性がありますが、C++03ではそうではありません。

于 2012-06-04T23:33:14.123 に答える
2

私は2つのことを提案します：

  • この場合、常にstd::unordered_map一方の端に挿入することは、赤黒木にとって最悪のシナリオです。
  • 面倒であることが判明した場合は、カスタムアロケータを使用しnewてください。あなたが話していることから、プール割り当て戦略を使用できます。

C ++ 11ではステートフルアロケータを使用できるため、適切で内部に埋め込まれたアロケータを提供しstd::vector<T>てスタックとして使用するのは簡単です。

于 2012-06-05T07:15:45.393 に答える
1

提案は単なる提案であり、試して測定するものです。挿入を行うための最もパフォーマンスの高い方法を実際にお伝えすることはできません。独自の特定のユース ケースを測定し、最適なものを確認する必要があります。

マップがコンパクトで密集しており (0 から最大キーまでのほとんどすべての項目が実際のデータで占められている)、最大キーが適切な配列インデックスになるのに十分なほど小さい場合は、a を使用しstd::vector<value>て常に末尾に挿入するように切り替えることができます。常に成長しているため、ベクターを再割り当てする必要がある場合があります (通常、これはベクターが 2 倍になる場合です)。これは高価になる可能性がありますが、一般的に挿入は非常に安価です。バイナリ ツリーの潜在的なリバランスに対処する必要はなく、ベクターは他の目的で非常にキャッシュ フレンドリーです。

マップのキー空間がコンパクト/高密度ではなく、最大キーが大きすぎてメモリへのインデックスが考えられない場合は、ヒントを使用した挿入が最善の策になります。

順序が重要でない場合は、std::unordered_mapを試すことができます。これはハッシュ テーブルの実装です。したがって、挿入コストはハッシュの品質と速度に関係します。64 ビット キーを取得して size_t ハッシュに変換するのは簡単で高速です (size_t は 64 ビットの場合もあります)。

しかし、私の言葉を鵜呑みにする必要はありません。測定して、自分の目で確かめてください...

于 2012-06-04T22:52:22.927 に答える