如何测试洗牌程序
我希望本文有助于你了解测试软件是一件很重要也是一件不简单的事。
我们有一个程序,叫ShuffleArray(),是用来洗牌的,我见过N多千变万化的ShuffleArray(),但是似乎从来没人去想过怎么去测试这个算法。所以,我在面试中我经常会问应聘者如何测试ShuffleArray(),没想到这个问题居然难倒了很多有多年编程经验的人。对于这类的问题,其实,测试程序可能比算法更难写,代码更多。而这个问题正好可以加强一下我在《我们需要专职的QA吗?》中我所推崇的——开发人员更适合做测试的观点。
我们先来看几个算法(第一个用递归二分随机抽牌,第二个比较偷机取巧,第三个比较通俗易懂)
目录
递归二分随机抽牌
有一次是有一个朋友做了一个网页版的扑克游戏,他用到的算法就是想模拟平时我们玩牌时用手洗牌的方式,是用递归+二分法,我说这个程序恐怕不对吧。他觉得挺对的,说测试了没有问题。他的程序大致如下(原来的是用Javascript写的,我在这里凭记忆用C复现一下):
//递归二分方法 const size_t MAXLEN = 10; const char TestArr[MAXLEN] = {'A','B','C','D','E','F','G','H','I','J'}; static char RecurArr[MAXLEN]={0}; static int cnt = 0; void ShuffleArray_Recursive_Tmp(char* arr, int len) { if(cnt > MAXLEN || len <=0){ return; } int pos = rand() % len; RecurArr[cnt++] = arr[pos]; if (len==1) return; ShuffleArray_Recursive_Tmp(arr, pos); ShuffleArray_Recursive_Tmp(arr+pos+1, len-pos-1); } void ShuffleArray_Recursive(char* arr, int len) { memset(RecurArr, 0, sizeof(RecurArr)); cnt=0; ShuffleArray_Recursive_Tmp(arr, len); memcpy(arr, RecurArr, len); } void main() { char temp[MAXLEN]={0}; for(int i=0; i<5; i++) { strncpy(temp, TestArr, MAXLEN); ShuffleArray_Recursive((char*)temp, MAXLEN); } }
随便测试几次,还真像那么回事:
第一次:D C A B H E G F I J 第二次:A G D B C E F J H I 第三次:A B H F C E D G I J 第四次:J I F B A D C E H G 第五次:F B A D C E H G I J
快排Hack法
让我们再看一个hack 快排的洗牌程序(只看算法,省去别的代码):
int compare( const void *a, const void *b ) { return rand()%3-1; } void ShuffleArray_Sort(char* arr, int len) { qsort( (void *)arr, (size_t)len, sizeof(char), compare ); }
运行个几次,感觉得还像那么回事:
第一次:H C D J F E A G B I 第二次:B F J D C E I H G A 第三次:C G D E J F B I A H 第四次:H C B J D F G E I A 第五次:D B C F E A I H G J
看不出有什么破绽。
大多数人的实现
下面这个算法是大多数人的实现,就是for循环一次,然后随机交换两个数
void ShuffleArray_General(char* arr, int len) { const int suff_time = len; for(int idx=0; idx<suff_time; idx++) { int i = rand() % len; int j = rand() % len; char temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } }
跑起来也还不错,洗得挺好的。
第一次:G F C D A J B I H E 第二次:D G J F E I A H C B 第三次:C J E F A D G B H I 第四次:H D C F A E B J I G 第五次:E A J F B I H G D C
但是上述三个算法哪个的效果更好?好像都是对的。一般的QA或是程序员很有可能就这样把这个功能Pass了。但是事情并没有那么简单……