如何测试洗牌程序

如何测试洗牌程序

我希望本文有助于你了解测试软件是一件很重要也是一件不简单的事。

我们有一个程序,叫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%)

注意

其实,以上的测试只是测试了牌在各个位置的概率。这个还不足够好。因为还可能会现在有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[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 ,请勿用于任何商业用途)

好烂啊有点差凑合看看还不错很精彩 (30 人打了分,平均分: 4.10 )
Loading...

如何测试洗牌程序》的相关评论

  1. @Daniel
    交换只是手段,Fisher_Yates其实就是从一堆里随机拿出一个放在最后一位,然后从剩下的里面再随机拿出一个放在倒数第二位。。。很简单的想法

  2. 不得不吐槽一下这些验证只是必要条件。
    也就是说,如果元素1, 2, …, n中任意一个元素在位置p_i(1 <= i <= n)出现的概率是1/n
    也不能说明这就是良好的随机置换(random permutation)生成算法
    良好的随机置换算法应该保证,对于n!个置换中的任意一个,在一次生成应该有1/(n!)的概率获得。
    前者只是后者的必要条件而已。

  3. 全文除了这句话以外都很好。“你调用rand()函数100次,其中,每个数出现的次数大约都在10次左右。(注意:我用了左右,这说明概率并不是很准确的)不应该有一个数出现了15次以上,另一个在5次以下,要是这样的话,这个函数就是错的。”———————–100次的样本空间出现15%这样的概率,不能说明函数有错。严格来说,就算样本空间是100W次都不能这样讲。这需要严格的数学证明的。
    所以说,一般人不要自己脑袋乱想个算法就拿来用,因为根本没经过严格的数学证明很难保证正确性的,最好能套用经典算法(都经过严格的数学证明),实在不行就改进经典算法来达到自己的目的。如果非要自己来创新算法,最好用数学证明一下,如果数学能力不够,就写case来尽量保证正确性

  4. 而且即便是fisher-yates算法,有些情况他也是永远不会出现的。只能做到尽量模拟随机。

  5. 我来说个Knuth的洗牌算法,源于TAOCP第三卷的习题。
    第一步:为每张牌生成一个随机数
    第二步:按这个随机数进行排序
    个人觉得是最简单的。

  6. 一个洗牌程序的功能是,对于长度为n的两两不同的数组,输出的任何一个排列的概率相等,也就是1/n!。可以验证,Fisher-Yates算法是可以保证这一点的。
    最后一个洗牌程序包括两个部分:第一部分“两手洗牌”,实际上是个确定变换,也就是说,输入序列就能直接决定这一步的输出,因此本身不带来随机性。第二部分“随机切牌”,是先随机从牌序列中切下一个部分(可能是全部),然后在这个切下的部分中随机切成两个部分,交换这两个部分的位置。通过5次随机切牌不可能达到相应的随机性。因此这个洗牌算法洗出的结果并不是“最大熵”的。
    那为何测试算法得到的结果看上去还不错呢?实际上该测试算法是有问题的,因为每张牌在每个位置上概率均等,并不能证明洗牌的结果是“最大熵”的,因为这里没考虑每张牌出现位置的“相关性”。
    另外,也能构造有问题的洗牌算法,满足测试程序的要求:
    比如将n张牌构成的序列随机切成两个部分(其中第一个部分的长度允许为0),然后交换这两个部分的位置。从测试结果来看,肯定能得到每张牌在每个位置上出现的概率均等的结果。

  7. rand_select(l):
    0, if l is empty, then end
    1, r = rand(len(l))
    2, o = l[r]
    3, l.remove(o)
    4, output(o)
    5, goto 0
    省事归省事,不过……

  8. 我测试了文章最后给出的 双手洗牌+切牌 算法,误差率确实可以达到比较低的数值,但是我用该算法去洗一副完整的52张扑克,将每一次的结果都记录到文本,之后分析10w、100w手牌的重复率。发现重复率竟然惊人的高,差不多有千分之一的概率,这说明这种算法有很大缺陷。
    随后我又用Fisher_Yates算法重复上述实验,发现在1000w手牌中也不会出现重复的情况。该算法也是Python random.shullfe()所采用的算法。

  9. 想问一下这个测试程序是怎么写的?循环 1000 次调用 shuffle 函数吗?如果是取系统时间作为种子,那么很有可能两次调用 shuffle 时取到的系统时间是一样的,这样产生的随机数序列也是一样的。有没有可能是因为这个原因导致了统计结果不均匀呢?

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注