如何测试洗牌程序

如何测试洗牌程序

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

我们有一个程序,叫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. 对比算法不做100万次统计值有失公平,
    至于为什么说伪随机数的性能差也没有解释……

  2. 也等着……不过感觉如果真模拟显示中的洗牌,每次洗牌,都是在原有顺序上相互insert,不知道算法上是怎么……

  3. 第三段代碼有誤
    for(int idx=0; idx int i = rand() % len;
    int j = rand() % len;
    應該是
    for(int idx=0; idx<suff_time; ++idx) {
    int i = rand() % len;
    int j = rand() % len;

  4. 即使算法正确,还是有问题的:「Note that for even rather small len(x), the total number of permutations of x is larger than the period of most random number generators; this implies that most permutations of a long sequence can never be generated.」(Python 文档说的)

  5. 依云 :
    即使算法正确,还是有问题的:「Note that for even rather small len(x), the total number of permutations of x is larger than the period of most random number generators; this implies that most permutations of a long sequence can never be generated.」(Python 文档说的)

    对我也想说这个. 对于长度为n的序列, 结果应该均匀分布在n!中情况上. 但是由于随机种子只有2^32(或2^64, whatever)个, 当n!大于种子个数的时候(这很容易)就会分布不均匀. 事实上, 只有2^64/n!的情况被覆盖了. n越大, 结果越糟糕.

  6. 你朋友的算法,从测试结果也很能看出问题啊:AB总在前面出现,IJ总在后边出现。
    但是并不能就此说你朋友的算法就是错的,其实还要看你朋友的游戏是什么样的游戏。如果发牌的游戏不是那种需要在取牌过程中就亮什么牌的打法,用户仅仅关心所有牌都到手之后,手上有哪些牌。那么,AB总在前面出现,IJ总在后面出现,并没有什么关系。如果是3个人在打牌,那验证条件只要弱化成在3k+1、3k+2、3k+3上出现是均匀的就好。算法对不对还是和具体的应用场景有些关系。

  7. 文中的测试更像是来评估这个算法而不是测试程序,算法的对错在设计review的时候是要检查的,像这种最好是能证明一下是平均的,而这种unit test类的测试这种表象的观察很难保证算法的正确性。就像第一眼你看看1,2两种算法大概能看出点好像不太平均,然后统计个几千次前两个就能“看”出来概率是不平均的,第三个在100万次的情况下“看上去”是平均分布的,但事实上并不一定。
    一个完美shuffle要达到的目标是元素a出现在i位置是1/n(总数为n). 文中结论说5%以内可以接受的话,那在52张扑克牌的洗牌里,如果有两个算法,一个把红桃A放在牌顶的概率是1/52,另一个是1/53,这两个在统计实验里是看不出来的(它们只是2%左右的误差)

    比如文中的fisher_yates算法,我可以把
    j = rand() % (i+1)
    改成
    j = rand() % 101*(i+1) % 100*(i+1) % (i+1)
    这样在前面的那些元素更容易被挑中,尽管这个多出的概率很低,一般测试很难观察到。

    而实际上不用改文中的那个程序就可能有这个bias. 假设rand() 能平均的生成一个0~32767(rand_max)之间的一个数,这样如果用rand() % 10来试图随机的取一个0~9之间的数,得到8和9的概率比其它几个数到低1/3277.而且这个偏差不是伪随机数的偏差,是这个算法里带来的。

    所以我想说的是用test来检测算法的正确性有点像贵站之前的一篇文章提到的散弹枪编程,test能在多大程度上发现问题在于“看”得有多细,但是终究无法避免算法根本上的问题。

  8. 不过,严格的说来,还应测试相邻牌之间的关系,如下面这个故意找茬的算法:):

    void ReverseArray( char* arr, int len )
    {
         if( len &lt;= 1 ) return;
         for( int i = 0; i &lt; len / 2; ++i )
         {
             char tmp = arr[i];
             arr[i] = arr[len - 1 - i];
             arr[len - 1 - i] = tmp;
         }
    }
    
    void ShuffleArray_Shift(char* arr, int len)
    {
        int shift = rand() % len;
        ReverseArray( arr, shift );
        ReverseArray( arr + shift, len - shift );
        ReverseArray( arr, len );
    }
    1. 你说的没错,是会有这样的情况,而且,这样的情况可能会更变复,隐藏地更深。我只是把问题简化一下,这样好说明测试方法。另外,这是建立在算法实现应该不会出现这样的情况,并对rand()函数的信任的基础上的。总之,你提示的很对。

  9. 试想,我们有个随机函数rand()返回1到10中的一个数,如果够随机的话,每个数返回的概率都应该是一样的,也就是说每个数都应该有10分之1的概率会被返回。

    这个是个弱条件,
    比如将一个数组向左平移rand()个单位,也满足这个条件

  10. gallium :
    所以我想说的是用test来检测算法的正确性有点像贵站之前的一篇文章提到的散弹枪编程,test能在多大程度上发现问题在于“看”得有多细,但是终究无法避免算法根本上的问题。

    同意gallium的看法,如果要真的刨根究底的话,文中的检测方法太过简单了。当然,如果连这样简单的检测都通不过的算法肯定不行。涉及到概率之后,很多问题相当复杂。

  11. 呵呵,真实世界的洗牌,洗得绝对好得话,最后每个人手上的牌都是可以算出来的。其实就是不好的洗牌了。@ev4n

  12. 测试随机性很麻烦的,最好的方案就是理论证明算法,测试保证算法是正确实现的。而不是测试保证算法是随机的。除非你测试保证n!种排列的概率都是相等的,而且这还有很多测试的局限性

  13. 还有,上面的统计也只是初步的测试,还没有测试炸弹出现的概率阿。
    我这个程序应该可以的,就是效率差了一些;
    嗯,
    a_b[]={};
    a_e[];
    for (i=0;i<num;i++){
    // get the n from left
    n = rand(num-i);for (j=0;j<num;j++)
    {
    if (a_b[j]=N)n++;
    if (n==j){a_e[i]=a_b[n];a_b[n]=N;continue}
    }}

  14. 测试比较有效,但是如果加上测试炸弹的概率应该更好。 模拟手洗的效果差,是不是我们手洗的时候也是不够随机呢? 或者多洗几次会效果好一些 (10秒前)

  15. 要是能算出来,就是洗得不好。因为真正的随机的定义就是无法使用计算推导出以及无法预测的,这个是核心。所以真随即序列是无法预测和计算的。可以参考IEEE 1363标准中的叙述@勇敢的Springz

  16. @k
    第三个算法的正确性依赖于suff_time的选择。假设suff_time=N,数组长度=n,如果计算一下shuffle最后每个字母位置固定不变的概率的话,可以知道它等于(1-(1-p)^N-Np(1-p)^(N-1))/n+(1-p)^N+N/n^2(1-p)^(N-1),其中p=(2n-1)/n^2。观察这个式子,当取N=n的时候(也就是文中的情况),并且令N趋向于无穷,这个概率会趋向于常数e^-2(约等于.15左右),这与我们期待的1/n相差甚远。一个正确的算法,应该至少取N=n^(1+epsilon)。这样的话当N趋向于无穷时,这个概率才会等于1/n。但是,即便如此,这个估计依然是有偏的(当N不够充分大的时候,概率离1/n比较远)。

  17. 这个应该是制定需求时就规定的吧?

    一般娱乐的话,洗不太匀问题还不太大,不过用户一定会发现坐某些位置总会拿好牌的……然后由于没有统计数据,会被当作小概率事件。

    国外赌场用的话,这东西威胁就太大了。好像前些年就有个“因为洗牌算法用的随机数不好,可以通过反向分析找到其随机序列”而导致赌场被攻击的。

  18. @gallium
    说得对,测试只能*验证*算法没有明显错误,而不能证明算法的正确(和物理实验一样的)。
    我在考虑既然要考虑 2-gram,那么要不要考虑 3-gram 呢?——洗牌的目标究竟是满足什么?

  19. @slayerxj
    这样的测试要是以一定的小概率通不过还是正常的,因为本来结果就是随机分布的(当然不是均匀分布)。所以测试过不过还得看RP啊……

    PS: 我终于知道大家为什么要改名评论了……

  20. 一直觉得洗牌很难,碰巧看到了这一篇 http://www.guokr.com/article/23047/ ,正好是讲手工洗牌的。也就是说手工洗牌本身就是非随机的洗法,想随机,要多洗几次。

    btw:mobile主题下,留言不能输入中文,能粘贴。

  21. static const char* list[][10] = {
    {0,1,2,3,4,5,6,7,8,9},
    {1,2,3,4,5,6,7,8,9,0},
    {2,3,4,5,6,7,8,9,0,1},
    ………..
    }

    static int cnt = 0;

    return list[cnt++%10];

    这个算法也能非常完美的通过lz的测试用例。

  22. 这个是如何设计统计检验的问题啊。检验是否均匀分布的话,我想到几点:
    1、最简单的卡方检验是否满足均匀分布,alpha可以自行控制。
    2、plot 均值的方差(某区间频次的平均数的方差)与样本数(每次permutation次数)的平方根,这两者应该成个线性关系。
    3、 i个区间和第j个区间的Wilcoxon rank-test验证无相关性。

  23. 另:这种验证,如果有一个已知是正确的算法。那么测试另一个的正确性,会容易n多倍。

  24. 感觉非常适合作为笔试题,比倒序字符串、算斐波那契数列什么的要有趣得多,而且可以同时检验算法和效率两个方向

    但问题本身来说,测试应该覆盖不到这个层面,而且如果是核心功能的话,本来就应该单拿出来讨论算法的(比方说 Diablo 的掉落机制、卡马克在 Quake 里的开平方等)

  25. 本来想看看您是怎么做的,结果呢,呵呵,一句话我就没兴趣了。
    ==============
    而这个问题正好可以加强一下我在《我们需要专职的QA吗?》中我所推崇的——开发人员更适合做测试的观点。
    ==============
    您这个洗牌测试程序,说白了,就是白盒测试。白盒测试,要么就是开发人员自己做,要么就是结对编程的另外一个人去复查/走查代码,写单元测试。

    您先搞清楚QA的定义吧。

  26. 可不可以先求全排列,然后随机抽一个?
    这样的话,算法的正确性就几乎全部集中在最后一个“随机”抽选上面了。

  27. 最近刚看了《STL源码剖析》,STL里提供了一个将容器元素打乱的算法random_shuffle(),思想和Fisher_Yates算法差不多,只不过迭代的顺序是从小到大,用C语言表示大概如下:
    void ShuffleArray_STL(char* arr, int first, int last)
    {
    int i, j;
    char temp;

    for(i = start + 1; i != last; i++){
    j = first + rand() % (i – first + 1);
    temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
    }
    }

  28. 个人觉得**Fisher_Yates算法**并不比**大多数人的算法**在结果上更好,只是它的效率比较高。

    样本数 1000w,取最大误差,结果如下:

    大多数人的算法:

    min: 99404 max: 100845
    min: 99404 max: 100845
    min: 99256 max: 100955
    min: 99256 max: 100955
    min: 99256 max: 100955
    min: 99256 max: 100955
    min: 99189 max: 100874
    min: 99189 max: 100874
    min: 99189 max: 100874
    min: 99189 max: 100874
    min: 99245 max: 100818
    min: 99245 max: 100818
    min: 99245 max: 100818
    min: 99245 max: 100818
    min: 99169 max: 100875
    min: 99169 max: 100875
    min: 99169 max: 100875
    min: 99169 max: 100875
    min: 99081 max: 100715
    min: 99081 max: 100715

    Fisher_Yates算法:
    min: 99427 max: 100615
    min: 99427 max: 100615
    min: 99427 max: 100615
    min: 99427 max: 100615
    min: 99301 max: 100627
    min: 99301 max: 100627
    min: 99301 max: 100627
    min: 99301 max: 100627
    min: 99301 max: 100627
    min: 99301 max: 100627
    min: 99335 max: 100559
    min: 99335 max: 100559
    min: 99335 max: 100559
    min: 99335 max: 100559
    min: 99335 max: 100559
    min: 99335 max: 100559
    min: 99282 max: 100662
    min: 99282 max: 100662
    min: 99282 max: 100662
    min: 99282 max: 100662

    即使取1000个样本,也没有出现像楼主那个 200 的数值(最多120左右)。

    程序在这里:
    https://gist.github.com/4116421

  29. rand()%mod 取模认为是在[0,mod)上的均匀分布本身就不科学,因为RAND_MAX不一定能被mod整除,参考http://www.azillionmonkeys.com/qed/random.html
    建议先实现一个[0,mod)上的均匀分布,再用来实验

发表回复

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