网上流行几条面试题, 都和经典的采样洗牌问题有关, 网上每过一段时间都有哥们拿出来问一下. 正好最近在翻的 TAoCP Vol 2 上有详细专门的讲解, 因此在此一并介绍.

这几道面试题是:

1.  Given a random number generator which can generate the number in range (1,5) uniformly. How can you use it to build a random number generator which can generate the number in range (1,7) uniformly?

(http://discuss.joelonsoftware.com/default.asp?interview.11.489564.8)

1. Generate a random permutation for a deck of cards.

2. Given a long log file (not sure how long), pick 1000 items evenly from them. (Google Interview)

其中, 第一条是随机数的生成问题. 第二条是生成一个序列的随机排列的问题, 第三条等价于生成一个序列的随机组合的问题. 实质上洗牌问题就是从集合中选取随机排列, 而采样问题就是从集合中选取随机组合.

第一条的解法要用到拒绝采样定理. 简单的说, 把 1-5 的随机数发生器用两次, 拼成一个5进制的数, 就是1-25. 将这 1-25 平均分配的25种情况映射到7种情况上, 问题就解决了. 因为21是7的倍数, 我们可以每三个映射到一个, 即1-3 映射到1, …, 19-21 映射到7. 可见, 这些情况之间的概率是一样的. 那么, 要是拼成的数字正好是 22-25 这四个呢? 有两种方法, 第一种是丢弃这个数字, 从头再来, 直到拼成的数字在1-21之间. 因为这个是个概率算法, 不能保证每次都能落在1-21, 所以采样的密度不高. 还有一种方法, 是说, 假如落到了 22-25, 那这次的采样结果就用上次的. 可以证明, 这看上去两个互相矛盾的算法, 结果都能均等的得到等概率的分布. (前者叫做 Reject Sampling, 后者叫做 Metropolis Algorithm, 都是数学物理模拟里面常用的方法)

第二条的解法很简单, 从后往前第k步的时候, 每次取一个1-52k (假如牌有52张) [感谢读者评论指出这个错误 不是1-52, 而是1-k] 的随机数 j, 交换 k 和 j. 这样, 每一位都是等概率的被交换, 最后的排列也是等概率的得到.

这个方法有一个趣闻. 我们知道, 计算机里的随机数发生器是伪随机数发生器. 伪随机数发生器的原理是用线性同余实现的, 即本次的随机数 乘以一个常数, 加上另一个常数, 再对一个大数c求同余. 我们可以把从一个随机数到下一个随机数的映射看成一个函数, 这个函数是必然形成循环的 (您把这个操作和集合整体当成循环群理解也是对的, 因为好的伪随机数发生器都设计得使得所有的数是各态遍历的). 这个循环的周期, 最长就是就是c. 所以, 如果您用伪随机数发生器来生成以上的排列的话, 只会得到最多 c 种不同的交换方案. 假设我们使用 32 位机器, 那么最大的可以用在做同余的c 就是 \(2^{32}\). 可是 13! 就已经是这个数量级了, 更不要说是 52 的阶乘. 这就意味着, 用计算机里的随机数发生器, 只能生成总体可能排列中极其有限的一部分. 所以, 假如您在电脑上玩扑克牌, 而扑克牌的洗牌算法又正好是上面我们说的那种的话, 您可能一辈子也抓不到某种组合. 这个不是概率很小的问题, 而是完全不可能. (此例来自 TAoCP, Vol 2)

第三条也不难, 虽然听上去吓人. 本质上只需要知道在已经处理了前 t (\(t \ge 1000\))个的情况下, 第 t +1 个被选中的概率. 实际上就是 1000/(t+1). 因此, 用这个概率去替换已经选中的1000个当中的某个. 可以证明, 任何时间停下来, 算法都是等概率的挑出了前面 t 个里面的1000 个. 这种任何时间能停下来还能获得正确结果的算法, 叫做 Anytime Algorithm, 在计算机科学领域随处可见, 尤其是 AI Search 方面.

第三条的算法在 TAoCP 第二卷里面交代得更加全面, 因为考虑了这 1000 个记录在内存里面放不下的情况. 这时候, 一个叫做 reservoir 的缓存被引入. 每次仅仅把选中的记录加入 reservoir, 而只保留记录在其中的序号. 在序号的数据结构上作替换, 最后, 按照最终留下来的那些序号, 再走一遍 reservoir, 就得到了要选的记录. 这个采样的方法在分析不定长网络日志的时候比较有用, 所以也是 Google 亲睐的面试题.

采样和洗牌的更多内容, 请参考 TAoCP Vol 2. 3.4.2.

老霍 告诉我, 银杏泰克拿了一个”2008年中国互联网最具潜力项目奖“.

老霍, tiny, yusheng, 还有戴总, 叶总, 张总, 陈MM 以及几个我至今也记不全名字的业务部门的大哥, 恭喜你们.

第一眼看到这个美剧的时候, 还以为是胡编乱造的民科, 像 CSI 和 Gray 一样不靠谱瞎编. 看了开头几集之后发现: 数学细节几乎没有错的. 加上好莱坞原有的犯罪片编剧的水平, 这可比其他美剧好看多了. （而且还有这么 l33t 的名字 :)

