如何测试洗牌程序
我希望本文有助于你了解测试软件是一件很重要也是一件不简单的事。我们有一个程序，叫ShuffleArray()，是用来洗牌的，我见过N多千变万化的ShuffleArray()，但是似乎从来没人去想过怎么去测试这个算法。所以，我在面试中我经常会问应聘者如何测试ShuffleArray()，没想到这个问题居然难倒了很多有多年编程经验的人。对于这类的问题，其实，测试程序可能比算法更难写，代码更多。而这个问题正好可以加强一下我在《我们需要专职的QA吗？》中我所推崇的——开发人员更适合做测试的观点。我们先来看几个算法（第一个用递归二分随机抽牌，第二个比较偷机取巧，第三个比较通俗易懂）递归二分随机抽牌有一次是有一个朋友做了一个网页版的扑克游戏，他用到的算法就是想模拟平时我们玩牌时用手洗牌的方式，是用递归+二分法，我说这个程序恐怕不对吧。他觉得挺对的，说测试了没有问题。他的程序大致如下（原来的是用Javascript写的，我在这里凭记忆用C复现一下）：
//递归二分方法 const size_t MAXLEN = 10; const char TestArr = {'A','B','C','D','E','F','G','H','I','J'};static char RecurArr={0}; static int cnt = 0; void ShuffleArray_Recursive_Tmp(char* arr, int len) { if(cnt > MAXLEN || len <=0){ return; } int pos = rand() % len; RecurArr = arr; 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={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; arr = arr; arr = 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了。但是事情并没有那么简单……如何测试在做测试之前，我们还需要了解一下一个基本知识——PC机上是做不出真随机数的，只能做出伪随机数。真随机数需要硬件支持。但是不是这样我们就无法测试了呢，不是的。我们依然可以测试。我们知道，洗牌洗得好不好，主要是看是不是够随机。那么如何测试随机性呢？试想，我们有个随机函数rand()返回1到10中的一个数，如果够随机的话，每个数返回的概率都应该是一样的，也就是说每个数都应该有10分之1的概率会被返回。一到概率问题，我们只有一个方法来做测试，那就是用统计的方式。也就是说，你调用rand()函数100次，其中，每个数出现的次数大约都在10次左右。（注意：我用了左右，这说明概率并不是很准确的）不应该有一个数出现了15次以上，另一个在5次以下，要是这样的话，这个函数就是错的。举一反三，测试洗牌程序也一样，需要通过概率的方式来做统计，是不是每张牌出现在第一个位置的次数都是差不多的。于是，这样一来上面的程序就可以很容易做测试了。下面是测试结果（测试样本1000次——列是每个位置出现的次数，行是各个字符的统计，出现概率应该是1/10，也就是100次）：递归随机抽牌的方法很明显，这个洗牌程序太有问题。算法是错的！
1 2 3 4 5 6 7 8 9 10 ---------------------------------------------------- A | 101283317208 65 23 3 0 0 0 B | 101191273239127 54 12 2 1 0 C | 103167141204229115 32 7 2 0 D | 103103 87128242195112 26 3 1 E | 104 83 62 67116222228 93 22 3 F |91 58 34 60 69141234241 65 7 G |93 43 35 19 44102174274185 31 H |94 28 27 27 46 68 94173310133 I | 119 27 11 30 28 49 64 96262314 J |91 17 13 18 34 31 47 88150511
快排Hack法看看对角线（从左上到右下）上的数据，很离谱！所以，这个算法也是错的。
1 2 3 4 5 6 7 8 9 10----------------------------------------------------- A | 74108123102 93198 40 37 52173 B |261170114 70 49 28 37 76116 79 C |112164168117 71 37 62 96116 57 D | 93 91119221103 66 91 98 78 40 E | 62 60 82 90290112 95 98 71 40 F | 46 60 63 76 81318 56 42 70188 G | 72 57 68 77 83 39400105 55 44 H | 99 79 70 73 87 34124317 78 39 I |127112102 90 81 24 57 83248 76 J | 54 99 91 84 62144 38 48116264
大多数人的算法我们再来看看大多数人的算法。还是对角线上的数据有问题，所以，还是错的。
1 2 3 4 5 6 7 8 9 10 ----------------------------------------------------- A |178 98 92 82101 85 79105 87 93 B | 88205 90 94 77 84 93 86106 77 C | 93 99185 96 83 87 98 88 82 89 D |105 85 89190 92 94105 73 80 87 E | 97 74 85 88204 91 80 90100 91 F | 85 84 90 91 96178 90 91105 90 G | 81 84 84104102105197 75 79 89 H | 84 99107 86 82 78 92205 79 88 I |102 72 88 94 87103 94 92187 81 J | 87100 90 75 76 95 72 95 95215
正确的算法下面，我们来看看性能高且正确的算法—— Fisher_Yates算法
void ShuffleArray_Fisher_Yates(char* arr, int len) { int i = len, j; char temp; if ( i == 0 ) return; while ( --i ){ j = rand() % (i+1); temp = arr; arr = arr; arr = temp; } }
这个算法不难理解，看看测试效果（效果明显比前面的要好）：
1 2 3 4 5 6 7 8 9 10 ----------------------------------------------------- A |107 98 83115 89103105 99 94107 B | 91106 90102 88100102 97112112 C |100107 99108101 99 86 99101100 D | 96 85108101117103102 96108 84 E |106 89102 86 88107114109100 99 F |109 96 87 94 98102109101 92102 G | 94 95119110 97112 89101 89 94 H | 93102102103100 89107105101 98 I | 99110111101102 79103 89104102 J |105112 99 99108106 95 95 99 82
但是我们可以看到还是不完美。因为我们使用的rand()是伪随机数，不过已经很不错的。最大的误差在20%左右。我们再来看看洗牌100万次的统计值，你会看到误差在6%以内了。这个对于伪随机数生成的程序已经很不错了。
1 2 3 4 5 6 7 8 9 10 ------------------------------------------------------------------------- A | 10009599939 1004519964799321 100189 10028499565 10052599984 B |99659 10039499699 10043699989 10040199502 100125 10008299713 C |9993899978 100384 100413 1000459986699945 10002599388 100018 D |999729995499751 100112 100503994619993299881 100223 100211 E | 100041 1000869996699441 1004019995899997 10015999884 100067 F | 100491 100294 100164 100321999029981999449 1001309962399807 G |998229963699924 10017299738 100567 10042799871 10012599718 H |99445 1003289972099922 10007599804 10012799851 100526 100202 I | 100269 1000019954299835 10007099894 100229 10018199718 100261 J | 10026899390 1003999970199956 100041 100108 10021299906 100019
如何写测试案例测试程序其实很容易写了。就是，设置一个样本大小，做一下统计，然后计算一下误差值是否在可以容忍的范围内。比如：样本：100万次最大误差：10%以内平均误差：5%以内 （或者：90%以上的误差要小于5%）注意其实，以上的测试只是测试了牌在各个位置的概率。这个还不足够好。因为还可能会现在有Patten的情况。如：每次洗牌出来的都是一个循环顺序数组。这完全可以满足我上面的测试条件。但是那明显是错的。所以，还需要统计每种排列的出现的次数，看看是不是均匀。但是，如果这些排列又是以某种规律出现的呢？看来，这没完没了了。测试的确是一个很重要，并不简单的事情。谢谢所有参与讨论的人。附录之前忘贴了一个模拟我们玩牌洗牌的算法，现补充如下：
void ShuffleArray_Manual(char* arr, int len) { int mid = len / 2; for (int n=0; n<5; n++) { //两手洗牌 for (int i=1; i<mid; i+=2) { char tmp = arr; arr = arr; arr = tmp; } //随机切牌 char *buf = (char*)malloc(sizeof(char)*len); for(int j=0; j<5; j++) { int start= rand() % (len-1) + 1; int numCards= rand()% (len/2) + 1; if (start + numCards > len ) { numCards = len - start; } memset(buf, 0, len); strncpy(buf, arr, start); strncpy(arr, arr+start, numCards); strncpy(arr+numCards, buf, start); } free(buf); } }
我们来看看测试结果：（10万次）效果更好一些，误差在2%以内了。
1 2 3 4 5 6 7 8 9 10 ------------------------------------------------------------------------- A |10002 9998 9924100061004810200 9939 981210080 9991 B | 9939 99621011810007 9974100371014910052 976110001 C |100541010010050 9961 9856 9996 985310016 992810186 D | 9851 9939 9852100761020810003 997410052 999210053 E |10009 99151005010037 9923100941007810059 9880 9955 F |101511011510113 9919 9844 9896 9891 990410225 9942 G |1000110116100971003010061 9993 9891 9922 988910000 H |1007510033 9866 985710170 9854100621007810056 9949 I |10045 9864 987910066 9930 991910085101041009510013 J | 9873 99581005110041 998610008100781000110094 9910
文章出自：http://www.uml.org.cn/Test/201302201.asp
好像很腻害的样子:loveliness:
页:
[1]
