大きなキーを複数のキーで並べ替え、ストアマッピング

Question

私は、複数のキーを持つカスタムパーティクルオブジェクトの大きなstd :: vectorを持っています。それは、50〜250k粒子を含む100MBほどの大きさではありません。

私は、異なる属性などによって、これらの粒子をプロットすることができるようにしたい：...それらの線に沿って気にいら

particle[p].kin_energy/particle[p].mass/particle[p].comet 

。そして、私はこれらのキーで並べ替える必要があります。私のアプリケーションの一部は、計算が終わった後にこれらの粒子をプロットしています。しかし、大規模なベクトルをオンザフライで並べ替えることは、15sek（それは長くなる）を取ることができます。複数のプリソートされたベクトルを別のキーで保存することは、多くのラムを必要とします。

異なる注文を同じベクターにマップする方法はありますか？このようなもの？

pair<position_ordered_by_mass;position_in_original_vector> mass_mapping; 

だから私は、すべての粒子と1つのベクトルを維持し、position_ordered_by_massを反復処理することにより、プロットの横になる粒子を見つけるためにmass_mappingを使用することができます。

これを行うコンテナ、または効率的なアプローチがありますか？

私はboost :: mulimap std :: mapといくつかの他のものを見ましたが、私が探していたものは実際には見つかりませんでした。

Answer 1

があなたのパーティクルオブジェクトのように見える

歓声が（〜420バイト）かなり重いので、代わりにあなただけのあなたの主ベクトル保存する粒子を指すインデックスを格納、複数の異なる事前ソートされた配列をつくことができます。

unsigned intは、これらの250k要素をすべて索引付けするために使用できます。 私の数学が正しければ、それぞれ約7MBにしかならないでしょう。

メインアレイへのアクセスパターンが非ローカルになるため（互いに離れた異なるインデックス間をジャンプする）、キャッシュミスが多く発生しますそれは非常に遅くすることができます。

Answer 2

このアプローチは私にとってうまく機能しました。私はソートされていないベクトルを新しいソートベクターに15sekから約35msまでロードし、さらにマルチスレッド（デュオコア）でロードプロセスを実行します。 428倍速くなります。ヘルプのThx。