模板
教程
環境
性能
功能
管理
測試中的隨機性(4)
|
if (z < -2.580 || z > 2.580) { Console.Write("充分證明 (1%) 模式不是隨機生成的："); Console.WriteLine(z < -2.580 ? "游程太少。" : 游程太多。"); } |
我以百分之一的顯著性水平執行了一次所謂的雙側檢驗。如果標準化檢驗統計量的絕對值大于 2.580，則不嚴格地說，這意味著所分析模式由隨機過程生成的幾率不到百分之一。值 2.580 源自統計表。如果檢驗統計量為負值，則實際游程數小于預期游程數，反之亦然。在圖 2 中，我也在查找證明該模式不是隨機生成的不充分證據。請注意，您在任何時候都不能肯定地說給定模式是隨機生成的;您只能通過檢驗來了解是否存在統計證據來證明該模式不是隨機生成的。
混排項目列表
讓我們討論一下混排項目列表。如果您有一個測試用例輸入集合并且想以隨機順序將其全部輸送到所測試系統中，則混排項目列表很有用。您可以將混排列表看作是生成項目的隨機排列。這個異常棘手的問題曾是大量研究工作的主題。最佳的通用混排算法稱為 Fisher-Yates 算法。有時候也稱之為 Knuth 混排算法。這種算法極其簡單。假設有一個項目數組：
|
string[] animals = new string[] { "ant", "bat", "cow", "dog", "elk", "fox" }; |
如果用 Fisher-Yates 算法的最常用形式來混排這列動物，將得到以下內容：
|
for (int i = 0; i < animals.Length; i++) { int r = objRan.Next(i, animals.Length); string temp = animals[r]; animals[r] = animals[i]; animals[i] = temp; } |
我迭代要混排的數組的每一個索引。我在當前索引和數組結尾之間選擇一個隨機位置，然后交換當前索引和隨機索引處的項目。不正確的混排算法非常常見。下面的例子就特別棘手?？紤]一下此嘗試：
|
for (int i = 0; i < animals.Length; i++) { // int r = objRan.Next(i, animals.Length); // 正確 int r = objRan.Next(0, animals.Length); // 不正確 string temp = animals[r]; animals[r] = animals[i]; animals[i] = temp; } |
此代碼將生成并執行，但最終所得的重排列表將偏向于項目的某些種排列。為例示這種情況，假設要混排的原始列表中只有三個項目，即 {ABC}?；炫诺哪康氖钱a生這三個項目的隨機排列，其中每種排列的產生幾率都均等。圖 3 中的表顯示了使用剛才所示的不正確混排算法后產生的所有 27 種可能的結果。
圖 3 中的表中的第一行表示，第一次迭代整個混排循環時，i 的值為 0，并且隨機索引 r 的值為 0。由于初始列表為 {ABC}，因此交換后的列表仍為 {ABC}。第二次迭代時，i 為 1 且隨機索引為 0。交換后，列表現在為 {BAC}。最后一次迭代時，i 為 3 且隨機索引為 0。交換后，最終列表排序為 {CAB}。這三個項目存在六種可能的最終排列。如果您要計算圖 4 的表中每個結果出現的次數，則將得到以下結果：
|
{ABC} = 4 次 {ACB} = 5 次 {BAC} = 5 次 {BCA} = 5 次 {CAB} = 4 次 {CBA} = 4 次 |
換言之，并不是所有排列的產生幾率都相等。請注意，A 在第一個位置出現 9 次，B 在第一個位置出現 10 次，C 在第一個位置出現 8 次。如果在賭博游戲模擬中使用這種不正確的混排算法，則會產生嚴重的問題。
如果使用正確的混合算法，您最終可能得到的結果如圖 4 中所示(注意 r 值從來不小于 i 值)。此時，這三個項目的六種可能的最終排列中每一種排列的產生概率都是相等的，某字母出現在某特定位置的概率也是相等的。同時還要注意，不需要進行第三次遍歷，因為它只會與自己交換數組中的最后一個值。因此，正確算法中的循環可轉到 animals.Length - 1 而不是 animals.Length。
原文轉自：http://www.uml.org.cn/Test/200611225.htm
