测试中的随机性(4)

发表于:2015-12-01来源:uml.org.cn作者:不详点击数: 标签:软件测试
返回页首 混排项目列表 让我们讨论一下混排项目列表。如果您有一个测试用例输入集合并且想以随机顺序将其全部输送到所测试系统中,则混排项目列表

返回页首

  混排项目列表

  让我们讨论一下混排项目列表。如果您有一个测试用例输入集合并且想以随机顺序将其全部输送到所测试系统中,则混排项目列表很有用。您可以将混排列表看作是生成项目的随机排列。这个异常棘手的问题曾是大量研究工作的主题。最佳的通用混排算法称为 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。

返回页首

  生成正态/高斯数字

  我将在本月专栏中演示的第四种方法是从钟形分布(通常称为正态或高斯分布)中生成数字。

  假设您要生成一些与一组人身高相对应的测试用例输入数据。可通过一种称为 Box-Muller 算法的非常巧妙的方法来生成正态分布的伪随机数字。用于创建图 1 中所示输出的代码的开头如下所示:

Gaussian g = new Gaussian();
double ht;
int outliers = 0;
Console.WriteLine("从平均值为 68.0 英寸、标准偏差为 6.0 英寸的" +
"正态/高斯分布生成 " +
"100 个随机身高 ->");

  我以一个程序定义的高斯对象为例。此对象执行所有工作并使用 Box-Muller 算法。可变身高将受一个正态分布值的约束。我还会初始化一个计数器以跟踪非正常值,即那些远高于或远低于平均身高的值。跟踪非正常值使我起码可以验证我的随机身高事实上是正态分布的。图 5 列出了生成并显示我的随机身高的代码。

原文转自:http://www.uml.org.cn/Test/200611225.htm