编程珠矶学习笔记(6)--测试及性能(基本的)来源: 发布时间:星期四, 2009年10月8日 浏览:0次 评论:0
转载自:http://blog.csdn.net/lijian818181/archive/2009/10/08/4643494.aspx
个人原创,转载请注明出处,谢谢! 一、 目的(1) 使用简单的测试脚手架来测试函数的正确性; (2) 使用简单的时间函数来度量函数的时间。 二、实现方法1. 使用断言来保证捕捉异常: int i = -999999; #define assert(v) { if ((v) == 0) printf(" binarysearch bug %d %d\n", i, n); } 2. 使用测试脚手架进行正确性验证: 3. 度量算法使用时间:
三、功能正确性测试代码请重点关注蓝色内容,其它部分请参考: “编程珠矶学习笔记(5)--两分搜索算法(折半查找算法)”。
#include <stdio.h> #include <stdlib.h> #include <time.h>
int i = -999999; #define assert(v) { if ((v) == 0) printf(" binarysearch bug %d %d\n", i, n); }
#define MAXN 1000000 typedef int DataType; DataType x[MAXN]; int n = 0;
int binarysearch (DataType t) { int l, u, m; l = 0; u = n-1; while (l <= u) { m = (l + u) / 2; if (x[m] < t) l = m+1; else if (x[m] == t) return m; else /* x[m] > t */ u = m-1; } return -1; }
#define s binarysearch /*定义被测的函数,需要测试其它函数在这替换即可*/
void test(void) { int i;
/* 初始化数组,同时将最高的元素也初始化*/ for (i = 0; i <= n; i++) { x[i] = 10*i; }
for (i = 0; i < n; i++) { /*测试1:查找每一位置i上的元素x[i],结果应返回i, 否则将报错*/ assert(s(10*i) == i);
/*测试2:查找目标值为10*i-5的元素位置,由于各元素为10*i, 所以结果应返回-1, 即找不到该元素,如不返回-1则将报错*/ assert(s(10*i - 5) == -1); }
/*测试3:查找目标值为10*n-5的元素位置,由于各元素为10*i, 所以结果应返回-1, 即找不到该元素,如不返回-1则将报错,该用例为边界测试的异常用例测试*/ assert(s(10*n - 5) == -1);
/*测试4:查找目标值为10*n的元素位置,由于数组元素索引为[0,n-1], 不包含n, 所以结果应返回-1, 即找不到该元素,如不返回-1则将报错,该用例为边界测试的异常用例测试*/ assert(s(10*n) == -1);
/*重新初始化数组:所有的元素均为10*/ /* equal elements */ for (i = 0; i < n; i++) { x[i] = 10; }
if (n == 0) { /*测试5:边界测试, n=0, 应该什么也找不到*/ assert(s(10) == -1); } else { /*测试6:正常条件测试,返回值应当在[0,n)之间*/ assert(0 <= s(10) && s(10) < n); }
/*测试7:异常情况测试,输入一个任意不存在的数, 应该什么也找不到*/ assert(s(5) == -1);
/*测试8:异常情况测试,输入一个任意不存在的数, 应该什么也找不到*/ assert(s(15) == -1);
}
int main(void) { /*启动脚手架测试函数,开始测试*/ test();
return 0; }
注: 每想到这段程序,总有一种想把自己以前所写的程序再好好测测的冲动,平时总觉得没什么可以测的,但看到这段程序,真是觉得下次写完程序后,应当再多花写心思来好好琢磨一下。 四、性能度量代码
时间度量的主要思想为: (1) 找寻随机的多个数,避免查找的特殊性; (2) 进行多轮测试,以使测试的时间准确性增加; (3) 不变改变数组的大小n,从而可以测出算法使用时间随n的变化规律(是否满足logn)。 请重点关注蓝色内容,其它部分请参考: “编程珠矶学习笔记(5)--两分搜索算法(折半查找算法)”。
#define MAXN 1000000 typedef int DataType; /*定义数据数型,可增加算法函数的通用性*/ DataType x[MAXN]; int n = 0;
/*t为待搜索的目标值*/ int binarysearch (DataType t) { int l, u, m; l = 0; u = n-1; while (l <= u) { /*目标仍在l和u之间*/ m = (l + u) / 2; /*折半*/ if (x[m] < t) { /*如果中间值小于目标值*/ l = m+1; /*l需要向u靠拢*/ } else if (x[m] == t) { /*如果等于t,则m即为要搜索的位置,返回即可*/ return m; } else { /*u需要向l靠拢*/ u = m-1; } } return -1; /*如果走到这,说明目标不在序列内,返回失败*/ }
/* 为使查找目标值多样化,特引入目标值数组*/ int p[MAXN];
/*打乱目标值数组内各元素的顺序,从而增加了搜索的随机性,从而避免了查找时间特殊化*/ void scramble(int n) { int i, j; DataType t; for (i = n-1; i > 0; i--) { j = (RAND_MAX*rand() + rand()) % (i + 1); t = p[i]; p[i] = p[j]; p[j] = t; } }
/*算法时间度量的脚手架函数*/ void timedriver() { int i, algnum, numtests, test, start, clicks;
/*可改变算法,n和测试的轮数,使测试函数有一定的扩展性和灵活性*/ while (scanf("%d %d %d", &algnum, &n, &numtests) != EOF) { /*初始化源数组内各元素的值*/ for (i = 0; i < n; i++) { x[i] = i; } /*如始化查找目标数组内的各元素*/ for (i = 0; i < n; i++) { p[i] = i; }
/*打乱目标数组各元素*/ scramble(n);
/*记录起始时间*/ start = clock(); for (test = 0; test < numtests; test++) { for (i = 0; i < n; i++) { switch (algnum) { /*调用被测函数,可以灵活的改变被测函数*/ case 1: assert(binarysearch(p[i]) == p[i]); break; case 2: /*other function*/; break; } } } /*记录函数运行总共所用时间*/ clicks = clock() - start;
/*打印测试结果*/ printf("%d\t%d\t%d\t%d\t%g\n", algnum, n, numtests, clicks, 1e9*clicks/((float) CLOCKS_PER_SEC*n*numtests)); } }
int main(void) { /*调用脚手架函数*/ timedriver();
return 0; }
0
相关文章读者评论发表评论 |