如何测试洗牌程序

如何测试洗牌程序 | 酷壳 – CoolShell.cn

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

我们有一个程序,叫ShuffleArray(),是用来洗牌的,我见过N多千变万化的ShuffleArray(),但是似乎从来没有要想过怎么去测试之。所以,我在面试中我经常会问如何测试ShuffleArray(),没想到这个问题居然难倒了很多有多年编程经验的人。对于这类的问题,其实,测试程序可能比算法更难写,代码更多。而这个问题正好可以加强一下我在《我们需要专职的QA吗?》中我所推崇的——开发人员更适合做测试的观点。

我们先来看几个算法(第一个比较诡异高深,第二个比较偷机取巧,第三个比较通俗易懂

递归二分方法

有一次是有一个朋友做了一个网页版的扑克游戏,他用到的算法比较诡异,是用递归+二分法,我说这个程序恐怕不对吧。他觉得挺对的,说测试了没有问题。他的程序大致如下(原来的是用Javascript写的,我在这里凭记忆用C复现一下):

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
34
35
//递归二分方法
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    {
        strncpy(temp, TestArr, MAXLEN);
        ShuffleArray_Recursive((char*)temp, MAXLEN);
    }
}

 

随便测试几次,还真像那么回事:

1
2
3
4
5
第一次:D C A B H E G F I J
第二次:C A B D H G E F J I
第三次:A B H F C E D G I J
第四次:B A H G E C D F J I
第五次:F B A D C E H G I J

快排Hack法

让我们再看一个hack 快排的洗牌程序(只看算法,省去别的代码):

1
2
3
4
5
6
7
8
9
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 );
}

运行个几次,感觉得还像那么回事:

1
2
3
4
5
第一次: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循环一次,然后随机交换两个数

1
2
3
4
5
6
7
8
9
10
void ShuffleArray_General(char* arr, int len)
{
    const int suff_time = len;
    for(int idx=0; idx        int i = rand() % len;
        int j = rand() % len;
        char temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}

跑起来也还不错,洗得挺好的。

1
2
3
4
5
第一次: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
11
12
     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
11
12
      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
11
12
      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算法

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;
    }
}

这个算法不难理解,看看测试效果(效果明显比前面的要好):

1
2
3
4
5
6
7
8
9
10
11
12
      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
11
12
      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%)

(全文完)

按照此文章的思路,我写了 一个delphi版本的Fisher_Yates算法

program Project1;

{$APPTYPE CONSOLE}
{$R *.res}

uses
  System.SysUtils;

const
  lens = 15;

type
  cards = array [1 .. lens] of char;

var
  S: cards;
  c: array [1 .. lens, 1 .. lens] of integer;
  i, j, cc: integer;

procedure cardcount(a: cards);
var
  i: integer;
begin
  inc(cc);
  for i := 1 to lens do
  begin
    inc(c[ord(a[i]) – 64, i]);
  end;
end;

procedure cardprint(a: cards);
var
  i: integer;
begin
  for i := 1 to lens do
    write(a[i] + ‘ ‘);
  writeln;
end;

procedure cardsort(a: cards);
var
  i, j: integer;
  temp: char;
begin
  i := lens;
  if i = 0 then
    exit;
  while i > 0 do
  begin
    j := random(maxint) mod i + 1;
    temp := a[i];
    a[i] := a[j];
    a[j] := temp;
    dec(i);
  end;
  cardcount(a);
  // cardprint(a);
end;

begin
  try
    cc := 0;
    fillchar(c, sizeof(c), 0);
    for i := 65 to 64 + lens do
      S[i – 64] := chr(i);
    // cardprint(S);
    for i := 1 to 1000 do
      cardsort(S);
    writeln(‘——————————————————————-‘);
    write(‘ ‘:2);
    for i := 65 to 64 + lens do
      write(chr(i):4);
    writeln;
    for i := 1 to lens do
    begin
      write(i:2);
      for j := 1 to lens do
        write(c[j, i]:4);
      writeln;
    end;
    readln;
  except
    on E: Exception do
      writeln(E.ClassName, ‘: ‘, E.Message);
  end;

end.