模板
教程
环境
性能
功能
管理
测试中的随机性(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}。混排的目的是产生这三个项目的随机排列，其中每种排列的产生几率都均等。图 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
