7

私は最近、boost とそれがコンテナーであることに関心を持ち始めたばかりであり、web と stackoverflow で、boost::unordered_map が大きなコレクションの最速のコンテナーであるという記事をいくつか読みました。したがって、私はこのクラス State を持っています。これはコンテナー内で一意でなければならず (重複はありません)、コンテナーには数十億ではないにしても数百万の状態が存在します。そのため、サイズを小さくし、計算をできるだけ少なくするように最適化しようとしています。以前はboost::ptr_vectorを使用していましたが、stackoverflowで読んだように、ベクターはオブジェクトがそれほど多くない場合にのみ有効です。私の場合、状態はロボットからの感覚運動情報を記述するため、膨大な量の状態が存在する可能性があるため、高速検索が最優先事項です。ブーストのドキュメントに従うunordered_map については、高速化するためにできることが 2 つあります。hash_function を使用し、等値演算子を使用して、hash_function に基づいて状態を比較します。そこで、ステート情報を取り込み、boost::hash_combine を使用して std::size_t ハッシュ値を作成するプライベート hash() 関数を実装しました。operator== は、基本的に状態のハッシュ値を比較します。そう：

  • std::size_t は、数十億の可能性のある hash_function の組み合わせをカバーするのに十分ですか? 状態の重複を避けるために、hash_values を使用するつもりです。

  • state_map を作成するとき、State* またはハッシュ値をキーとして使用する必要がありますか? すなわち:boost::unordered_map<State*,std::size_t> state_map; または boost::unordered_map<std::size_t,State*> state_map;

  • boost::unordered_map::iterator = state_map.find() を使用したルックアップ時間は、boost::ptr_vector を通過して各反復子のキー値を比較するよりも高速ですか?

  • 最後に、このような順序付けられていないマップを最適化して速度と高速ルックアップを実現する方法に関するヒントやコツを教えていただければ幸いです。

編集:私はかなりの数の答えを見てきました.1つはブーストを使用せずにC ++ 0X、もう1つはunordered_setを使用しないことですが、正直に言うと、boost::unordered_setがハッシュ関数でどのように使用されるかをまだ知りたいです. ブーストのドキュメントに従って実装しましたが、順序付きセットでブーストのハッシュ関数を使用する方法がまだわかりません。

4

3 に答える 3

4

これは少し混乱しています。

  • あなたの言うことは、「物事をスピードアップするためにできること」ではありません。むしろ、順序付けされていないマップの要素型として、また順序付けられていないセット (むしろ必要な場合があります) として適格であるために、型が必須の要件です。

  • ハッシュ値ではなく、オブジェクトを比較する等値演算子を提供する必要があります。等価性の要点は、同じハッシュを持つ要素を区別することです。

  • size_tx86 では 32 ビット、x64 では 64 ビットの符号なし整数型です。「数十億の要素」、つまり数ギガバイトのデータが必要なので、とにかく堅実な x64 マシンを持っていると思います。

  • 重要なのは、ハッシュ関数が優れていることです。つまり、衝突がほとんどないことです。

  • マップではなく、セットが必要です。オブジェクトをセットに直接入れます: std::unordered_set<State>. 何かにマッピングする場合、つまり状態を別のものにマッピングする場合は、マップを使用します。できれば、Boost ではなく C++0x を使用してください。

  • 使い心地hash_combineは良いです。

赤ちゃんの例:

struct State
{
  inline bool operator==(const State &) const;
  /* Stuff */
};

namespace std
{
  template <> struct hash<State>
  {
    inline std::size_t operator()(const State & s) const
    {
      /* your hash algorithm here */
    }
  };
}

std::size_t Foo(const State & s) { /* some code */ }

int main()
{
  std::unordered_set<State> states; // no extra data needed
  std::unordered_set<State, Foo> states; // another hash function
}
于 2011-07-14T00:30:52.320 に答える
2

ハッシュを忘れてください。意味のあるキーを持っていることを示唆するものは（少なくともあなたの質問からは）ありません。

一歩下がって、実際のパフォーマンス目標を言い換えてみましょう。

  • State オブジェクトのいずれにも重複が存在しないことをすばやく検証したい

他の人を追加する必要がある場合はコメントしてください。

前述の目標とあなたのコメントから、実際にはunordered_mapではなく、 ordered_setを使用することをお勧めします。はい、順序付き検索はバイナリ検索 O(log (n)) を使用し、順序なし検索はルックアップ O(1) を使用します。

ただし、違いは、このアプローチでは、新しいものを作成しようとしているとき、つまり State creation-time のときに、類似の状態がまだ存在しないことを確認するためだけに、 ordered_setが必要であるということです。

他のすべてのルックアップでは、実際には、ordered_set を調べる必要はありません! あなたはすでに鍵を持っているからです。State* であり、キーは魔法の間接参照演算子によって値にアクセスできます: *key

したがって、このアプローチでは、ordered_set をインデックスとして使用して、作成時にのみ状態を確認します。それ以外の場合はすべて、ポインター値キーの逆参照演算子を使用して State にアクセスします。

上記のすべてがあなたを納得させるのに十分でない場合は、ハッシュを使用して同等性を迅速に判断するというアイデアの棺桶の最後の釘を次に示します。ハッシュ関数は衝突の確率が小さいですが、状態の数が増えるにつれて、その確率は完全に確実になります。したがって、耐障害性に応じて、状態の衝突に対処することになります (そして、質問と対処する予定の状態の数から、多くの状態に対処するようです)

これが機能するには、状態のすべての内部プロパティ (ジャイロスコープ、スラスター、加速度計、陽子線など) をテストするための比較述語が明らかに必要です。

于 2011-07-14T01:03:05.083 に答える
2

unordered_map はハッシュテーブルです。ハッシュを保存しません。これは、ストレージおよび検索方法として内部的に行われます。

オブジェクトが保存する唯一のアイテムであるため、要件を考えると、 unordered_set の方が適切な場合があります。

少し混乱していますが、等値演算子とハッシュ関数は真のパフォーマンス項目ではありませんが、コンテナーが正しく機能するために重要なオブジェクトに必要です。適切なハッシュ関数はノードをバケット全体に均等に分散し、ハッシュ関数に基づいて一致に関するあいまいさを取り除くために等値演算子が使用されます。

std::size_t はハッシュ関数に適しています。完全なハッシュはありません。衝突が発生し、これらの衝突項目はそのバケット位置のリンク リストに保存されます。

したがって、 .find() は、最適なケースでは O(1) になり、平均的なケースでは O(1) に非常に近くなります (最悪のケースでは O(N) ですが、まともなハッシュ関数はそれを回避します)。

プラットフォームやアーキテクチャについては言及していません。数十億のエントリでは、それらと State オブジェクトのサイズによっては、メモリ不足の状況について心配する必要がある場合があります。

于 2011-07-14T00:28:56.220 に答える