个人原创，转载请注明出处，谢谢！

一、 目的

(1)    使用简单的测试脚手架来测试函数的正确性；

(2)    使用简单的时间函数来度量函数的时间。

二、实现方法

1.       使用断言来保证捕捉异常:

int i = -999999;

#define assert(v) { if ((v) == 0) printf("  binarysearch bug %d %d\n", i, n); }

2.       使用测试脚手架进行正确性验证：
第一步：准备脚手架环境（包括各种必要的初始化）;
第二步：使用脚手架函数来调用被测函数；
第三步：捕捉异常

3.       度量算法使用时间：
第一步：记录开始时间；
第二步：调用被测算法函数；
第三步：记录结束时间；
start = clock();
test_function();
clicks = clock() - start;

 

三、功能正确性测试代码

请重点关注蓝色内容，其它部分请参考: “编程珠矶学习笔记（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;

}