Boost Multi-Indexとlookupsを含むC ++コードをoderd_multimapにスピードアップする必要があります
-
24-10-2019 - |
質問
クラスのオブジェクトに基づいたエージェントベースのモデルをスピードアップする戦略を探しています Host
, 、ブーストマルチインデックスコンテナに保管されるポインター。私はサメを使用して、大部分の時間が関数によって消費されていると判断しました calcSI()
:
関数 calcSI()
クラスのすべてのインスタンスを計算する必要があります Host
クラスの他のインスタンスの属性に依存する特定の確率 Host
. 。 (約10,000〜50,000のインスタンスがあります Host
, 、およびこれらの計算は、各ホストに対して約25,600回実行されます。)
プロファイルを正しく解釈している場合、に費やした時間の大部分は calcSI()
に行く Host::isInfectedZ(int)
, 、それは単に何かのインスタンスをboost unordered_multimapのタイプでカウントするだけです InfectionMap
:
struct Infection {
public:
explicit Infection( double it, double rt ) : infT( it ), recT( rt ) {}
double infT;
double recT;
};
typedef boost::unordered_multimap< int, Infection > InfectionMap;
のすべてのメンバー Host
含む InfectionMap carriage
, 、 と Host::isInfectedZ(int)
の数をカウントするだけです Infections
特定に関連付けられています int
鍵:
int Host::isInfectedZ( int z ) const {
return carriage.count( z );
}
私はどれほど高価であるかについての情報を見つけるのに苦労しています
count
機能は、Boostの順序付けられていないマルチマップ用です。追加することでオーバーヘッドを増やす必要がありますHost
各キーのインスタンスの数を追跡するための別の2次元配列(つまり、の数Infections
それぞれに関連付けられていますint
)?ブーストマルチインデックスのより大きな構造的オーバーホールが、1つまたは2つの必要のない複合キーインデックスを排除するなど、より役立つかどうか疑問に思っています。マルチインデックスのバックグラウンドメンテナンスは、プロファイラーに表示されません。 Multi-Indexには8つのインデックスがあり、そのほとんどはOrdered_non_uniqueです。
プロファイラーに表示されない可能性のあるものに関心があるべきことがありますか、それともプロファイラーの大きな結果がありませんか?
の並列化とマルチスレッド calcSI()
残念ながらオプションではありません。
アップデート: それを知るのに役立つかもしれません InfectionMap carriage
めったに10ペアを超えることはなく、通常は5未満です。
更新2: 上記の#1で提案された戦略を試してみました。 Host
配列 int carriageSummary[ INIT_NUM_STYPES ]
, 、可能な値によってインデックスが付けられます z
(ほとんどのシミュレーションでは、可能な値が10未満です)。各エントリの値は、に作成された変更を追跡します carriage
. 。 Host::isInfectedZ( int z )
関数が読み取ります:
int Host::isInfectedZ( int z ) const {
//return carriage.count( z );
return carriageSummary[ z ];
}
そして、この機能に専念する時間 表示されます 実質的にドロップしたこと - 私は今正確な比較をすることはできません:
明らかに、アレイを使用することはかさばるのですが、の小さな範囲では大丈夫です z
. 。他のコンテナ(つまり、順序付けされていない_mapではなく)は、より大きな範囲により効率的になりますか?
マルチインデックスの変更に関するフィードバックも大好きです。
解決
#1で提案したように、ホスト::キャリッジUNORDERED_MULTIMAPの横にあるキャリッジカウントアレイを維持して、両方の「同期」に保ちます。ホスト:: isInfectuedzは、(できれば)より速いキャリッジカウントアレイを使用します。
int Host::isInfectedZ( int z ) const {
return carriageCount[ z ];
}
ISInfectedに渡すことができる整数の範囲が大きい場合は、キャリッジ数に連想配列を使用します。
STD :: MAPまたはBOOST :: UNORDEREDを連想配列に使用できます。ルックアップの場合、前者は対数的な時間的複雑さを持ち、後者は一定の時間的複雑さを持っています。しかし、この連想配列は通常非常に小さいため、STD :: MAPは実際には高速になる可能性があります。 STD :: MAPは、頭上のスペースが少ない場合もあります。両方を試して、プロファイラーを実行して確認してください。私の賭けはstd :: mapにあります。 :-)
編集:
私のコメントに対するあなたの答えを見てみると、キャリッジ数に通常の固定サイズ配列を使用することをお勧めします。連想配列のものを忘れてください。
編集2:
スクラップしたいかもしれません
typedef boost::unordered_multimap< int, Infection > InfectionMap;
そして、あなたはそのような小さな指標を扱っているので、あなた自身の手書きの感染症のクラスをロールアップします。
更新#2への応答:
あなたが改善したのを見てうれしいです。たとえば、16の整数の固定配列よりも「かさばる」コンテナが見つかるとは思いません。 STLおよびブーストコンテナは、メモリをチャンクに割り当て、要素がほとんどない場合でも、固定サイズのアレイと同じ大きさになります。
Boost :: Arrayに興味があるかもしれません。これは、Cスタイルの固定配列の周りにSTLのようなインターフェイスをラップします。これにより、STD :: VectorまたはSTD :: MAPの固定サイズアレイを「スワップアウト」しやすくなります。