0

kcachegrind を使用してデバッグ モードでコードを実行すると、プログラムのボトルネックは 2 つのベクトルが比較されるポイントであることがわかりました。

if (v1 == v2) {
  // DO
}

より効率的にするにはどうすればよいですか？これは良いですか

if (v1[0] == v2[0]) {
   if (v1 == v2) {
      // DO
   }
}

最初の行は、役に立たない比較をフィルタリングします。

その前に試してみた

if (!v2.empty())
  if (v1 == v2) 
   // DO

ただし、ほとんどの場合、それらは空ではないことがわかりました。したがって、 empty() の追加時間も含まれます。

ベクトルのサイズはほとんど小さいと言わざるを得ません。2~4エレメント。まれに、10 に拡張されます。

更新: Mats Petersson のおかげで、最適化モードでコンパイルすることにより、パフォーマンスがさらに向上したようです。

4

5 に答える 5

5

それが本当にプログラムのボトルネックである場合は、設計をリファクタリングする必要があります。2 つの範囲の比較は、常にO(N)で実行されます。

本当に設計を維持したい場合は、そのパフォーマンスを維持するか、推測するかのいずれかを選択できます。最も変化するベクトルの部分を探すことができます。もちろん、完全にランダムな push_back がある場合は、それだけの価値はありません。次に、それらの要素のテストを最初に開始できます。

于 2013-04-27T18:50:50.100 に答える
4

試してみますが、の内部は次のv1 == v2ようになると思います。

 for(int i = 0; i < v1.size && i < v2.size; i++)
 {
    if (v1[i] != v2[i])
       return false;
 }

[上記はおそらく実際の実装方法ではなく、「このように機能する」として示されています]

したがって、インデックス 0 が最も一般的に異なる要素である場合、ほとんど得られません。

ぜひ、試してみてください（とにかくここで尋ねるよりもおそらく速いでしょう！）

もちろん、この特定の質問の主な部分は、コメントを考慮して、「最適化をオフにしてコードをベンチマーク/プロファイリングしないでください」です。コードの非常に詳細でルーピーなビットを測定すると、パフォーマンスが 10 倍低下するのは非常に簡単です。その後、最適化がオフになります [そして、「デバッグ モード」が追加のチェックなどを有効にして、範囲外の使用がないことを確認する場合、など、100 ～ 1000 倍遅いコードを確認できます]

于 2013-04-27T18:43:43.830 に答える
2

あなたの型は基本的な整数型であるため、*を使用してそれらをメモリのチャンクとして比較することができますmemcmp

memcpy2 つのバッファ ( void*) を取得し、バッファのメモリ チャンクが等しい場合は 0 を返します

bool equal = v1.size() == v2.size() && memcmp(&v1.front(), &v2.front(), sizeof(v1[0]) * v1.size()) == 0;

(*) - 必ずしも役に立たないことを示すために、try という言葉を強調しましたが、可能性の 1 つです。

于 2013-04-27T18:48:02.927 に答える
2

2 番目のコード ブロックはわずかに効率的ですが、正しくありません。1 つまたは両方のベクトルが空の場合に何が起こるかを考えてみてください。ここでの唯一の節約は、文字列の最初の文字が異なる場合の呼び出しのオーバーヘッドとループ設定のオーバーヘッドを回避することです。これらの節約は小さすぎるため、プログラムを複雑にする価値はありません。

大幅に節約したい場合は、文字列を等価性を異なる方法で実装するカスタム クラスに置き換えることを検討してください。コードが異なります。

于 2013-04-27T18:42:37.573 に答える
0

あなたが持っている実装は、配列のサイズが等しいことを確認することから始めて、要素を1つずつ調べてそれらを比較し続けると思います(最初の違いでできるだけ早くfalseを返します)。したがって、あなたの提案はあまり役に立たず、 std::mismatch も役に立ちません。

ただし、ベクトルを並べ替えておくことができれば、よりスマートなチェックが可能になる可能性があります。あなたはできる？

于 2013-04-27T18:42:50.527 に答える