如何测试洗牌程序 | 酷 壳 - CoolShell.cn
Read full article from 如何测试洗牌程序 | 酷 壳 - CoolShell.cn
下面，我们来看看性能高且正确的算法—— Fisher_Yates算法
1
2
3
4
5
6
7
8
9
10
11
12
13
| 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; }} |
在做测试之前，我们还需要了解一下一个基本知识——PC机上是做不出真随机数的，只能做出伪随机数。真随机数需要硬件支持。但是不是这样我们就无法测试了呢，不是的。我们依然可以测试。
我们知道，洗牌洗得好不好，主要是看是不是够随机。那么如何测试随机性呢？
试想，我们有个随机函数rand()返回1到10中的一个数，如果够随机的话，每个数返回的概率都应该是一样的，也就是说每个数都应该有10分之1的概率会被返回。
一到概率问题，我们只有一个方法来做测试，那就是用统计的方式。也就是说，你调用rand()函数100次，其中，每个数出现的次数大约都在10次左右。（注意：我用了左右，这说明概率并不是很准确的）不应该有一个数出现了15次以上，另一个在5次以下，要是这样的话，这个函数就是错的。
举一反三，测试洗牌程序也一样，需要通过概率的方式来做统计，是不是每张牌出现在第一个位置的次数都是差不多的。
于是，这样一来上面的程序就可以很容易做测试了。
下面是测试结果（测试样本1000次——列是每个位置出现的次数，行是各个字符的统计，出现概率应该是1/10，也就是100次）：
其实，以上的测试只是测试了牌在各个位置的概率。这个还不足够好。因为还可能会现在有Patten的情况。如：每次洗牌出来的都是一个循环顺序数组。这完全可以满足我上面的测试条件。但是那明显是错的。所以，还需要统计每种排列的出现的次数，看看是不是均匀。但是，如果这些排列又是以某种规律出现的呢？看来，这没完没了了。
之前忘贴了一个模拟我们玩牌洗牌的算法，现补充如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
| 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); }} |
