程序设计导论：Python语言实践

1.6.3　模拟

给定转换矩阵，模拟随机冲浪者行为所需的代码出人意料的简单，实现代码参见randomsurfer.py（程序1.6.2）。程序读取一个转换矩阵，根据规则进行Web冲浪。从页面0开始，移动跳转的页面数量由命令行参数指定。程序累计访问每个页面的次数，每个页面的访问次数除以全部访问页面的数量，结果为随机冲浪者访问该页面的概率。这个概率称为“页面排名（the page's rank）”。换言之，randomsurfer.py程序计算所有页面排名的估计值。

1. 一步随机移动

计算的关键是随机移动，随机移动由转换矩阵指定。程序通过变量page保存冲浪者的当前位置。矩阵p[][]第page行的各元素值指定了冲浪者跳转到页面j的概率。换言之，当冲浪者位于第page个页面，则程序的任务是基于转换矩阵第page行的概率分布（即一维数组p[page]），产生一个取值范围为0到n - 1之间的随机数。如何实现这个任务呢？程序使用random.random()函数产生一个取值范围为0到1之间的随机浮点数，但如何基于这个浮点数实现跳转到一个随机页面呢？一种解决方法是设想第page行的概率定义为在区间（0, 1）中n个区间的集合，每个区间的概率对应于区间长度。随机值r位于其中一个区间，其概率由区间长度精确指定。实现上述推断的代码如下：

变量total跟踪在行数组p[page]中定义的区间端点，for循环结构用于查找包含随机值r所在的区间。例如，假设在示例中冲浪者的当前位置为页面4，转换概率分布为0.47、0.02、0.47、0.02和0.02，变量total取值来自0.0、0.47、0.49、0.96、0.98和1.0。这些值表明概率定义了5个区间：（0，0.47）、（0.47，0.49）、（0.49，0.96）、（0.96，0.98）和（0.98，1），分别对应每一个页面。现在，假设random.random()函数返回结果值为0.71，从0到1到2到结束点递增j的值，表明0.71位于区间（0.49，0.96），所以冲浪者跳转到第3个页面（页面2）。程序接着按同样的计算方法计算p[2]，从而实现冲浪者的页面跳转。如果n的取值比较大，我们使用二分查找算法以显著提高计算速度（具体请参见4.2节习题第35题）。典型情况下，模拟可能需要大量的页面跳转，所以在这种情况下，提高查找效率十分必要。基于离散概率分布生成一个随机整数的示意图如图1-6-4所示。 ...