Skip to Main Content
程序设计导论:Python语言实践
book

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

by 罗伯特 塞奇威克, 凯文 韦恩, 罗伯特 唐德罗
August 2021
Intermediate to advanced content levelIntermediate to advanced
350 pages
13h 15m
Chinese
Pearson
Content preview from 程序设计导论: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所示。 ...

Become an O’Reilly member and get unlimited access to this title plus top books and audiobooks from O’Reilly and nearly 200 top publishers, thousands of courses curated by job role, 150+ live events each month,
and much more.
Start your free trial

You might also like

Go程序设计语言

Go程序设计语言

艾伦A. A.多诺万, 布莱恩W. 柯尼汉
C++语言导学(原书第2版)

C++语言导学(原书第2版)

本贾尼 斯特劳斯特鲁普
Go语言编程

Go语言编程

威廉·肯尼迪

Publisher Resources

ISBN: 9787111549246