原文写于2010-06-23
=================
今天遇到了一件好事和一件坏事,好事是我在图书馆预定的编程珠玑终于到我手上了,坏事是我准备留到暑假看的GEB被人预定了,我必须在7月4日前还给图书馆。。于是,我看了大半天的编程珠玑,于是,我的形式语言与自动机、数据库考试又危险了。。
对于这本被誉为历史上最伟大的计算机科学著作之一的奇书,我一开始读还没领悟出多少精华,第一章介绍了一种我从未使用过的性能分析器,大体是帮助程序员观察各个运算和函数所占用的时间,从而有针对性地对程序进行优化;第二章推崇了一种我闻所未闻的语言Awk,它不需要定义变量,有时可以隐含for循环,数组可以直接引用字符串(像 array["hello"] = 1);第三章是关于程序的调试的,主要方法是对程序进行单元测试;第六章给出了许多程序设计的箴言。直到我跳到第十三章,终于看到了感到收获挺大的内容,下面隆重推出~
第十三章:绝妙的取样
关于生成随机数的算法,这个问题之所以能引起我的注意,是因为这个学期帮心理系编写了一个程序,给他们做实验用,实验中要求生成n个随机数,其中每连续的m个不能出现重复数字。我当时用了最暴力的方法,结果效率不太理想,运气不好时生成一组数据会需要将近1分钟,于是我花了几个小时的时间把数据全生成出来,然后每次直接调生成好的数据进来。后来我把这个程序交给了心理系,本来说要付我酬劳的,后来没了下文,有没有往我的账户里打钱我也不知道,本以为这将是我的第一桶金的。。。
回到正题,讨论的问题很简单,就是生成m个[1, n]内不重复的随机数:
约定:random(l, r)表示等概率地生成[l, r]内的任意一个整数,S存的是我们生成的随机数
最简单的方法就是
size = 0;
while(size < m) {
x = random(1, n);
if(x is not in S) {
insert x in S;
size = size + 1
}
}
当然,这样就会遇到我之前的尴尬。我们先从算法的正确性来看其中的问题所在,这里我们计算的是m元组生成的概率,即不计顺序,(1, 2, 3) = (2, 1, 3):
如果算法正确的话,每个元组是等概率生成的,即生成任意一个m元组的概率应该是pm = 1 / C(m, n),其中C(m, n)表示组合数
①当m = 1时,显然p = 1 / n = 1 / C(1, n),成立
②假设m = k时,pk = 1 / C(k, n),而1个k元组相对应于k!种排列,每个排列生成的概率是1 / A(k, n),A(k, n)表示排列数,等于C(k, n) * k!
当m = k + 1时,对于k + 1元组的其中任意一种排列,它的概率是1 / A(k, n) * 1 / n * (k / n + (k / n)^2 + (k / n)^3 + …),
其中(k / n + (k / n)^2 + (k / n)^3 + …是一个几何级数,等于1 / (1 - k / n),
原式 = 1 / A(k, n) * 1 / n * 1 / (1 - k / n) = (n - k - 1)! / n! = 1 / A(k + 1, n)
由于上述概率是k + 1元组中的任意一种排列,故pk+1 = (k + 1)! / A(k + 1, n) = 1 / C(k + 1, n)
由①和②可得,该算法生成任意一个m元组的概率pm = 1 / C(m, n)
现在算法的正确性是证明了,但是我们看到计算过程中,几何级数那块,分母是以n的幂的形式出现的,而最终得到的概率是n的阶乘的形式,有没有一种更直接的方法呢?Robert W. Floyd给出了一种简洁的算法:
for(i = n - m + 1; i <= n; ++i) {
x = random(1, i);
if(x is not in S)
insert x in S;
else
insert i in S;
}
用这个算法,对m元组中的每个数只要调用一次random函数即可,非常之高效,对于它的正确性的证明在解决了下一个问题后给出。
上面的算法,生成的仅仅是m元组,并不要求排列上的随机,而更多的时候我们需要生成的是m个[1, n]内不重复的随机排列的随机数,
当然最直接的方法是先生成m元组,然后随机地去打乱它。
但是,对floyd的算法稍加改进后,我们可以得到更简介高效的算法来完成这个任务:
for(i = n - m + 1; i <= n; ++i) {
x = random(1, i);
if(x is not in S)
insert x in front of S;
else
insert i in S after x;
}
比如n = 10, m = 5,我们生成的随机数的顺序是1 3 5 3 6,将会以如下顺序得到随机序列:
1
3 1
5 3 1
5 3 9 1
6 5 3 9 1
下面来证明一下它的正确性:
对于任意一个m个元素的序列,我们都可以逆推出生成这个序列的随机数序列,且这个随机数序列是唯一的
比如n = 10, m = 5,最后生成的序列是7 2 9 1 5,那么我们就可以逆推出生成它的随机数序列是5 1 2 2 7
反过来,对于任意一个有m个随机数的序列,都可以推出一个m个元素的序列,且这个序列是唯一的
那么任意一个随机序列生成的概率就是1 / A(m, n)
由此,我们又可以证明前一个生成m元组算法是正确的:
因为对于每一阶段i,这两个算法所能得到的元素是一样的,都是[1, i],设k = i - (n - m),则任意k元组所对应的序列有k!个,这k!个序列是等概率生成的,等于1 / A(k, n),那么k元组生成概率就是k! / A(k, n) = 1 / C(k, n)。
递推到m元组也同样成立。
不过,到此我们的任务还没有全部完成,因为如果要使得最后一个算法能高效的完成,一 个合理的数据结构是必不可少的。
它要能保证高效地查找与插入,同时要能保持元素间的拓扑结构,我一开始想用笛卡尔树来维护S,用平衡二叉树的性质 保证元素的前后关系,heap的性质来建立数值的关系,但对于“insert i in S after x”的操作并不能保证在logm的复杂度内完成。
当我看到书后的解答后,不由地赞叹数据结构的奇妙,那个我在数据结构课上学后就再也没用到过的结 构派上了用场:线索二叉树
仔细一想,线索二叉树不就是综合了链表和二叉树两者的优点,即保证了元素间的拓扑关系,用可以高效地进行查询,实在太妙了。
当然,关于随机数生成的算法讨论还有很多,据说计算机程序设计艺术里就有,有空的时候再研究研究。
初识《编程珠玑II》
《编程珠玑II》热门书评
-
高级入门书
4有用 1无用 fcicq 2012-03-13
在(原书)出版后很长的时间中, 算法本身也随着很多行业领域的发展有了很大的变化.举例来说, 游戏行业为了更快的渲染, 找出了求欧式距离的高速近似算法. 很多其它问题也有了现代且更加高速的解法(但适用条件可能有所不同).基于这一点, 希望看到这个评论的同学注意一下, 比较现代相对于当时有什么方面已经发...
-
纠正一个错误
4有用 0无用 江边一鹤 2009-09-23
中文版,24页中二分搜索的awk程序,$1 == "print" {for i =1;i <= n;i++}print i ":t" x[i]}应该改为$1 == "print" {for (i =1;i <= n;i++)pr...
-
行文风格有待商榷
3有用 0无用 njuxukai 2009-03-25
书今天到手了,不知道是翻译的缘故 还是自己水平不够。 觉得问题的描述和分析都很生硬,看不太懂,往往要看上几遍才明白句子的准确意思。阅读的趣味性一般,不过关键看内容了。原本是在互动上看到有人评论翻译到达了信达雅,没这个感觉,以后还是要信任影印版。...
-
建议读完第一本再读续
2有用 0无用 wuyve 2013-06-21
作为上一本的续作,一些内容看似是重复的:性能监测、二分搜索排错、“另辟蹊径”的解决方法、代码调优、估算、取样和随机选择。这其中大部分不是“复制——粘贴”式的重复,而是深化或视角的变换。 &nbs...
-
没有第一本来的好
2有用 0无用 mark 2011-03-20
编程珠玑 II 没有再版,我觉得原因之一是它没有第一本写的好,内容充实本书有不少内容与第一部分重复,比如粗略估算,最后一部分的算法内容也基本上没有突出的东西,随机取样第一本里已提到,这里介绍了一个 Floyd 算法,最后的 find 第 K 个大的数,是上一本中的快排的变形,此外介绍了一下数值分析中...
书名: 编程珠玑II
作者: [美] Jon Bentley
出版社: 人民邮电出版社
译者: 钱丽艳 | 刘田
出版年: 2008 年10月
页数: 186
定价: 39.00元
装帧: 平装
丛书: 图灵程序设计丛书
ISBN: 9787115176066