以开头的几集为例. 第一季第一集是一个真实的数学建模. 数据, 假设各方面要素都全了. 第二集是有点扯淡的测不准(只会影响微观测量), 但是顺便看到扫雷问题是 NP 完全的时候我还是会心一笑. (顺带八卦一下, Knuth 大爷说了, NP 和 P 的问题, 会在 2048 \(2^11\) 年或者 4096 \(2^12\) 年被解决 :) 这哥们黑板上写了 CLIQUE 和 3SAT, 不知道大家注意到没有, 呵呵.

第三集的 Patient Zero 理论还是很靠谱的, SIR 模型列在黑板上的常微分方程也是看得我心痒痒的真想当场列一个 logistic 方程(SARS刚过去的那年我参加数学建模竞赛用的数学模型就是 SIR). 就是生物信息那边是极其不靠谱的. 病毒DNA测序之后哪有能拿DNA的N级结构直接 diff 一下就能比较出病毒不同的, 那还要基因挖掘和生物信息学干啥. 不过把数学家英明神武的塑造成一个生物信息学家还算可以接受. 第四集其实没啥技术含量, 说白了也可以说非线性方程的特性不能仅从坐标维度上的信息刻画. 比如 z = xy 在 (0, 0) 点的形态是非线性的, 但是沿两个坐标轴导数都是0 (八卦一下, 我去年很长一段时间的研究就是从子空间的性态去刻画非线性函数在全空间的性态, 显然需要很多的假设才能刻画准确). 第五集有点小民科, 因为黎曼猜想的证明方法可能是代数数论或者代数几何, 不见得就能“分解任意质数”. 况且, 要是有了任意分解质数的, 就 NP=P 了, Chariles 就可以直接回家享福了 (我可能是错的, 因为分解质数好像不是 NPC). Anyway, 分解质数必然会给 NP=P 问题更多的洞见.

下面的我还没时间看. 就转了一圈. wikipedia 有专门的每集用到的数学的列表.  还有无数的博客在分析这个剧集, 或者做科普. 可贵的是, 来自科研一线的数学家在帮助设计规划这个剧集. 据说当初一开始就是 Caltech 的数学家和研究生设计的脚本, 连黑板上的公式都是他们写的. 现在 Wolfram 接手了. Wolfram Research 据说还专门派了一个小组到哥伦比亚广播公司作剧集的数学顾问. 象牙塔里面的数学系也没闲着, 西东北大学有专门的关于剧集的博客. 康乃尔大学也有关于此的数学博客. 连 TI 都有面向教育的教案.

其实这也不是个案了. 我几个月前买了一本书, 叫做 “The Physics of Superheroes” (超人背后的物理学) 文风优美, 讲解深刻, 而且写作的教授可不是民科, 而是正儿八经的明尼苏达大学的物理学教授 James Kakalios.

一线的科学家能够放下身段找些大家感兴趣的话题作科普, 这个国家的下一代怎么能不强大? 什么叫科学技术强国, 从一些小侧面就看出来了.

补: 既然说到了科普, 最近关于爱科普的文章引起的争议也很多, 补几句废话吧.

