C言語による検索アルゴリズムの記述方法について

Question

お世話になっております。C言語を学び20年ほど経ちましたが、未だにスマートな記述方法を知らないケースがあります。質問させてください。

配列dataの中から特定値VALUEを検索し、発見時に条件分岐することを考えます。

これをサブルーチン化せずに記述すると以下のようになりgoto/label構文が出てきます。もちろん、サブルーチン化とかフラグ管理という方法もありますが、goto/label構文以上に複雑になってしまっては本末転倒です。これをスマートに記す方法があればご教示願います。よろしくおねがいします。

for(i = 0; i < N;i++)  {
   if(VALUE == data[i]){
     //当該データを発見した場合の処理。
     goto label;
   } 
}
//当該データが存在しなかった場合の処理。
label:;

Comments

[Zuishin]

サブルーチン化で検索という一機能をモジュール化できるならそうするのがスマートだと思います。
それによってテストも再利用も可能になり、コードの依存性も低くなります。

記述は増えるかもしれませんが、メインルーチンを読む際に検索の実装まで読む必要はなくなり、ループが関数呼び出しにかわることで単純になって可読性も高くなります。

できないのであれば、そこにはできない理由(極度のチューニングが求められるなど)があるはずなので、追及すべきはスマートさではなく実行効率などになるはずです。

検索の速度を上げたいのであれば、リニアサーチをやめてアルゴリズムとそれを支えるデータ構造を考え直すのが良いと思います。

どういう状況でしょうか？

[episteme]

C++tag ついてるけど、Cの質問?
C++なら std::find / std::find_if で解決するんだが。

[dodox86]

> サブルーチン化とかフラグ管理という方法もありますが、goto/label構文以上に複雑になってしまっては本末転倒です。

個人的な範囲ですが、C言語のプログラミングでも goto/labelの出番を感じたことが無いので、むしろその感覚に少し違和感を感じます。「スマート」と思う主観に相違があるのでは。

[dodox86]

> C言語のプログラミングでも goto/labelの出番を感じたことが無いので、

これは言い過ぎだったかも。多重ループからの脱出や、Linuxのドライバーなど、一部のプログラムでは散見されるケースはありますね。（私自身は使いませんが）

[HogeAnimalLover]

失礼、ライブラリ関数の利用は考えていないと書いていませんでした。これも含めようと思います。

[Zuishin]

> ライブラリ関数の利用は考えていないと書いていませんでした。

スマートじゃないです。

[episteme]

> ライブラリ関数の利用は考えていないと書いていませんでした。

後出しジャンケンかよー...回答に追記しました。

[takasima20]

現在の自分の知見が正しいと確認したいがための質問じゃないの？
たぶん何を回答しても納得しない気がするなあ。

Answer 1

未だにスマートな記述方法を知らないケースがあります。

「なにをもってスマートとするか」によるんじゃないかと。
コードを書かずに解決するのがいちばんスマートと考えるなら、
検索アルゴリズムは書かずにライブラリに任せます。

#include <stdio.h> 
#include <search.h>

// 検索はライブラリに任せ、比較関数だけを用意する
int equals(const void* x, const void* y) {
  return *(const int*)x == *(const int*)y ? 0 : 1;
}

int main(void) {
    int data[5] = { 1, 3, 5, 0, 2 };
    unsigned int size = 5;

    int key = 3;
    // VC++ では lfind は deprecated とのこと、しゃーないから _lfind で代用
    int* p = (int*)_lfind(&key, 
                          data, &size, sizeof(int),
                          equals);
    if ( p != NULL ) {
        printf("found %d at %p\n", *p, p);
    } else {
        printf("sorry, not found %d\n", key);
    }
    return 0;   
}

[追記] 後出しジャンケンに対応:

ライブラリ関数の利用は考えていないと書いていませんでした。これも含めようと思います。

どうせなら使いまわしの効くコードを書くのがスマートと考えるなら、
qsort みたく配列の型にも要素数にも検索条件にも依存しない検索関数を定義します。

#include <stdio.h> 
#include <stdbool.h>

/* どんな配列が検索対象であっても使えるスマートな検索関数 */
void* find_if(const void* base, unsigned int nelem, unsigned int size, bool (*comp)(const void*, const void*), void* arg) {
  for ( unsigned int i = 0; i < nelem ; ++i ) {
    if ( comp(base, arg) ) return base;
    base = (const unsigned char*)base + size;
  }
  return NULL;
}

