Serendip

Web Studio

演習3-1

元の binsearch と改良版 binsearch2 とで実行時間の差を比べる。

#include <stdio.h>
#include <time.h>
#define MAXSIZE 0x100000

int binsearch(int x, int v[], int n);
int binsearch2(int x, int v[], int n);

int main(int argc, char *argv[])
{
    int v[MAXSIZE];
    int i;
    time_t t;

    for (i=0; i<MAXSIZE; i++) {
        v[i] = i;
    }

    t = clock();
    for (i=0; i<MAXSIZE; i++) {
        binsearch(i, v, MAXSIZE);
    }
    printf("binsearch  => %f\n", difftime(clock(), t));

    t = clock();
    for (i=0; i<MAXSIZE; i++) {
        binsearch2(i, v, MAXSIZE);
    }
    printf("binsearch2 => %f\n", difftime(clock(), t));


    return 0;
}

int binsearch2(int x, int v[], int n)
{
    int low ,high, mid;

    low = 0;
    high = n - 1;
    while (low < high) {
        mid = (low + high) / 2;
        if (x < v[mid]) {
            high = mid;
        } else {
            low = mid + 1;
        }
    }

    return low == high ? mid : -1;
}

/* binsearch : v[0] <= v[1] <= ... <= v[n-1] の中で x を探せ */
int binsearch(int x, int v[], int n)
{
    int low, high, mid;

    low = 0;
    high = n - 1;
    while (low <= high) {
        mid = (low + high) / 2;
        if (x < v[mid]) {
            high = mid - 1;
        } else if (x > v[mid]) {
            low = mid + 1;
        } else { /* 一致した */
            return mid;
        }
    }

    return -1; /* 一致するものがなかった */
}

実行結果

binsearch2 の方が実行時間がかかるようになってしまっている・・・

$ ./ex3-1
binsearch  => 293985.000000
binsearch2 => 301982.000000

プログラミング言語C 第2版 ANSI規格準拠

posted with amazlet at 09.11.27

B.W. カーニハン D.M. リッチー
共立出版
売り上げランキング: 9726

Amazon.co.jp で詳細を見る