K&R 演習3-1 解答 (プログラミング言語C 第2版)

スポンサーリンク

鍛錬 333

K&R 演習3-1 解答 (プログラミング言語C 第2版)

われわれの二分探索では,ループの中で二つのテストを行なっている。これは本来 1 回で十分である (外側でもっとテストが必要になるという代償はあるが)。ループの中で 1 回しかテストをしないようなプログラムを書き,実行時間の差を測定せよ。

B.W.カーニハン D.M.リッチー 石田晴久 訳 『プログラミング言語C 第2版 ANSI 規格準拠』, (共立出版, 2017), pp.71.

スポンサーリンク

旧バージョンの binsearch 関数

以下は、参考書に記述されている関数 binsearch です。

/* 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;  /* 一致するものがなかった */
}

B.W.カーニハン D.M.リッチー 石田晴久 訳 『プログラミング言語C 第2版 ANSI 規格準拠』, (共立出版, 2017), pp.53.

スポンサーリンク

新バージョンの binsearch 関数

問題文では、「ループの中で 1 回しかテストをしないようなプログラムに書き直せ」と指示されています。

以下は、参考書に記述されている関数 binsearch を書き直しています。

int binsearch(int x, int v[], int n)
{
	int low;
	int high;
	int mid;
	int tmp;
	
	low = 0;
	tmp = 0;
	high = n - 1;
	while (low <= high) {
		mid = (low + high) / 2;
		if (x < v[mid]) {
			high = mid - 1;
		}
		else {
			tmp = mid;
			low = mid + 1;
		}
	}
	
	return (x == v[tmp]) ? tmp : -1;
}
スポンサーリンク

プログラム (旧バージョン)

以下は、関数 binsearch を書き直す前のプログラム kr_3_1_old.c です。

今回は、各種パラメータを次の通り設定しています。

項目 設定値
検索する数値 912,345,678
配列の要素数 1,000,000,000
関数を繰り返す回数 100,000,000
// include
#include <stdio.h>

// preprocessor
#define ARRAY_SIZE  1000000000  // 配列の要素数
#define SEARCH_NUM   912345678  // 検索する数値
#define ROOP_FUNC    100000000  // 関数 binsearch を繰り返す回数

// prototype
int binsearch(int x, int v[], int n);

// global
int v[ARRAY_SIZE];

// main
int main(void)
{
	int x;
	int n;
	int p;
	int i, m;
	
	// 配列に 0 ~ 999999999 を昇順で格納
	for (i=0,m=0; i < ARRAY_SIZE; i++,m++)
		v[i] = m;
	
	n = ARRAY_SIZE;  // 配列の要素数
	x = SEARCH_NUM;  // 探索する数値
	
	for (i = 0; i < ROOP_FUNC; i++) {
		p = binsearch(x, v, n);
	}
	if (p == -1)
		printf("ERROR,%d は 配列v[]に存在しない\n", x);
	else
		printf("SUCCESS,%d は v[%d] に存在する\n", x, p);
	
	return 0;
}

/* 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;  /* 一致するものがなかった */
}
スポンサーリンク

プログラム (新バージョン)

以下は、書き直した関数 binsearch を記述したプログラム kr_3_1_new.c です。

今回は、各種パラメータを次の通り設定しています。

項目 設定値
検索する数値 912,345,678
配列の要素数 1,000,000,000
関数を繰り返す回数 100,000,000
// include
#include <stdio.h>

// preprocessor
#define ARRAY_SIZE  1000000000  // 配列の要素数
#define SEARCH_NUM   912345678  // 検索する数値
#define ROOP_FUNC    100000000  // 関数 binsearch を繰り返す回数

// prototype
int binsearch(int x, int v[], int n);

// global
int v[ARRAY_SIZE];

// main
int main(void)
{
	int x;
	int n;
	int p;
	int i, m;
	
	// 配列に 0 ~ 999999999 を昇順で格納
	for (i=0,m=0; i < ARRAY_SIZE; i++,m++)
		v[i] = m;
	
	n = ARRAY_SIZE;  // 配列の要素数
	x = SEARCH_NUM;  // 探索する数値
	
	for (i = 0; i < ROOP_FUNC; i++) {
		p = binsearch(x, v, n);
	}
	if (p == -1)
		printf("ERROR,%d は 配列v[]に存在しない\n", x);
	else
		printf("SUCCESS,%d は v[%d] に存在する\n", x, p);
	
	return 0;
}

// ===================================================================
// @brief     整列済み配列から二分探索で値を検索し,その位置を取得する
// @param[in] x  探索する数値
// @param[in] v  探索される配列
// @param[in] n  配列の要素数
// @return    tmp -> xが存在した場合の,xが格納されている配列の位置
// @return    -1 -> xは存在しない
// @note      無し
// ===================================================================
int binsearch(int x, int v[], int n)
{
	int low;
	int high;
	int mid;
	int tmp;
	
	low = 0;
	tmp = 0;
	high = n - 1;
	while (low <= high) {
		mid = (low + high) / 2;
		if (x < v[mid]) {
			high = mid - 1;
		}
		else {
			tmp = mid;
			low = mid + 1;
		}
	}
	
	return (x == v[tmp]) ? tmp : -1;
}
スポンサーリンク

実行結果

問題文では、「実行時間の差を測定せよ」と指示されています。

今回は time コマンドを使用して各プログラムの実行時間を測定しました。

関連記事:Linux,コマンドを使用して、プログラムの実行時間を計測する

旧バージョン

以下は、関数 binsearch を書き直す前のプログラム kr_3_1_old.c を実行しています。

***@ubuntu:~/***/test/c$ 
***@ubuntu:~/***/test/c$ gcc -Wall -Wextra kr_3_1_old.c -o kr_3_1_old
***@ubuntu:~/***/test/c$ time ./kr_3_1_old
SUCCESS,912345678 は v[912345678] に存在する

real    0m16.055s
user    0m14.492s
sys     0m1.488s

 
上記に示した通り、旧バージョンのプログラム kr_3_1_old.c の実行時間は、以下に示す通りです。

項目 結果
real 0m16.055s
user 0m14.492s
sys 0m1.488s

新バージョン

以下は、書き直した関数 binsearch を記述したプログラム kr_3_1_new.c を実行しています。

***@ubuntu:~/***/test/c$ 
***@ubuntu:~/***/test/c$ gcc -Wall -Wextra kr_3_1_new.c -o kr_3_1_new
***@ubuntu:~/***/test/c$ time ./kr_3_1_new
SUCCESS,912345678 は v[912345678] に存在する

real    0m15.139s
user    0m13.896s
sys     0m1.173s

 
上記に示した通り、新バージョンのプログラム kr_3_1_new.c の実行時間は、以下に示す通りです。

項目 結果
real 0m15.139s
user 0m13.896s
sys 0m1.173s

実行時間の差

実行時間の差は以下に示す通り、関数を書き直したプログラムのほうが若干速いことが分かりました。

項目 結果 (kr_3_1_old.c) 結果 (kr_3_1_new.c)
real 0m16.055s 0m15.139s
user 0m14.492s 0m13.896s
sys 0m1.488s 0m1.173s
タイトルとURLをコピーしました