1

次元 > 1 で自然に表されるデータを保存および生成しています。ただし、プログラマーが独自のカスタム インデックスを持つ 1D ベクトルを使用して複数の次元を表すことを推奨する多くの回答を見てきました。私の質問は次のとおりです。1 次元のみを使用することで得られるものは何ですか?

私の現在のプロジェクトでは、パフォーマンスが優先事項です (最初にコード、次にプロファイルを知っていますが、このプロジェクトは速度を上げるために別の言語から C++ にインポートされています)。ベクトル オブジェクトを 1 つだけ持つだけでオーバーヘッドが削減されることがわかりましたが、それはインデックスを頻繁に計算することよりもはるかに優れているのでしょうか? ネストされたベクトルを使用するという回答が 1 つありました。

vector < vector<int> >

への多くの呼び出しを引き起こしますnew。これがどのように厄介なのかわかりましたが、これは本当ですか?

4

1 に答える 1

4

まず、 astd::vector<std::vector<int>>はさまざまなサイズの内部ベクトルを持つことができます。ただし、この型を使用して 2D 配列を模倣することについて具体的に話していると仮定します。ベクターを作成するときにベクターのサイズを設定すると仮定すると、すべてが一度に行われるため、動的割り当ての量について心配する必要はおそらくありません。

ベクトルは、その要素の配列を内部的に割り当てます。したがって、外側のベクトルはベクトルの配列を割り当てており、それらの内側のベクトルのそれぞれはints の配列を割り当てています。次のように考えることができます。

┌─────┐
│ vec │
└──╂──┘
   ┃
   ▼
┌─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┐
│ vec │ vec │ vec │ vec │ vec │ vec │ vec │ vec │ vec │
└──╂──┴──╂──┴──╂──┴──╂──┴──╂──┴──╂──┴──╂──┴──╂──┴──╂──┘
   ┃     ┗━━━━━━━━━━┓
   ▼                ▼
┌─────┬─────┬┄   ┌─────┬─────┬┄
│ int │ int │    │ int │ int │
└─────┴─────┴┄   └─────┴─────┴┄

ご覧のとおり、 ints の配列は互いに完全に分離されています。それらはメモリの完全に異なる場所にある可能性があります。これは断片化として知られています。ほとんどの場合、メモリの単一の連続したブロックにはなりません。このため、2D ベクターの異なる「行」にまたがる要素にアクセスすると、キャッシュ ミスが発生する可能性があります。

ただし、ints の 1 つのベクトルを割り当てて独自の 2 次元インデックスを作成すると、メモリ レイアウトは次のようになります。

┌─────┐
│ vec │
└──╂──┘
   ┃
   ▼
┌─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┬┄
│ int │ int │ int │ int │ int │ int │ int │ int │ int │
└─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┴┄

はint、単一の連続したメモリ ブロックに格納されます。どのアクセスも同様のメモリ アドレスを持ち、キャッシュ ヒットにつながる可能性があります。これにより、パフォーマンスが向上する可能性があります。

于 2013-03-27T18:01:05.680 に答える