首先, 我从来就不认为方舟子的科普写的好, 或者原创性高. 不信? 读读这篇. 你要是问我方舟子一天一篇从鳄鱼到链霉素哪来这么多材料(让我一天一篇写计算机科普我都要X尽人亡啊), 我就回答了: 呵呵, 呵呵, 美国的国家地理杂志恰好很多次都比方舟子的文章早一个月两个月印刷出来送到我手里. 所以我觉得, 大家不必迷信他的科普. 他囫囵吞枣的写很多不是他的研究方向的东西, 并且脱离科研一线很多年, 写出来的东西, 看了启发是不大的. 不必迷信这个人的文章.

其次, 我也是不怎么同意连岳在地震的时候的言论的, 但是我依然敬佩他作为一个评论人的勇气和洞见. 这些洞见并不因为他没学过概率论就失去价值. 我就算知道高深的数学, 我还是没他在社会问题上深刻. 人和人是有差距的, 不要用英俊的科学脸庞去鄙视别人, 至少读这篇博的人, 我希望没有这样的不健康的心态.

英文中哲学叫做 philosophy, 中文叫做爱智慧. 智慧是个抽象的东西, 只有去爱它, 才会变得有趣. 爱科学, 或者说, 爱这个世界和社会, 科学和社会才会变得有趣. 如果一个科普工作者不爱这个世界, 哪里会有超人的物理学这样有趣的书问世呢?

和世界上大多数国际机场一样, 美国夏威夷国际机场非常大. 为了方便旅客在航站之间转运, 航站之间用巴士提供交通服务. 在夏威夷, 他们用本地人的语言把这种巴士命名为 wiki wiki, 意思是”很快”. 因为在本地人的语言里面, wiki 是”快”的意思. 

1995 年的时候, “极限编程”方法论大牛, Ward Cunningham, 觉得应该建立一个公共的网站, 让人能够输入一个 Pattern 的名字, 就能查阅到一个 Design Pattern 的用法, 而且这个网站还能被人编辑, 实现知识共享. 从此, 世界上第一个 wiki 网站就建立起来了, 他把它的东西叫做 WikiWikiWeb, 意思就是”快速查阅的网站”. 这时候 wiki 还只是在程序员之间流行, 直到 2001 年, 一个叫 Jimmy Wales 的, 创建了 Wikipedia, 从此, 才算是普及了. Wiki 和 Wikipedia 彻底改变了我们的生活. 试想, 人类协作创造了一本共享智慧的, 随时可访问(中国大陆和朝鲜除外)的百科全书, 是多么值得荣耀的伟大成就! 

且慢, 以前人类难道没有百科全书么? 有, 几乎每个像样的图书馆都有大英百科全书, 为什么这些百科全书没有如此大的改变我们的信息获取方式呢? 沿着同样的逻辑链条, 我们可以问更多的问题: 在没有 Google 之前, 似乎搜索引擎也有, 但这个东西我们很少用, 也很少听说, 为什么就是 Google 一出现, 就彻底改变了我们的检索方式呢? 

问题的答案很多, 我说我的答案: 很多事情, 只有在人能很快的完成的时候, 才有了做的可能. 这句话可能比较拗口, 反过来说可能更加好懂: 如果用某种方法做一件事情太耗时间了, 那么人就不可能用这个方法做事情. 只有一个方法能够让人足够快的做好事情的时候, 这个方法才会变得实用, 同时这个事情才有做的可能性. 

为避免过于抽象, 我们仍然用例子说明. 美国宪法规定要10年做一次人口普查, 但是直到 1890 年, 美国才进行了历史上第一次完整的全国人口普查. 传统上, 人口普查的数据提取上来, 要花多于10年的时间才能处理完, 因此, 人口普查从来就做不完. 直到1890年左右, IBM 公司发明打孔卡片, 卖给了美国人口统计局, 美国人口统计局采用了打孔卡片作为报表, 从此才能在2年内做完一次人口普查统计. 打孔卡片比人填表统计快多少呢, 也就快5倍而已. 但是就这个5倍, 把原本不可能做到的全国人口普查变成了可能. 

