vector間における効率的な値の比較

質問

２つのベクターに入ったdoubleの網羅的な比較を行う関数をC++で書こうとしています。
(VC++ 2008)

doubleのベクター　vctr_1 , vctr_2 があるとします。

vctr_1 には (100.0, 200.5 , 300.1 , 400.0 )
vctr_2 には(50.0 , 70.2, 100.1, 220.0 , 300.0 ) というdouble の値が入っていて　vctr_1の値のうち、vctr_2に近い値（誤差0.2以内）が見つかるものを.新しいベクターとして返すという処理を考えています。

この場合 100 : 100.1 と300.1: 300.0　が 誤差 0.2 未満で近い値といえ、100 と300.1が格納されたベクターを返す、という処理です。

私の考えた方法はベクターaの各要素に対してベクターbの各要素をループで比較する、というものでした。

以下コード
----------------------------
//比較を行う関数。ベクター１、２　要素の比較をし誤差内の数値をベクター１からとりだし、別のベクターとして返す。
vector<double> compare_doubles_with_tol(vector<double> v1,vector<double> v2 , double tol ){
//似た値を格納するベクター
vector<double> v_match;
//ベクター１に関してループ
vector<double>::iterator it1 = v1.begin();
while( it1 != v1.end() ){
//ベクター２に関してループ
vector<double>::iterator it2 = v2.begin();
while( it2 != v2.end() ){
//誤差内の値を見つける
if( fabs(*it1 - *it2) < tol ){
v_match.push_back(*it1);
}
++it2;
}
++it1;
}
return v_match;
}

int main() {
//ベクター１
std::vector<double> vctr_1;
vctr_1.push_back(100.0);
vctr_1.push_back(200.5);
vctr_1.push_back(300.1);
vctr_1.push_back(400.0);
//ベクター２
std::vector<double> vctr_2;
vctr_2.push_back(50.0);
vctr_2.push_back(70.2);
vctr_2.push_back(100.1);
vctr_2.push_back(220.0);
vctr_2.push_back(300.0);

//誤差0.2内で似た値があるものを新たなベクターとして得る。
vector<double> matched = compare_doubles_with_tol(vctr_1,vctr_2,0.2);

for (int i = 0 ; i < matched.size() ; ++i){
cout << matched[i]<<endl;

}

return 0;
}
-------------------------

このコードで望んだ結果は得られますがループの繰り返しを行っていて処理が遅くなってしまいます。実際の仕事ではベクターの要素数が100前後のものを非常に数多く処理しなければならず、このままでは処理時間が膨大なものになってしまいそうです。

このような場合どのような処理、コードを作成すれば処理速度の向上が望めるでしょうか。

回答No.2

osamuy · ベストアンサー

事前に、両ベクターをソートしておいて、小さい値からチェックしていけば、余分な比較をせずにすむとか。

ex) vctr_1の100.0で範囲外だったvctr_2の50.0と70.2は、vctr_1の200.5でも範囲外なのが明らか。

ソートするための計算量も含めれば、O(n*log n)でいけるかと。
ベクターの出現順の安定性を求められなければですが。

// rubyで書いているのは、C++慣れてないから。

参考URL：

http://ideone.com/R4HQX

お礼

お礼が遅くなってしましたが、コードありがとうございます。
rubyは使ったことはないのですが、書いてあることはほぼ読み取れますのでC++に書き直してみようと思います。とても助かりました。

回答No.4

ki073

No.3です。
＞3)i7-920. コア数. 4. スレッド数. 8　になります。ご指摘のようにboostのマルチスレッドの利用も将来的には考えていました。
boostは名前しか知らないんですが、openMPの方が簡単かもしれません。基本的にプログラム構造を変更する必要がないので。

ところで、質問欄と同じような総当たりのアルゴリズムでプログラムを書いてベンチマークをとってみました。
それぞれ100個のデータです。C++ではなくNo.2と同じRubyです。narrayという行列計算用のライブラリを使っています。（実はcompare_doubles_with_tolは１行で書けるのです）

compare_doubles_with_tolに相当する部分だけの時間ですが、１回あたり0.14msecになります。（実際には1000回実行して0.140秒です）CPUも同じCore i7-920(2.66GHz)です。C++で書けばこれよりも更に速いはずです。

この結果を遅いとみるか、十分な速さと見るかは何回くらい実行するかで決りますが、全体のプログラムができたらプロファイラで各部分の実行時間を計ってみることをお勧めします。ファイルの読み込みにものすごく時間がかかっていて、計算の部分をいくら速くしても効果がないこともよくありますので。

お礼

>全体のプログラムができたらプロファイラで各部分の実行時間を計ってみることをお勧めします
たしかに実際のプログラムでは他にも色々な処理も関与しているのでプロファイラでの計測は必要ですね。いままで使ったことはなかったのですがこの機会に試してみようと思います

回答No.3

ki073

ちょっと確認ですが、
1) vctr_1, vctr_2の個数はどれくらいか（両方とも100前後か、片方が多い、少ない）vctr_2をソートするための時間と効果のバランス。

2) vctr_2の値が毎回違うのか、何度か同じものを利用しているのなら事前にソートすることができる。

3) CPUのCore数だけ簡単に並列化可能ですが、Core数はいくつで利用可能か。ある程度まで最適化して後並列化すれば並列化分だけ速くなる。

それとソートしたもの調べるときに、頭から順番に調べるのではなく、二分探索などを使うと速くなります。

補足

1)vctr_1, vctr_2の要素は両方とも100前後になります。両方ともだいたい同じ数になります。
2) vctr_2の値は毎回異なります。
3)i7-920. コア数. 4. スレッド数. 8　になります。ご指摘のようにboostのマルチスレッドの利用も将来的には考えていました。

二分探索ははじめて聞いたのですが、確かに有効なアプローチですね。

回答No.1

kmee

「v1の要素しか返さない」
「v_matchの値は重複しない」のなら
・ v_match.push_back(*it1); した時点で残りのv2と比較する必要無し
※ もとのプログラムでは、vctr_2: {100.1, 100.1 , 100.1 }だったらmatched: {100,100,100}になります。

v1,v2ともに昇順ソートしてあれば
・*it1 + tol <= *it2 になった時点で それ以降のv2は調べる必要無し
・*it1 -tol >= *v2.end()になった時点で、それ以降のv1は調べる必要無し
・*it1 +tol <= *v2.begin()なら、その*itについて調べる必要無し
・毎回v2の先頭から比較するのではなく、
　　[前回の最後の*it2] <= *it1 - tol なら、それより前にマッチするものは無いので、そのままit2を続ける。
　　そうでないなら、 *it2 <= *it1 - tol になるまで--it2で前へ戻す。
　　　※ 上記の「v1のみ、重複無し」なら、この時点での判定→v_match.push_back→次のit1も可能

お礼

ご指摘のように論理的に処理することでかなり無駄が省けそうですね。思っていたより複雑な処理になりそうですがアドバイスを参考にさせていただいてなんとか書いてみようと思います。
ありがとうございました。