2

2 つの大きなベクトル (整数) を比較しようとしています。つまり、各エントリで、2 つのベクトルが同じ要素を持っているかどうかを確認します。イテレータを使用して比較を行い、単純な for ループを使用して、いくつかのことを試しました。どちらも機能しますが、多くのベクトルを比較する必要があるため、速度を上げるものが必要です。C ++でそれを行う最良の方法は何ですか?? よろしくお願いします！

typedef vector<int> fingerprint;

double aakernel(fingerprint a,fingerprint b, double h){

    double diff = 0;
    vector<int>::iterator dd = a.begin();
    vector<int>::iterator ee = b.begin();

    for(; dd != a.end() && ee != b.end() ;++dd, ++ee){ /*option one*/
        if (*dd!=*ee){
            diff++;
        }

    }


    for (int dd=0;dd<int(a.size());dd++){ /*option two*/
        if (a[dd]!=b[dd]){
            diff++;
        }
    }
    double due = (h/(1-h));
    double q = -log(due)*diff;
    double K = exp(q);
    return (K);
}
4

5 に答える 5

3

ベクトルが任意である場合、現在のようにすべての要素を順次比較するよりも漸近的には良くなりません。そのため、パフォーマンスが向上する場合と向上しない場合があるマイクロ最適化が残っています (コンパイラのオプティマイザーがそれらを処理する方法によって異なります)。

私が考えることができるのは、変化しない評価をループから外すことだけです。(そしておそらく++on typeも使用していませんdoubleが、とにかくコンパイラがこれを最適に処理すると思います):

double diff = 0;
for (
  auto itA = a.begin(), itB = b.begin(), endA = a.end();
  itA != endA;
  ++itA, ++itB
) {
  if (*itA != *itB) {
    diff += 1.0;
  }
}
于 2013-11-11T08:55:22.247 に答える
2

1）これを分割して、それぞれに異なるスレッドを使用することで、これを高速化できます。

2) MMX などの並列処理マシンのオペコードを調べて、適用可能かどうかを確認することもできます。

3) コンパイラ、そのオプティマイザ、CPU などによっては、分岐をなくしただけでパフォーマンスが大幅に向上する場合とされない場合があります。代わりに...

if (*dd != *ee){
    diff++;
}

...多分試してみてください...

diff += bool(*dd - *ee);

最初にバージョンのアセンブリ言語をチェックしてif ()、オプティマイザーが既にこれを行っているかどうかを確認する価値があるかもしれません。まだブランチがある場合bool(*dd - *ee)は、必要に応じてインライン アセンブリに戻って、他のいくつかのことを試すことができます。

4）同じベクトルを他の多くのベクトルと比較することになると仮定すると、データ内の範囲のチェックサム/ハッシュを保存できます。これにより、同じベクトルが異なる代替と比較されるときに、異なるハッシュを持つ領域のみが考慮されます。これは可能性がありますいくつかの違いを見逃す - 適切なハッシュの場合は 2^bit に約 1 - しかし、これがフィンガープリントの場合は、とにかく確率論的であると想定し、これは重要ではありません。

5) NSA のためにこれを行っている場合は、VBA で再コーディングすることをお勧めします。

于 2013-11-11T09:41:27.420 に答える
1

2 つのfingerprint値が通常同じである場合は、最初に

memcmp(&a[0], &b[0], a.size() * sizeof(int))

2 つの配列に違いがあるかどうかをテストします。違いがある場合にのみ、どれだけの違いがあるかを調べます。

于 2013-11-11T09:10:54.983 に答える