/* 比較関数: 等しいならば true を返す */
bool equals(const void* item, const void* arg) {
  return *(const int*)item == *(const int*)arg;
}

int main(void) {
    int data[5] = { 1, 3, 5, 0, 2 };

    int key = 3;
    int* p = (int*)find_if(data, 5, sizeof(int),
                           equals, &key);
    if ( p != NULL ) {
        printf("found %d at %p\n", *p, p);
    } else {
        printf("sorry, not found %d\n", key);
    }
    return 0;   
}

Comments

[dodox86]

> コードを書かずに解決するのがいちばんスマートと考えるなら、
> 検索アルゴリズムは書かずにライブラリに任せます。

自らコードを書かないことがバグを含む問題を減らすことにも繋がり、いち意見としても方針が明確と感じましたので高評価させていただきました。

[HogeAnimalLover]

題意にライブラリ使用の可否を書き忘れましたが、追記くださりありがとうございます。ベストアンサーにさせていただきます。

[episteme]

...で、あなたは"なにをもってスマート"としたのでしょうか?

[HogeAnimalLover]

はい。質問当初はy_waiwaiさんの回答がもっとも欲しいもの（当初考えるスマートな記述）でした。
ただし、そもそも「スマート」の方針が曖昧であり、ご指摘の通り出来あえ関数利用やサブルーチン化も適切と考えました。

[episteme]

> 質問当初はy_waiwaiさんの回答がもっとも欲しいもの

一発こっきり/他で使うつもりがないなら僕だってそうします。
# そもそも他に選択肢があるならCでは書かないけどwww

Answer 2

for(i = 0; i < N ;i++)  {
   if(VALUE == data[i]) break;
}
if(i<N){
     //当該データを発見した場合の処理。
}else{ 
    //当該データが存在しなかった場合の処理。
}

ってするかなあ、オレなら

Comments

[HogeAnimalLover]

ありがとうございます。質問当初の状況においては最も欲しかった回答でした。

Answer 3

話の前提（「検索」という機能で関数化しないことの必要性？）が良く分かりませんが…

【検索して何かするような処理】というのを一塊で書かなくてはならないのだとしても，
それをmain関数内にべた書きせねばならないのでなければ，その処理自体を丸ごと関数にしてやれば良いのでは．
そうすればreturnで抜けれるので，｛見つかったとき，見つからなかったとき｝を素直に書けるのではないでしょうか．

//何かわからんけど，dataからVALUEを検索して，
//見つかったときには何かをするし，見つからなかったときも何かをする
void SomeFunc( const ???Type *data, ???Type VALUE )
{
  for(int i = 0; i < N;i++){
    if(VALUE == data[i]){
      //データを発見した場合の処理をここで行い，returnする
      ...
      return;
    } 
  }

  //データ未発見時処理
  ...
}

Comments

[fana]

一塊の【検索して何かするような処理】は，そのプログラム内において相応の役目を担っており，名前も付けれるだろし，IN/OUT を明確にできるはずだし明確にすべき．
C言語で書いていて，そういう処理をあえて関数にしない理由（利点）があるのだろうか？

[HogeAnimalLover]

仰るとおり、そもそもサブルーチン化が適切と思います。設計を見直します。

Answer 4

std::vector<int> v{ 3, 3, 4 };
if(std::find(v.begin(), v.end(), 1) != v.end()){
  std::cout << "found" << std::endl;
}
else{
  std::cout << "unfound" << std::endl;
}

これも一般的かと。コンテナによっては、hasメソッドがあることもあります。

Comments

[HogeAnimalLover]

ライブラリの使用は考えていませんでしたが、参考になりました。ありがとうございます。

Answer 5

スマートとは何をもっていうのでしょうか。
短いことでしょうか。
分かりやすいことでしょうか。

それによっては答えが真逆になると思います。

自分だけがそのコードを弄るなら気にしませんが、他の人が触る可能性があるなら、冗長であろうとも分かりやすいフラグ管理法を使うと思います。（C では大丈夫ですが、他の言語だと for カウンタをその場で宣言することで、for ブロック外で for カウンタの値を使えないこともありますから）

Comments

[HogeAnimalLover]

設計、というか方針を見直します。ありがとうございます。

Answer 6

こんなイディオムが一般的だと思います。

for(i=0; i<N && VALUE!=data[i]; i++);
if(i!=N){
   //当該データを発見した場合の処理。
}

Comments

[HogeAnimalLover]

質問当初の状況に置いては欲しかった回答の一つです。ありがとうございます。