2

std::vector::size()呼び出されるたびにベクトルのサイズを再計算しますか、それともベクトルが変更されたときにのみ変更されるカウンターを維持しますか? たとえば、std::vector<double>メンバーを持つクラスがある場合、別のカウンターでそのサイズを追跡する速度の利点はありますか?

4

5 に答える 5

12

size()一定の時間の複雑さが保証されており、適切な実装では、可能な限り高速な操作になります。

于 2012-04-18T23:37:49.943 に答える
3 
this->_Mylast - this->_myFirst

通常、2 回のメモリ フェッチが必要です。カウントをレジスタに保持すると、より高速になる可能性があります。私が言うかもしれないと言うのは、小さなループでは、減算される2つの値がキャッシュにあるためです。これは、常にレジスターよりもずっと遅いわけではありません-マシンによって異なります。そして、タイトなループで動作する巧妙なコンパイラーは、データフロー分析が正しく行われていれば、とにかく両方をレジスターに維持できます。それほど小さくないループでは、違いに気付くことはありません。レジスターでそれを維持することは、反復ごとにレジスターを更新するための追加の操作を意味します。これは、他の操作と並行して実行できる場合は無料になるか、命令サイクルがかかる可能性があります。そのため、違いを測定するのは難しいでしょう。

いずれにせよ、STL のすべての実装に同じコードが含まれている場合でも、マイレージはプロセッサによって異なりますsize()。

于 2012-04-18T23:47:17.933 に答える
2

ベクター内で行われるため、別のカウンターでサイズを追跡する必要はありません。この関数のコードは次のようになります。

iterator begin() {return start;}
iterator end() {return finish;}
size_type size() const { return size_type(end() - begin());}

iterator start;
iterator finish;

要素をプッシュまたはポップすると変数「start」、「finish」が変更されるため、関数 size() はマイナスの時間だけで済みます。別のカウンターを使用する場合は、要素をプッシュまたはポップすると、プラスまたはマイナスも 1 つになります。

于 2012-04-19T02:27:23.527 に答える
1

いいえ - そのまま使用してくださいstd::vector::size()

MSVC では、次のように実装されてthis->_Mylast - this->_Myfirstいます。これに勝るものはありません。

于 2012-04-18T23:38:18.203 に答える
1

他の人が言ったように、それはほとんど速くなりません。ベクトルのサイズが一定の場合にのみ、この事実を利用することで実際に CPU サイクルを節約できます。実際には、サイズのクエリを完全にスキップできます。これは、レンダリングループなどで非常に頻繁に繰り返される反復にとって重要かもしれません.次の違いを想像してみてください:

// reset vector of size=3 to value 10

for( size_t i=0; i < myvec.size(); ++i )
{
   myvec[i] = 10.0;
}

対

 myvec[0] = myvec[1] = myvec[2] = 10.0;

典型的な使用例は、3D 座標ベクトル、IP アドレスなどです。ただし、内部で size() をクエリする std::vector ルーチンを独自のものに置き換える準備をしてください。つまり、要点は、CPUサイクルを節約するために、サイズ演算子はターゲットではなく、他の論理的な場所を探すことです。ベクトルのサイズが一時的であっても変わらない場合は、CPU サイクルを絞り出すための足がドアに入っています。

PS: Valgrindは、最初に最適化する場所を教えてくれる友人です。実際、サイズ演算子は最有力候補として頻繁に登場します。少なくとも一部のアルゴリズムでは。

幸運を！

于 2012-04-19T08:43:51.817 に答える