22

私はを使用してmap<MyStruct, I*> map1;います。どうやら私の総アプリ時間の9％がそこで費やされています。具体的には、私の主要な機能の1つの1行にあります。マップはそれほど大きくありません（ほとんどの場合<1k、<20が一般的です）。

使用したい代替実装はありますか？自分で書くべきではないと思いますが、いいアイデアだと思ったらできます。

追加情報：要素を追加する前に常に確認します。キーが存在する場合は、問題を報告する必要があります。ポイントの後よりも、ルックアップにマップを多用し、要素を追加しません。

4

7 に答える 7

56

最初に、マップとは何か、そして実行している操作が何を表しているのかを理解する必要があります。Astd::mapはバランスの取れたバイナリ ツリーです。ルックアップには操作が必要O( log N )です。各操作は、キーの比較と、ほとんどの場合無視できる余分な操作 (ポインター管理) です。挿入は、挿入ポイントの特定と、新しいノードの割り当て、ツリーへの実際の挿入、および再調整にほぼ同じ時間がかかります。O( log N )隠された定数はより高くなりますが、複雑さは再びです。

挿入前にキーがマップにあるかどうかを判断しようとすると、ルックアップのコストが発生し、成功しない場合は、挿入ポイントを見つけるために同じコストが発生します。iterator と bool のペアを返すことで、追加のコストを回避できstd::map::insertます。これは、挿入が実際に行われたか、要素が既にそこにあったかを示します。

それを超えて、キーを比較するのがどれほどコストがかかるかを理解する必要があります。これは、質問が示すものから外れます ( MyStruct1 つまたは 1000 個のキーしか保持できない可能性がintあります)。これは、考慮に入れる必要があるものです。

最後に、 amapがニーズにとって最も効率的なデータ構造ではない場合があり、std::unordered_map一定時間の挿入が予想される (ハッシュテーブル) (ハッシュ関数が恐ろしいものでない場合) または単純な順序付けられた配列 (またはstd::vector) でさえ、バイナリ検索を使用して要素を見つけることができる小さなデータ セット (これにより、より高価な挿入を犠牲にして、割り当ての数が減りますが、保持されている型が十分に小さい場合は、価値がある）

パフォーマンスの場合と同様に、測定してから、どこに時間が費やされているかを理解しようとします。また、アプリケーションの内容によっては、特定の関数またはデータ構造に費やされる時間の 10% は、多くの場合もほとんどない場合もあることに注意してください。たとえば、アプリケーションがルックアップとデータ セットへの挿入を実行するだけで、CPU の 10% しか使用しない場合、他のすべての部分を最適化する必要があります。

于 2012-04-15T20:43:24.113 に答える
10

おそらく、キーが既に存在するかどうかを実行しinsertて確認する方が速いでしょう：pair.secondfalse

このような

if ( myMap.insert( make_pair( MyStruct, I* ) ).second == false)
{
  // report error
}
else
  // inserted new value

find...毎回電話をかけるのではなく。

于 2012-04-15T20:27:16.733 に答える
7

代わりに、ツリーの代わりにハッシュキーを使用して要素を見つけることができますmap。この回答は、より優先する場合にいくつかのヒントを提供します。unordered_mapunordered_mapmap

于 2012-04-15T20:34:51.333 に答える
5

長い道のりかもしれませんが、小さなコレクションの場合、最も重要な要素がキャッシュのパフォーマンスである場合があります。

std::map[AFAIK]はあまりキャッシュ効率が良くない赤黒木を実装しているので、おそらくマップを実装するのstd::vector<pair<MyStruct,I*>>は良い考えであり、[マップルックアップの代わりに]そこでバイナリ検索を使用します。少なくともそれははstd::vector、よりもキャッシュに収まる可能性が高いため、[要素の挿入を停止]のみを検索し始めたら効率的ですmap。

この係数[cpu-cache]は通常無視され、大きなO表記では定数として隠されますが、大きなコレクションの場合は大きな影響を与える可能性があります。

于 2012-04-15T20:30:53.847 に答える
2

マップを使用している方法では、インスタンスに基づいてルックアップを行ってMyStructおり、特定の実装によっては、必要な比較にコストがかかる場合とそうでない場合があります。

于 2012-04-15T20:27:48.043 に答える
1

使用したい代替実装はありますか？自分で書くべきではないと思いますが、いいアイデアだと思ったらできます。

問題を十分に理解している場合は、実装がどのように優れているかを詳しく説明する必要があります。

map適切な構造ですか？その場合、標準ライブラリの実装は高品質（十分に最適化されている）である可能性があります。

MyStruct比較を簡略化できますか？

問題はどこにありますか？サイズ変更ですか？見上げる？

構造のコピーと割り当てのコストを最小限に抑えましたか？

于 2012-04-15T20:32:42.143 に答える
1

コメントで述べたように、適切なコードがなければ、普遍的な答えはほとんどありません。ただし、MyStructが非常に大きい場合、スタックのコピーにコストがかかる場合があります。MyStructおそらく、独自の比較メカニズムへのポインターを格納して実装することは理にかなっています。

template <typename T> struct deref_cmp {
  bool operator()(std::shared_ptr<T> lhs, std::shared_ptr<T> rhs) const {
    return *lhs < *rhs;
  }
};

std::map<std::shared_ptr<MyStruct>, I*, deref_cmp<MyStruct>> mymap;

ただし、これはプロファイルする必要があるものです。それは物事をスピードアップするかもしれません。

このような要素を検索します

template <typename T> struct NullDeleter {
  void operator()(T const*) const {}
};
// needle being a MyStruct
mymap.find(std::shared_ptr<MyStruct>(&needle,NullDeleter()));

言うまでもなく、最適化できる可能性はもっとあります。

于 2012-04-15T20:45:05.633 に答える