|
我希望本文有助于你了解測試軟件是一件很重要也是一件不簡單的事。
我們有一個程序，叫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
|
|
模板
教程
環境
性能
功能
管理