天气预报也是很好的例子. 天气预报的原理是解一个数值偏微分方程, 这个道理科学家在1922年就知道了. 但在计算机没出现前, 是没有天气预报员这个职业的. 直到1955年, 在电子计算机的帮助下, 天气预报才变成了现实. 那么, 1955 年的电子比1922年的机械式计算机快了多少倍呢? 也就1000倍. 另外有一个未经证实传说说, 以前预报24小时内的天气预报需要计算机计算25小时, 直到更快的计算机出现, 才使得2小时之内可以算出24小时的天气预报, 使得天气预报实用化. 这个, 也就是10倍的更新. 

快工具和慢工具的差别, 带来了一件事情可做与不可做的差别. 其实不光是表面上速度的改变, 对应内里是整个方法体系的本质改变才是关键. 比如, 在 UNIX 下数一个文档有几个a开头的词是很简单的事情, 只需要知道正则表达式和管道就行了. 在没有正则表达式和管道的环境里, 这个事情就比较难 (或者有更加好的方法我不知道?). 当然, 这事也可以做, 只是慢了10倍而已. 同理, 从纽约到华盛顿步行也能到, 就是慢了一点而已. 而汽车让从纽约到华盛顿变成了一件很平常的事情, 其实小汽车也就比步行快了不到20倍而已. 到图书馆查百科全书也是一种获取资料方式, 在网上 Google 也是一种方式, 后者(一分钟)比起前者(一小时), 也就快了10倍到100倍而已. 可不同的仅仅是速度么? 正则表达式提供了新的描述角度; 汽车是一种新的不耗费体力的快速交通工具; Google 是一种新的获取信息的手段, 这些速度的表面差异, 对应的内里, 是本质差异. 虽然改变的是速度, 却不仅仅是速度. 甚至, 我们可以大胆的断定, 如果没有本质的内里的变化, 速度也不可能有10倍的提升. 

我们都知道, 做事情要高效, 要 WikiWiki. WikiWiki,  是每一个想要管理好时间的人的圣杯, 是每一个想多做点事情的人的魔咒; 可是很显然, 平凡的工具, 至多越用越熟; 即使用到烂熟, 也不能带来本质的效率提升的; 一成不变的思想, 最多用到极致, 形成一个自我体系, 但跳出体系外, 是不能带来崭新的角度和本质的提升的. 特别的, 是在计算机科学以及计算机编程领域, 快工具和新思想层出不穷. 依我的观察, 在计算机科学的发展史中, 每一个时代都有很多新思想涌现, 带来的是革命性的思维方法和崭新的理论实践, 以及快好几个数量级的效率提升; 在在编程方面, 我们大多数人也见识了 UNIX 管道哲学, 和函数式编程的哲学对效率的提升.  这些新思想, 好工具, 是我们计算机科学领域最好的珠玑, 也是在大海边玩耍的孩子不可错过的晶亮的贝壳. 

那么, 心急的读者要问了, 到底哪些是晶亮的贝壳和藏着的珠玑呢? 别急, 我会把我见到的认为是晶亮的贝壳和珠玑的好东西记录在这里, 所以, 请继续关注我这个系列的后续文章 :) 

最后附送几个不算八卦的八卦, 算是本文花絮: 

1. 本文中间那句拗口的中文是翻译自 Software Tools 中的一句: < Many jobs will not get done at all unless they can be done quickly.> 里面还有 “We consider people cost a great deal more than machines, and the disparity will increase in the future” 以及 “The extra freedom permitted by got’s is just what you don’t want” 等道理深刻的话语.  有时候我真的怀疑, Software Tools 是一本讲哲学的书, 而不是一本编程书. 

2. Wiki 最早的思想来自于苹果机上的 hypertalk. 这个软件相当于是个人多媒体 Wikipedia. 苹果的 Applescript 自然语言编程的语法, 也是借鉴的这个软件的语言, 叫做 hypertalk. 这个软件称得上是个人计算机的 killer app, 但是不幸被苹果收购之后就中断开发了.  Steve Jobs 这家伙很没文化, 收购并扼杀了很多苹果上的经典软件, 这些故事等以后有空细说. 

3. 关于汽车之比人快10倍, 但是本质上改变了人的生活的例子是借用的 Knuth 的, 具体可见 <Mathematics and Computer Science: Coping with Finiteness>, 文章发在 1976 年的 Science. 这是一篇好文章!

4. Ward Cunningham 的网站, http://c2.com/cgi/wiki 是历史上最早的 wiki 百科, 只是全是关于计算机和编程的而已.