2

アクション中にすでに処理したインスタンスに関する情報を格納するデータ構造が必要です。制限があるため、インスタンス自体に保存できません（たとえば、アクションを並行して実行できるため）。

具体的には、情報を保存したいインスタンスには一意の番号があるため、インスタンスへのポインターの代わりに、その一意の番号を使用して情報を保存できます。

私の最初の解決策は、を使用することでしたstd::set<Instance *>。インスタンスを処理するたびに、そのインスタンスをセットに追加して、そのインスタンスをすでに処理したことがわかるようにします。

  • 利点：これは初期化が非常に高速です
  • 短所：ルックアップはO（1）ではなく、O（logN）です。

私の2番目の解決策は、std::vector<bool>（実際にはstd::vector<byte>ブールベクトルには非ブールベクトルよりも遅くなる特定の特殊化があるため）を使用することでした。インスタンスの一意の番号は、ベクターへのインデックスとして使用できます。ベクターには、インスタンスを既に処理したかどうかを示すtrueまたはfalseが含まれています（幸い、一意の番号は1からカウントされ始めます）。

  • 利点：ルックアップはO（1）です
  • 短所：std :: vectorはすべての要素を明示的に（そしておそらく独立して）初期化する必要があるため、比較的遅い場合は初期化

Cスタイルの配列（memsetを使用できます）を使用することもできますが、インスタンスの数（または一意の番号の数）が事前にわからないため、配列memsetを拡張するための独自のコードを作成する必要があります配列の残りの部分、...（これはそれほど難しいことではありませんが、避けたいものです）。

初期化が非常に速く、O（1）ルックアップ時間がかかる他の種類のデータ構造はありますか？

4

2 に答える 2

8

boost::unordered_setまたは新しいC++11を試してみてくださいstd::unordered_set。これらは、std :: setのようなツリーではなく、ハッシュベースのコンテナです。

于 2012-04-27T11:45:20.060 に答える
5

さて、そのような単純な識別方法では...私はハッシュテーブルを使用します。

使えないboost::unordered_mapのstd::unordered_map？

もちろん、償却されたO（1）挿入ではなく、保証されたO（1）挿入が必要な場合は、より高度な実装を好むかもしれませんが、それで始められるはずです。

于 2012-04-27T11:46:11.693 に答える