開発環境
- OS X Lion - Apple(OS)
- Emacs、BBEdit - Bare Bones Software, Inc. (Text Editor)
- プログラミング言語: C
- Clang (コンパイラ)
プログラミング言語C 第2版 ANSI規格準拠 (B.W. カーニハン D.M. リッチー (著)、 石田 晴久 (翻訳)、共立出版)の第3章(制御の流れ)、3.3(Else-If)の演習 3-1を解いてみる。
その他参考書籍
- プログラミング言語Cアンサー・ブック 第2版 (クロビス・L.トンド、スコット・E.ギンペル(著)、矢吹 道郎(翻訳))
演習 3-1.
コード
sample.c
#include <stdio.h> int binsearch(int x, int v[], int n); int main() { enum last {LENGTH = 1000000}; int v[LENGTH]; int i, index; for (i = 0; i < LENGTH; i++) v[i] = i; index = binsearch(5, v, LENGTH); printf("%d\n", index); index = binsearch(-10, v, LENGTH); printf("%d\n", index); /* 実行速度の差を確認するため */ for ( i = 0; i < 10000000; i++) { index = binsearch(5, v, LENGTH); } return 0; } int binsearch(int x, int v[], int n) { int low, high, mid; low = 0; high = n - 1; mid = (low + high) / 2; while (low <= high && x != v[mid]) { if (x < v[mid]) high = mid - 1; else low = mid + 1; mid = (low + high) / 2; } if (x == v[mid]) return mid; return -1; }
入出力結果(Terminal)
$ time ./a.out 5 -1 real 0m2.044s user 0m1.994s sys 0m0.009s $
ループの中で二つのテストを行っている場合の実行時間。
コード
sample.c
#include <stdio.h> int binsearch(int x, int v[], int n); int main() { enum last {LENGTH = 1000000}; int v[LENGTH]; int i, index; for (i = 0; i < LENGTH; i++) v[i] = i; index = binsearch(5, v, LENGTH); printf("%d\n", index); index = binsearch(-10, v, LENGTH); printf("%d\n", index); /* 実行速度の差を確認するため */ for ( i = 0; i < 10000000; i++) { index = binsearch(5, v, LENGTH); } return 0; } 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; }
入出力結果(Terminal)
$ time ./a.out 5 -1 real 0m1.813s user 0m1.799s sys 0m0.006s $
1回だけではそんなに差が出なかったから、for loopで何回も検索するようにしてみたものの、そんなに差が出なかった。(というか、while loopの中で2回テストする方が実行速度が速いという結果に。。)
0 コメント:
コメントを投稿