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

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

ただいまの
回答率

90.62%

  • C++

    3328questions

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

  • ArrayList

    86questions

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

C++ CArray 検索速度

解決済

回答 5

投稿

  • 評価
  • クリップ 0
  • VIEW 955

t.yamamoto

score 1

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

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

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

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

    クリップを取り消します

  • 良い質問の評価を上げる

    以下のような質問は評価を上げましょう

    • 質問内容が明確
    • 自分も答えを知りたい
    • 質問者以外のユーザにも役立つ

    評価が高い質問は、TOPページの「注目」タブのフィードに表示されやすくなります。

    質問の評価を上げたことを取り消します

  • 評価を下げられる数の上限に達しました

    評価を下げることができません

    • 1日5回まで評価を下げられます
    • 1日に1ユーザに対して2回まで評価を下げられます

    質問の評価を下げる

    teratailでは下記のような質問を「具体的に困っていることがない質問」、「サイトポリシーに違反する質問」と定義し、推奨していません。

    • プログラミングに関係のない質問
    • やってほしいことだけを記載した丸投げの質問
    • 問題・課題が含まれていない質問
    • 意図的に内容が抹消された質問
    • 広告と受け取られるような投稿

    評価が下がると、TOPページの「アクティブ」「注目」タブのフィードに表示されにくくなります。

    質問の評価を下げたことを取り消します

    この機能は開放されていません

    評価を下げる条件を満たしてません

    評価を下げる理由を選択してください

    詳細な説明はこちら

    上記に当てはまらず、質問内容が明確になっていない質問には「情報の追加・修正依頼」機能からコメントをしてください。

    質問の評価を下げる機能の利用条件

    この機能を利用するためには、以下の事項を行う必要があります。

回答 5

checkベストアンサー

0

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

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2017/01/10 16:43

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

    キャンセル

  • 2017/01/10 16:57

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

    キャンセル

0

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

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2017/01/10 18:39

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

    キャンセル

0

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

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

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2017/01/10 18:39

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

    キャンセル

0

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

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

ソートしてもいいなら

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

でやりますね。

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

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

たとえば、

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

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

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

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

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

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

で 1回目でOK。

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

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2017/01/10 18:41

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

    キャンセル

0

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

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

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

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

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

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2017/01/10 18:45

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

    キャンセル

  • 2017/01/10 19:27

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

    キャンセル

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

  • ただいまの回答率 90.62%
  • 質問をまとめることで、思考を整理して素早く解決
  • テンプレート機能で、簡単に質問をまとめられる

関連した質問

同じタグがついた質問を見る

  • C++

    3328questions

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

  • ArrayList

    86questions

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