1

約500個の数字を持つマスターリスト整数配列があります。そして、欠落している数字を見つけるためにマスターリストから選んだ100個のランダム化された数字のセットがあります。ここで、この乱数リストをマスター リストと照合する必要があります。プログラムをハングアップさせずにそれを実行するための C プログラミングでの最良のアプローチは何でしょうか。500 個の要素に対して単純な「for」ループを通過すると、リスト全体を通過する必要があるためハングします。誰かがこれについて私に指示できますか？

ありがとう。

4

2 に答える 2

3

まず、プロファイルを作成する必要があります。私たちが話しているのは、最大で500 * 100=50,000の操作だけです。あなたがそれを非常に非効率的にコーディングしない限り、平均的な現代のコンピュータはそれを10分の1秒未満で終えることができます。

とにかくそれを最適化したいと仮定して、マスター配列をソートし、ランダム化された配列の各要素に対してバイナリ検索を実行する必要があります。これにより、500個の数値の二分探索には最大9回の比較が必要になるため、操作の数が50,000から最大900に減少します。

これは、標準Cライブラリの組み込みのソートおよびバイナリ検索関数（qsortおよび）を使用する実装です。bsearch

int less_int(const void* left, const void* right) {
    return *((const int*)left) - *((const int*)right);
}

int main(void) {
    size_t num_elements = 500;
    int* a = malloc(num_elements*sizeof(int));
    for(size_t i=0 ; i<num_elements ; i++) {
        a[i] = rand() % num_elements;
    }
    qsort(a, num_elements, sizeof(int), less_int);
    size_t num_rand = 100;
    int* r = malloc(num_rand*sizeof(int));
    for(size_t i=0 ; i < num_rand ; i++) {
        r[i] = rand() % num_rand;
    }

    for (size_t i = 0 ; i != num_rand ; i++) {
        int *p = (int*) bsearch (&r[i], a, num_elements, sizeof(int), less_int);
        if (p) {
            printf ("%d is in the array.\n", *p);
        } else {
            printf ("%d is not in the array.\n", r[i]);
        }
    }

    free(a);
    free(r);
    return 0;
}

ideoneで実行中のこのプログラムへのリンクは次のとおりです。

于 2012-10-15T12:51:45.830 に答える
1

n - ランダム化された配列の長さ。

m - マスターリスト配列の長さ。

  1. ランダム化された配列を並べ替えます。n*log(n)
  2. マスター リスト内のすべての要素に対して、並べ替えられた配列でのバイナリ検索。したがって、不足しているすべての要素があります。(m)*log(n)

=> (m+n) * log(n)操作全体。n=100とm=500で、

600 * log(100)基数 2 へのログ

生のコーディングでの 50000 回の反復と比較して、約 3986 回の反復。

PS: 両方の配列がソートされている場合、O(m) の比較だけで十分です。

于 2012-10-15T13:07:00.023 に答える