速度が非常に重要な科学プロジェクト (HPC) に取り組み始めたところです。現在、データ構造を設計しています。プロジェクトの中核は、偏微分方程式を解くための double 値の 3D グリッドです。
ここでの速度はおそらくコードの単純さよりも大きな懸念事項であるため、STL が通常の C スタイルの配列と比較してどのように機能するかを知りたいと思います。私の場合、それは 3D グリッドなので、a) 線形インデックス付きの 1 次元ベクトル、b) 3 つのベクトルのベクトル、c) 1 次元の c-style 配列、または d) 3 次元の c-style を考えていました。配列。
古い質問を調べましたが、構築/破壊に関する質問しか見つかりませんでした（データ構造はプログラムの開始時に一度だけ作成されるため、ここでは重要ではありません-高速なインデックス作成と計算が重要です）または異なるSTLコンテナーの比較。
手伝ってくれてありがとう
相対的なパフォーマンスがどうなるかを前もって言うのは困難です (あるいは不可能ですらあります)。一般に、最新のマシンでは、フラット ベクトルを使用してインデックスを計算すると、ベクトルのベクトルのベクトルよりも優れています。古いマシンでは、その逆が当てはまりました。(最近のマシンでは、ローカリティが低いため、通常、乗算はページ ミスよりも安価です。古いマシンでは、乗算は高価で、キャッシュがなかったため、ローカリティは違いを生みませんでした。)
また、マシンとライブラリの実装によっては、std::vectorこのフラット ベクトルに を使用すると、メモリへの単純なポインターを使用するよりもコストがかかる場合があります (そうでない場合もあります。事前に知ることはできません)。私は今でもベクトルを最初に使用し、すべてを制御クラスに慎重にラップし、それでもパフォーマンスの問題がある場合はポインターに切り替えます。
1D 配列と 3D 配列のメモリ レイアウトは同じになり、線形のメモリ レイアウトに似ていますstd::vector。適切な場所にマップするための 1 次元ベクトルとインライン関数です。
一方、ベクトルのベクトルは、ベクトル内のデータがオブジェクト内に格納されず、動的に割り当てられて参照されるため、まったく異なるレイアウトを持ちます。これは、a 内の 2 つの異なる行が、std::vector<std::vector<int>>メモリ内のまったく無関係な場所にある可能性があることを意味します。
ベクトルは、個別にサイズ設定された生の配列を処理するために手動で行う必要があることを内部的に実行します。したがって、それらが適切に使用されている限り、ベクトルは同じタスクを実行する生の配列と同じように実行する必要があります。
たとえば、1 つのベクトルは 1 次元の c-array と同じように動作する必要があり、ベクトルのベクトルは、各要素が配列を指しているポインターの生の配列を使用した場合とほぼ同じように動作する必要があります。
ただし、3 次元配列の次元サイズが均一である場合 (つまり、不規則な配列ではない場合)、ベクトルはサイズを個別に管理するために追加のコストを支払います (たとえば、サイズを個別に保存する必要があります)。コンパイル時に次元サイズのいずれかがわかっている場合は、「STL」コンテナ「std::array , because it won't have that unnecessary overhead. You can even have multi-dimentionalstd::arrays」を使用する方がよいでしょう:
template<typename T, int Planes, int Rows, Cols>
using Matrix = std::array<std::array<std::array<T,Cols>,Rows>,Planes>;
厳密には必須ではありませんが、これは と同じである必要がありますがT arr[Planes][Rows][Cols];、生の c-array の問題はありません。
HPC で広く使用されている、動的に割り当てられた (割り当て後の次元が変更できない) 静的配列オブジェクトは、フラット配列とドープ ベクトルの組み合わせです。基本的には、メモリの大きなフラット チャンクを割り当て、そこにポインタのツリーを構築するという考え方です。2D 配列の場合、ツリーは各行の先頭へのポインターの単純な線形リストです。3D 配列の場合、ツリーには 2 つのレベルがあり、第 2 レベルの各要素は、第 1 レベルに対応する 2D スライスの行を指します。[]割り当てられたメモリの先頭にドープ ベクター ツリーを配置すると、インデックス演算子を直接適用できA[i][j][k]ます。&A[i]i
このアプローチの問題点の 1 つは、ドープ ベクター ツリーのサイズが非常に大きくなる可能性があることです。たとえば、64 ビット マシン上の 1000x1000x1000 配列のこのデータ構造のサイズは、1000x1000x8 バイトまたはほぼ 8 MiB です。これにより、特定のデータ アクセス パターンで貴重なキャッシュ スペースが使用される可能性があります。