C++ CArray 検索速度

###C++ CArray 検索速度

CArrayの要素のうち、該当する要素場所を検索する関数を作成しています。
現在は下記ソースになっており、正常に動作しているのですが、
かなり頻繁に呼ぶ事になるので、少しでも速度改善をしたいと思います。

int Get_Ary_pos(CString path,ZDATA_ARRAY* zAry){

ZDATA	data_z;
int i = -1;

size = (int)zAry->GetSize();
for(i = 0;i < size;i++){
	data_z = zAry->GetAt(i);
	if(path == data_z.path){break;}
}

return i;

}

###試したこと
CArrayは速度に不向きという事なので、
配列に変換し配列で検索したかったのですが、ZDATA内にCStringがある事からかうまくいきません。

###補足情報(言語/FW/ツール等のバージョンなど)
言語C++ VC2005を使用

行動規範の内容に同意します

回答5件

かなり頻繁に呼ぶ事になるので、少しでも速度改善をしたいと思います。

データ構造とアルゴリズムを変更しない前提で可能な改善としては：

第1引数の型をCString→const CString&に変更。冗長な文字列コピー処理を削減します。
zAry->GetAt(i);の戻り値を、値型ZDATAではなく参照型const ZDATA&で受ける。冗長なオブジェクトコピー処理を削減します。

単純な線形探索では計算量O(N)より速くなることはありません。他回答にもあるように、データをソートしておき2分探索を行うか、ハッシュマップや木構造に変換することで、計算量をO(logN)程度に抑える必要があるかもしれません。

ただし、本当にアプリケーションにおいて「同関数が速度的なボトルネックなのか」を実際に測ってください。これは最適化の鉄則です。単に何度も呼ばれるからという理由のみで、（データ構造を変えるような大掛かりな）最適化を試みるべきではありません。

投稿2017/01/10 08:39

yohhoy

総合スコア6191

t.yamamoto

2017/01/10 09:45

回答ありがとうございます。現在作成しているプロが「Aryの中から一つを探す」という事がメインとなっており、表記させて頂いた関数に似た関数が多くあります。仰る通り鉄則なので、実際に測ってみた所、 1関数当たり、1ミリ秒でも平均早くなれば、全体の処理で200ミリ秒ほど早くなる計算でしたので、何かないかと質問させて頂いた次第です。

yohhoy

2017/01/10 10:27

蛇足ですが、仮に「1関数当たり、1ミリ秒でも平均早くなれば、全体の処理で200ミリ秒ほど早く」なったとして、その200ミリ秒には本当に価値があるか？と言う観点もお忘れなく。（別に最適化を否定しているわけではありませんが、そういうバランス感覚は必要です）

行動規範の内容に同意します

デフォルトで提供されている関数等を使う方法があります。

そうでないなら、自分で実装します。

ソートしてもいいなら

ソート -> バイナリサーチ

でやりますね。

バイナリサーチは中央値を割り出して、その位置の値と対象を比較して大きいなら後ろへ、
小さいなら前へ... のようにやっていくのでリニアサーチ ( 質問にあるような検索方法 ) よりは
時間が少なく済みます。

ただ、問題があって、
前の方にある場合はリニアサーチの方が早い。

たとえば、

10 個のデータでソートしたときに 0番目に来る場合、

バイナリサーチの場合:
10 / 2 = 5
-> 5番目と比較
=> 小さいので前へ ( -1 )

(5-1) / 2 = 2
-> 2番目と比較
...

と3回ぐらいでたどり着く。

しかし、リニアサーチだと

0, 1, 2, 3... と進んでいくのでまず 0番目をチェック
=> 同じ

で 1回目でOK。

そうでない場合はリニアよりはバイナリの方がいい。

投稿2017/01/10 07:43

BeatStar

総合スコア4962

t.yamamoto

2017/01/10 09:41

回答ありがとうございます。ソート時間とサーチ時間の差分を計測し、効果的な場合にサーチ方法自体を変更してみます。

行動規範の内容に同意します

検索についてはepisteme様指摘どおりですがもうひとつ。
全要素を一時変数に代入していますが、毎回コピー発生するためボトルネックになります。
参照またはポインタで参照すべきです。

C++
1ZDATA    data_z; 
2for(i = 0;i < size;i++){ 
3    //data_z = zAry->GetAt(i);           // 代入（コピー）は不要
4    cosnt ZDATA &data_z = zAry->GetAt(i);// 参照またはポインタ
5    if(path == data_z.path){break;} 
6}