如何测试洗牌程序

恒温 · 2012年11月20日 · 620 次阅读

Link http://coolshell.cn/articles/8593.html

我希望本文有助于你了解测试软件是一件很重要也是一件不简单的事。
我们有一个程序，叫 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 了。但是事情并没有那么简单……
如何测试
在做测试之前，我们还需要了解一下一个基本知识——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 | 101 283 317 208   65   23    3    0    0    0
B | 101 191 273 239 127   54   12    2    1    0
C | 103 167 141 204 229 115   32    7    2    0
D | 103 103   87 128 242 195 112   26    3    1
E | 104   83   62   67 116 222 228   93   22    3
F | 91   58   34   60   69 141 234 241   65    7
G | 93   43   35   19   44 102 174 274 185   31
H | 94   28   27   27   46   68   94 173 310 133
I | 119   27   11   30   28   49   64   96 262 314
J | 91   17   13   18   34   31   47   88 150 511
快排 Hack 法
看看对角线（从左上到右下）上的数据，很离谱！所以，这个算法也是错的。

1 2 3 4 5 6 7 8 9 10

A |   74 108 123 102   93 198   40   37   52 173
B | 261 170 114   70   49   28   37   76 116   79
C | 112 164 168 117   71   37   62   96 116   57
D |   93   91 119 221 103   66   91   98   78   40
E |   62   60   82   90 290 112   95   98   71   40
F |   46   60   63   76   81 318   56   42   70 188
G |   72   57   68   77   83   39 400 105   55   44
H |   99   79   70   73   87   34 124 317   78   39
I | 127 112 102   90   81   24   57   83 248   76
J |   54   99   91   84   62 144   38   48 116 264
大多数人的算法
我们再来看看大多数人的算法。还是对角线上的数据有问题，所以，还是错的。

1 2 3 4 5 6 7 8 9 10

A | 178   98   92   82 101   85   79 105   87   93
B |   88 205   90   94   77   84   93   86 106   77
C |   93   99 185   96   83   87   98   88   82   89
D | 105   85   89 190   92   94 105   73   80   87
E |   97   74   85   88 204   91   80   90 100   91
F |   85   84   90   91   96 178   90   91 105   90
G |   81   84   84 104 102 105 197   75   79   89
H |   84   99 107   86   82   78   92 205   79   88
I | 102   72   88   94   87 103   94   92 187   81
J |   87 100   90   75   76   95   72   95   95 215
正确的算法
下面，我们来看看性能高且正确的算法—— 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[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
这个算法不难理解，看看测试效果（效果明显比前面的要好）：

1 2 3 4 5 6 7 8 9 10

A | 107   98   83 115   89 103 105   99   94 107
B |   91 106   90 102   88 100 102   97 112 112
C | 100 107   99 108 101   99   86   99 101 100
D |   96   85 108 101 117 103 102   96 108   84
E | 106   89 102   86   88 107 114 109 100   99
F | 109   96   87   94   98 102 109 101   92 102
G |   94   95 119 110   97 112   89 101   89   94
H |   93 102 102 103 100   89 107 105 101   98
I |   99 110 111 101 102   79 103   89 104 102
J | 105 112   99   99 108 106   95   95   99   82
但是我们可以看到还是不完美。因为我们使用的 rand() 是伪随机数，不过已经很不错的。最大的误差在 20% 左右。
我们再来看看洗牌 100 万次的统计值，你会看到误差在 6% 以内了。这个对于伪随机数生成的程序已经很不错了。

1 2 3 4 5 6 7 8 9 10

A | 100095 99939 100451 99647 99321 100189 100284 99565 100525 99984
B | 99659 100394 99699 100436 99989 100401 99502 100125 100082 99713
C | 99938 99978 100384 100413 100045 99866 99945 100025 99388 100018
D | 99972 99954 99751 100112 100503 99461 99932 99881 100223 100211
E | 100041 100086 99966 99441 100401 99958 99997 100159 99884 100067
F | 100491 100294 100164 100321 99902 99819 99449 100130 99623 99807
G | 99822 99636 99924 100172 99738 100567 100427 99871 100125 99718
H | 99445 100328 99720 99922 100075 99804 100127 99851 100526 100202
I | 100269 100001 99542 99835 100070 99894 100229 100181 99718 100261
J | 100268 99390 100399 99701 99956 100041 100108 100212 99906 100019
如何写测试案例
测试程序其实很容易写了。就是，设置一个样本大小，做一下统计，然后计算一下误差值是否在可以容忍的范围内。比如：

样本：100 万次
最大误差：10% 以内
平均误差：5% 以内（或者：90% 以上的误差要小于 5%）

注意
————更新2012年11月20日————
其实，以上的测试只是测试了牌在各个位置的概率。这个还不足够好。因为还可能会现在有 Patten 的情况。如：每次洗牌出来的都是一个循环顺序数组。这完全可以满足我上面的测试条件。但是那明显是错的。所以，还需要统计每种排序组合的出现的次数，看看是不是均匀。
测试的确是一个很重要，并不简单的事情。谢谢所有参与讨论的人。
附录
————更新2012年11月20日————
之前忘贴了一个模拟我们玩牌洗牌的算法，现补充如下：
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[i];
arr[i] = arr[mid+i];
arr[mid+i] = 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   9924 10006 10048 10200   9939   9812 10080   9991
B |   9939   9962 10118 10007   9974 10037 10149 10052   9761 10001
C | 10054 10100 10050   9961   9856   9996   9853 10016   9928 10186
D |   9851   9939   9852 10076 10208 10003   9974 10052   9992 10053
E | 10009   9915 10050 10037   9923 10094 10078 10059   9880   9955
F | 10151 10115 10113   9919   9844   9896   9891   9904 10225   9942
G | 10001 10116 10097 10030 10061   9993   9891   9922   9889 10000
H | 10075 10033   9866   9857 10170   9854 10062 10078 10056   9949
I | 10045   9864   9879 10066   9930   9919 10085 10104 10095 10013
J |   9873   9958 10051 10041   9986 10008 10078 10001 10094   9910
（全文完）

（转载本站文章请注明作者和出处酷壳 – CoolShell.cn ，请勿用于任何商业用途）
————————============ 感谢 42qu.com 为本站提供 VPS ============————————