質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

新規登録して質問してみよう
ただいま回答率
85.50%
C++

C++はC言語をもとにしてつくられた最もよく使われるマルチパラダイムプログラミング言語の1つです。オブジェクト指向、ジェネリック、命令型など広く対応しており、多目的に使用されています。

ArrayList

Java用のタグです。arrayListはListインターフェースを実装した、リサイズ可能な配列用クラスです。

Q&A

解決済

5回答

5789閲覧

C++ CArray 検索速度

t.yamamoto

総合スコア7

C++

C++はC言語をもとにしてつくられた最もよく使われるマルチパラダイムプログラミング言語の1つです。オブジェクト指向、ジェネリック、命令型など広く対応しており、多目的に使用されています。

ArrayList

Java用のタグです。arrayListはListインターフェースを実装した、リサイズ可能な配列用クラスです。

0グッド

0クリップ

投稿2017/01/10 07:10

###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を使用

気になる質問をクリップする

クリップした質問は、後からいつでもMYページで確認できます。

またクリップした質問に回答があった際、通知やメールを受け取ることができます。

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

guest

回答5

0

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

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

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

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

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

投稿2017/01/10 08:39

yohhoy

総合スコア6189

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

t.yamamoto

2017/01/10 09:45

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

2017/01/10 10:27

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

0

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

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

ソートしてもいいなら

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

でやりますね。

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

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

たとえば、

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

総合スコア4958

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

t.yamamoto

2017/01/10 09:41

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

0

検索については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}

投稿2017/01/10 07:37

can110

総合スコア38234

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

t.yamamoto

2017/01/10 09:39

細かい部分から変更していってみます。 回答ありがとうございます。
guest

0

unordered mapがデータの増加の影響を受けなくていいと思いますが、
VC2005で使えるかはわかりませんが。
http://vivi.dyndns.org/tech/cpp/unordered_map.html

投稿2017/01/10 07:34

katsuya141

総合スコア367

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

t.yamamoto

2017/01/10 09:39

回答ありがとうございます。 2005で試せる場合試してみます
guest

0

ベストアンサー

コンテナ(ここではCArray)の要素を昇順/降順にソートしておくわけにはいかんのですか?
ソート済の列なら二分検索でlogN回の比較回数で見つけてくれます。

投稿2017/01/10 07:20

episteme

総合スコア16614

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

t.yamamoto

2017/01/10 07:43

回答ありがとうございます。 ソートも考えていたのですが、 CArrayの要素が頻繁に増加するソースの一部に組み込んでいますので、 逆に追加時のソート時間の増加を考慮し、まずはソートなしで何かないか検討しています。 最終的にソート関係の部分も変更し、速度検証は行ってみます。
episteme

2017/01/10 07:57

であるなら、メモリが潤沢なのであれば二分木やハッシュ表の方が速い。 # 要素数がそこそこ多いとき。要素が少ないときはアルゴリズムの単純な # 可変長配列の方がマシなことも。
guest

あなたの回答

tips

太字

斜体

打ち消し線

見出し

引用テキストの挿入

コードの挿入

リンクの挿入

リストの挿入

番号リストの挿入

表の挿入

水平線の挿入

プレビュー

15分調べてもわからないことは
teratailで質問しよう!

ただいまの回答率
85.50%

質問をまとめることで
思考を整理して素早く解決

テンプレート機能で
簡単に質問をまとめる

質問する

関連した質問