私は現在、格子上の物理シミュレーションをコーディングしています。この格子のループを記述することに興味があります。それらは、格子セルのエッジによって構成された閉じた曲線です。この格子セルに関する情報 (情報とは、ループを構成するためにエッジが価値があるかどうかを示すブール変数を意味します) を 3 次元ブール配列に格納しています。
私は今、このループを処理するための適切な構造について考えています。それらは基本的にエッジのリストであるため、3D 整数ベクトルの配列のようなものが必要になります。各エッジは、現在のパラメーター化で 3 つの座標によって定義されます。ループの直径を計算するメソッドが必要になるため、この「リスト」オブジェクトを中心にクラスを構築することをすでに考えています。
しかし、私はそれをしなければならない構造の選択をあまり認識していません.私の物理学のバックグラウンドはC ++で十分に教えてくれませんでした. そのため、このコードを形作るためのあなたの提案を聞きたいです。このようなことをコーディングするいくつかの新しい方法を発見することを本当に楽しみにしています.
2 つの別個のものが必要です。1 つは、すべてのエッジを追跡し、(int,int,int) インデックスによってエッジ オブジェクトを高速に検索できるようにすることです (おそらくそこは必要intありませんが、そのようなものは必要ありませんsize_t)。これは、これらの順序付けられたサブセットを作成する 2 番目のゴールからは完全に独立しています。
エッジ データベースがまばらになるため (つまり、特定のエッジとして実際に識別される可能性のあるインデックスはわずかしかありません)、3 次元マトリックスを使用するという以前の提案は不適切です。代わりに、ハッシュ マップを使用してエッジを検索することをお勧めします。
これがどれほど簡単かは、個々の整数の予想されるサイズによって異なります。つまり、整数あたり 21 ビットを超えないように管理できますか (たとえば、整数がshort int16 ビットしかない値である場合)、それらを 1 つの 64 ビット値に連結できます。これには既にstd::hash実装があります。それ以外の場合は、たとえば、独自のハッシュ特殊化を実装する必要がありますstd::hash<std::array<uint32_t,3>>(これも非常に簡単で、高度にスタック可能です)。
キーをハッシュ化できたら、それを に投げて処理を完了できますstd::unordered_map。そのことは速いです。
次に、ループを識別するための存続期間の短いデータ構造が必要になるため、一方の端では拡張され、他方の端では決して拡張されないデータ構造が必要になります。つまり、インスタンスが非常に大きい場合は、おそらく anstd::vectorまたはおそらく an で問題ないことを意味しstd::dequeます (ただし、最初にベクトルを試してください!)。
インデックスをローカル ベクトルのエッジに維持することをお勧めします。unordered_map でエッジ オブジェクトをいつでも検索できます。次に問題は、インデックスをどのように表現するかです。Int が整数型 (たとえばint、size_t、short、 ...) を表す場合、おそらく最も一貫性があるのは を使用することstd::array<Int,3>です --- 整数の型が異なる場合は、std::tuple<...>.