fscanfの挙動

[came_tongue_0001]

こんばんわ。

C言語はあまり明るくないんですが、興味本位で次のようなプログラムを書いてみました。

コード:

#include <stdio.h>
#include <stdlib.h>

#define MAXDATA 10000
#define KEY_NOT_FOUND EXIT_FAILURE

void read_file(int a[], char filename[]) {
  FILE* fin;
  int n = 0;
  if ((fin = fopen(filename, "r")) == NULL) {
    printf("ファイルをオープンできません\n");
    exit(EXIT_FAILURE);
  }
  while(!feof(fin) && n < MAXDATA) {
    fscanf(fin, "%d", &(a[n]));
    n++;
  }
  fclose(fin);

}

void bubbleSort(int a[], int n) {
  int i, j, k, tmp;
  for (k = n - 1; k > 0; k--) {
    for (i = 0; i < k; i++) {
      for (j = 1; j <= k; j++) {
        if (a[j] < a[j - 1]) {
          tmp = a[j]; a[j] = a[j - 1]; a[j - 1] = tmp;
        }
      }
    }
  }
}

int binary_search(int ary[], int key, int imin, int imax) {
  if (imax < imin) {
    return KEY_NOT_FOUND;
  } else {
    int imid = imin + (imax - imin) / 2;
    if (ary[imid] > key) {
      return binary_search(ary, key, imin, imid - 1);
    } else if (ary[imid] < key) {
      return binary_search(ary, key, imid + 1, imax);
    } else {
      return imid;
    }
  }
}

int main(int argc, char* argv[]) {
  char *endp, s[6];
  int x, a[MAXDATA], position;

  if (argc < 2) { return EXIT_SUCCESS; }

  read_file(a, argv[1]);
  bubbleSort(a, MAXDATA);

  scanf("%5s%*[^\n]%*c", s);
  x = strtol(s, &endp, 10);

  position = binary_search(a, x, 0, 99999);

  if (position == KEY_NOT_FOUND) {
    printf("見つからない\n");
  } else {
    printf("x=%d ---> %d\n", x, position);
    printf("またお会いしましょう\n");
  }
  return EXIT_SUCCESS;
}

ところがコンパイルして実行してみると、無限ループみたいにずーっと入力を促し続けます。
どうやら一番最初のread_file(ファイルから配列にデータを入れていく関数)の終了時点で引っかかってるらしく、延々と入力要請な状態に陥る模様です。
fscanfの記述方法が間違ってるんじゃないか、とあちこちのサイトで記述方法を調べて、書き換えてテストしてみたんですが、全く改善せず、ほとほと困り果てた状態です。
一体何が間違ってるんでしょうか。

なお、コマンドライン引数として与えるファイルはPythonで

コード:

import random

with open('hogehoge.dat', 'w', encoding = 'ascii') as f:
    [print(random.randint(1, 99999), file = f) for i in range(10000)]

として作成しています。
また、利用したOSはXubuntu 20.04LTSで、コンパイラはgcc 9.3.0. とclang 10.0.0を用いてみました。

[みけCAT]

これはfscanfが問題なのではなく、
その次のbubbleSort関数の処理にかなり長時間(実験はしていないが、1時間くらい～？)かかるだけだと思います。
topコマンドなどでCPU使用率をチェックし、CPU使用率が下がるのを待ってから入力をしてみましょう。

なお、普通のバブルソートはO(n^2)であり、10000件であれば数秒～数十秒程度でできるはずですが、
ここで使われているbubbleSort関数はO(n^3)なので、
nが大きくなっていくに従いバブルソートよりさらにどんどん処理時間が伸びます。

また、このコードには他にも
・binary_search関数の引数imaxに与える値が不適切
　(せっかく定義した定数を使っていない上、大きすぎるため範囲外アクセスの原因になる)
・見つからない時にEXIT_FAILUREを返すようになっているが、これは1と定義されていることがあり、
　見つかった時の添字として返される1と区別がつかなくなってしまう (環境依存)
という問題があります。

[came_tongue_0001]

>> みけCAT さん

お返事ありがとうございます。

> その次のbubbleSort関数の処理にかなり長時間(実験はしていないが、1時間くらい～？)かかるだけだと思います。

実は元々、QuickSortのコードを使ってました。
ただ、その時も全く同じ症状で、コード的にエラーを追いやすいだろう、って言うので、bubbleSortに置き換えたのです。
そして、(いわゆる)printfデバッグも行って、データがbubbleSortに流れ込んで行ってないだろう、とアタリをつけたわけです(と言うのも、sort関数の最後にprintfを差し込んで、配列aを表示させたけど、全くsortが行われていなかった)。

> ・binary_search関数の引数imaxに与える値が不適切
>　(せっかく定義した定数を使っていない上、大きすぎるため範囲外アクセスの原因になる)

あ、これもデバッグの為に色々差し替えてて・・・全然直してなかったです(苦笑)。どこに原因があるのかサッパリ分からなかったもので・・・・・・。

> ・見つからない時にEXIT_FAILUREを返すようになっているが、これは1と定義されていることがあり、
>　見つかった時の添字として返される1と区別がつかなくなってしまう (環境依存)

あ、これはgcc/clangを調べてみますね・・・どうもこの辺、Pythonとかやってると例外処理的に考えていけません。

[came_tongue_0001]

>> みけCAT さん

> その次のbubbleSort関数の処理にかなり長時間(実験はしていないが、1時間くらい～？)かかるだけだと思います。

全くその通りでしたorz
Pythonでの生成データ数を減らしてみたら上手く動きました。
最初に少ないデータ数でやるべきだった・・・orz
まさか、昨今のPCでデータ数10000程度で根を上げる、なんて想像してませんでした。
っつーか、バグを探す際のチェックが甘かったです。

ビックリしたんですが、MAXDATAを1000まで、なら上手く動くんですが、10000だと反応しなくなる、ってのは初めて見た現象です。
はぁ、ってなカンジでした。

お騒がせ致しました。