ACM の例では、動的計画法のために大きなテーブルを作成する必要がありました。各セルに 2 つの整数を格納する必要があったため、std::pair<int, int>. ただし、それらの巨大な配列を割り当てるには 1.5 秒かかりました。
std::pair<int, int> table[1001][1001];
その後、このコードを次のように変更しました
struct Cell {
int first;
int second;
}
Cell table[1001][1001];
割り当てには0秒かかりました。
この大きな時間差は何によって説明されるのでしょうか?
std::pair<int, int>::pair()コンストラクターはフィールドをデフォルト値 ( の場合はゼロint)で初期化し、struct Cellそうしません (何もしない自動生成されたデフォルト コンストラクターしかないため)。
初期化には、各フィールドへの書き込みが必要であり、比較的時間がかかる大量のメモリアクセスが必要です。代わりにstruct Cell何も行われず、何もしない方が少し高速です。
これまでの答えは、問題の完全な大きさを説明していません。
Sharptoothが指摘しているように、ペアソリューションは値をゼロに初期化します。Lemurikが指摘したように、ペアソリューションは、メモリの連続ブロックを初期化するだけでなく、テーブル内のすべての要素に対してペアコンストラクターを呼び出します。ただし、それでも1.5秒かかることは考慮されていません。他に何かが起こっています。
これが私の論理です：
あなたが古代のマシンを使っていたと仮定すると、たとえば1.33GHzで実行しているとすると、1.5秒は2e9クロックサイクルになります。構築する2e6ペアがあるので、どういうわけか、各ペアコンストラクターは1000サイクルかかります。2つの整数をゼロに設定するコンストラクターを呼び出すのに1000サイクルはかかりません。キャッシュミスがどのようにそれを長くかかるかはわかりません。100サイクル未満なら信じられます。
これらすべてのCPUサイクルが他にどこに向かっているのかを見るのは興味深いと思いました。必要な無駄のレベルを達成できるかどうかを確認するために、見つけた中で最も古いC++コンパイラを使用しました。そのコンパイラはVC++v6でした。デバッグモードでは、私が理解できないことをします。これには、テーブル内の各アイテムのペアコンストラクターを呼び出す大きなループがあります-十分に公平です。そのコンストラクターは、2つの値をゼロに設定します-十分に公平です。ただし、その直前に、68バイト領域のすべてのバイトが0xccに設定されます。その地域は、大きなテーブルが始まる直前です。次に、その領域の最後の要素を0x28F61200で上書きします。ペアコンストラクターを呼び出すたびに、これが繰り返されます。おそらく、これはコンパイラによるある種の簿記であるため、実行時にポインタエラーをチェックするときにどの領域が初期化されているかがわかります。私'
とにかく、それは余分な時間がどこに行くのかを説明するでしょう。明らかに、別のコンパイラはこれほど悪くないかもしれません。そして確かに、最適化されたリリースビルドはそうではありません。
これらはすべて非常に良い推測ですが、誰もが知っているように、推測は信頼できません。
その1.5秒以内にランダムに一時停止すると言いますが、かなり速くする必要があります。各ディメンションを約3倍に増やすと、10秒以上かかる可能性があるため、一時停止しやすくなります。
または、デバッガーで取得し、ペアコンストラクターコードで分割してから、シングルステップで実行内容を確認することもできます。
いずれにせよ、あなたは単なる推測ではなく、質問に対する確固たる答えを得るでしょう。
私の推測では、それは std::pair が作成される方法です。ペア コンストラクターを 1001x1001 回呼び出すと、メモリ範囲を割り当てるだけの場合よりもオーバーヘッドが大きくなります。
これは、C++ を作成し、STL を慎重に使用する必要があることを示す良い例です。何かご意見は？
私のプロジェクトでは、C&C++ コード レベルのベンチマーク テスト ツールに取り組んでいます。このツールでは、「良い」コードと「悪い」コーディング習慣を見つけるために多くのコード サンプルを作成します。C9B.M の詳細については、 http: //effodevel.googlecode.com を参照してください。計画中。このようなケースをたくさん経験したことがある方は、ぜひプロジェクトに参加してください。