编程珠玑II

Jonas 2011-01-10 0

读过一部分。对笔试还是很有帮助的。

whitefish 2012-06-16 0

读读挺有启发，而且很有趣

Goooooouwa 2011-12-15 0

独一无二的经典计算机著作，不讲工程素养，而是编程的实践技能。

amazingnan 2012-04-07 0

自己水平有限，看得有点不知所云

SunTiejiang 2012-06-25 0

真的不错，相比一些个算法教材，编程珠玑更注重于提升代码能力。

senninha 2012-06-10 0

温故而知新好书就应该多读几遍

312day 2013-01-29 0

任何代码都有改进的余地，嗯。

ensoleilly 2016-03-26 0

很好但是没有1好～还是强烈推荐。

今天不热 2012-01-24 0

第一次知道这个书是看到zizipo在读。真的是好书，读了好几遍，依然有重读的欲望

skeeey 2015-08-12 0

不错的算法书，一些思想还是很重要的

Jonas 2011-01-10 0

读过一部分。对笔试还是很有帮助的。

whitefish 2012-06-16 0

读读挺有启发，而且很有趣

Goooooouwa 2011-12-15 0

独一无二的经典计算机著作，不讲工程素养，而是编程的实践技能。

amazingnan 2012-04-07 0

自己水平有限，看得有点不知所云

SunTiejiang 2012-06-25 0

真的不错，相比一些个算法教材，编程珠玑更注重于提升代码能力。

senninha 2012-06-10 0

温故而知新好书就应该多读几遍

312day 2013-01-29 0

任何代码都有改进的余地，嗯。

ensoleilly 2016-03-26 0

很好但是没有1好～还是强烈推荐。

今天不热 2012-01-24 0

第一次知道这个书是看到zizipo在读。真的是好书，读了好几遍，依然有重读的欲望

skeeey 2015-08-12 0

不错的算法书，一些思想还是很重要的

我想说两句

这本书和大名鼎鼎的《编程珠玑II》是同一本书

王飞 2010-03-21 1赞

这本书和大名鼎鼎的《编程珠玑II》是同一本书, 只是前者是英文的，后者为中文的。前几天看到朋友仔看这本书，正准备去买的，后来在看《编程珠玑》的时候才发现自己已经有了这本书了。

连锁书

Vmiyu 2013-02-11 0赞

耻。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。

写程序就是精雕细琢

fkpwolf 2011-09-01 0赞

1. 里面有章《文档设计》，谈到如何设计表格，选择字体，还有文字的排版。我记得侯捷有出过一本关于排版的书，当然不以为然，觉得搞技术的人去弄这些雕虫小技，有点赚稿费之嫌。现在我才发现，文档也是用户体验的一部分，简洁明了对与交流是必不可少的，而要做到这点却不那么简单。

没人吐槽这渣翻译么？

学徒 2012-04-09 0赞

书是好书，内容是好内容，只是看着翻译翻的东西会吐血啊。
我真的很怀疑翻译者自己是不是能很清楚地明白自己到底在翻什么？

书是好书，内容是好内容，只是看着翻译翻的东西会吐血啊。
我真的很怀疑翻译者自己是不是能很清楚地明白自己到底在翻什么？

初识《编程珠玑II》

angus 2014-07-03 0赞

原文写于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的复杂度内完成。

当我看到书后的解答后，不由地赞叹数据结构的奇妙，那个我在数据结构课上学后就再也没用到过的结构派上了用场：线索二叉树
仔细一想，线索二叉树不就是综合了链表和二叉树两者的优点，即保证了元素间的拓扑关系，用可以高效地进行查询，实在太妙了。

当然，关于随机数生成的算法讨论还有很多，据说计算机程序设计艺术里就有，有空的时候再研究研究。

能让你灵机一动的好书

宏儿 2010-10-31 1赞

这本书对得起《编程珠玑》这个书名。相比计算机书籍习惯性的几百页这个厚度，这本书很薄。但应了那句话，浓缩就是精华呀。书中对算法的每个大的领域方向都有灵机一动的实用方法，让你会不禁感叹，原来还可以这样的！

建议读完第一本再读续

wuyve 2013-06-21 2赞

        作为上一本的续作，一些内容看似是重复的：性能监测、二分搜索排错、“另辟蹊径”的解决方法、代码调优、估算、取样和随机选择。这其中大部分不是“复制——粘贴”式的重复，而是深化或视角的变换。
        除此以外，本书介绍了上一本没有涉及的方面：小语言、轻量级文档、图表制作等。这些阅读时比算法要轻松得多。
        不像上一本经过了再版的修订从而添加了些C++代码，《续》的代码基本是Awk和C语言，前者虽然和C很接近，仍是个阅读障碍。如果读者并未对Awk一种编程语言有所了解，同时阅读这两种代码确实困难不小。出于同样的原因，《续》和的年代要比原作的第2版更古老，尽管经典不那么容易过时，也是不小的美中不足。比如，你会在习题中看到为了考虑磁带特性而特别设计的算法，这在现在看来就不是那么有实用价值了。
        因此我强烈建议，先读完原作，再来读这本《续》，在具备了一定基础之后，深化理解，提高阅读效率，轻松愉快。如果先读《续》，效果和效率可能要大打折扣了。

没有第一本来的好

mark 2011-03-20 2赞

编程珠玑 II 没有再版，我觉得原因之一是它没有第一本写的好，内容充实

本书有不少内容与第一部分重复，比如粗略估算，最后一部分的算法内容也基本上没有突出的东西，随机取样第一本里已提到，这里介绍了一个 Floyd 算法，最后的 find 第 K 个大的数，是上一本中的快排的变形，此外介绍了一下数值分析中的牛顿迭代法等

书中第三部分介绍了 I/O，不是计算机的 I/O，而是人性化 I/O，数据的图形化呈现，文档布局等内容。虽然与技术方面的关系不是太大，但是还是很有意义。

课后习题一扫而过没有做。

虽然没有第一本来的好，但是 Jon Bentley 大师的书仍然是五星啊

高级入门书

fcicq 2012-03-13 4赞

在(原书)出版后很长的时间中, 算法本身也随着很多行业领域的发展有了很大的变化.
举例来说, 游戏行业为了更快的渲染, 找出了求欧式距离的高速近似算法. 很多其它问题也有了现代且更加高速的解法(但适用条件可能有所不同).

基于这一点, 希望看到这个评论的同学注意一下, 比较现代相对于当时有什么方面已经发生了变化, 并仔细的考虑这些方面/因素对所述内容的影响.
不限于本书, 偶看到的很多书都需要这样对待, 这对读者是一个考验, 而非书籍或作者的问题.

但是偶对这书有一点不满, 本书迭代法开方与检测质数的算法不高效, 而这并非近年出现的内容.

纠正一个错误

江边一鹤 2009-09-23 4赞

中文版，24页中二分搜索的awk程序，
$1 == "print" {for i =1;i <= n;i++}print i ":t" x[i]}应该改为
$1 == "print" {for (i =1;i <= n;i++)print i ":t" x[i]}

高级入门书

fcicq 2012-03-13 4

在(原书)出版后很长的时间中, 算法本身也随着很多行业领域的发展有了很大的变化.
举例来说, 游戏行业为了更快的渲染, 找出了求欧式距离的高速近似算法. 很多其它问题也有了现代且更加高速的解法(但适用条件可能有所不同).

基于这一点, 希望看到这个评论的同学注意一下, 比较现代相对于当时有什么方面已经发生了变化, 并仔细的考虑这些方面/因素对所述内容的影响.
不限于本书, 偶看到的很多书都需要这样对待, 这对读者是一个考验, 而非书籍或作者的问题.

但是偶对这书有一点不满, 本书迭代法开方与检测质数的算法不高效, 而这并非近年出现的内容.

纠正一个错误

江边一鹤 2009-09-23 4

中文版，24页中二分搜索的awk程序，
$1 == "print" {for i =1;i <= n;i++}print i ":t" x[i]}应该改为
$1 == "print" {for (i =1;i <= n;i++)print i ":t" x[i]}

行文风格有待商榷

njuxukai 2009-03-25 3

书今天到手了，不知道是翻译的缘故还是自己水平不够。觉得问题的描述和分析都很生硬，看不太懂，往往要看上几遍才明白句子的准确意思。阅读的趣味性一般，不过关键看内容了。
原本是在互动上看到有人评论翻译到达了信达雅，没这个感觉，以后还是要信任影印版。

建议读完第一本再读续

wuyve 2013-06-21 2

        作为上一本的续作，一些内容看似是重复的：性能监测、二分搜索排错、“另辟蹊径”的解决方法、代码调优、估算、取样和随机选择。这其中大部分不是“复制——粘贴”式的重复，而是深化或视角的变换。
        除此以外，本书介绍了上一本没有涉及的方面：小语言、轻量级文档、图表制作等。这些阅读时比算法要轻松得多。
        不像上一本经过了再版的修订从而添加了些C++代码，《续》的代码基本是Awk和C语言，前者虽然和C很接近，仍是个阅读障碍。如果读者并未对Awk一种编程语言有所了解，同时阅读这两种代码确实困难不小。出于同样的原因，《续》和的年代要比原作的第2版更古老，尽管经典不那么容易过时，也是不小的美中不足。比如，你会在习题中看到为了考虑磁带特性而特别设计的算法，这在现在看来就不是那么有实用价值了。
        因此我强烈建议，先读完原作，再来读这本《续》，在具备了一定基础之后，深化理解，提高阅读效率，轻松愉快。如果先读《续》，效果和效率可能要大打折扣了。

没有第一本来的好

mark 2011-03-20 2

编程珠玑 II 没有再版，我觉得原因之一是它没有第一本写的好，内容充实

本书有不少内容与第一部分重复，比如粗略估算，最后一部分的算法内容也基本上没有突出的东西，随机取样第一本里已提到，这里介绍了一个 Floyd 算法，最后的 find 第 K 个大的数，是上一本中的快排的变形，此外介绍了一下数值分析中的牛顿迭代法等

书中第三部分介绍了 I/O，不是计算机的 I/O，而是人性化 I/O，数据的图形化呈现，文档布局等内容。虽然与技术方面的关系不是太大，但是还是很有意义。

课后习题一扫而过没有做。

虽然没有第一本来的好，但是 Jon Bentley 大师的书仍然是五星啊

这本书和大名鼎鼎的《编程珠玑II》是同一本书

王飞 2010-03-21 1

这本书和大名鼎鼎的《编程珠玑II》是同一本书, 只是前者是英文的，后者为中文的。前几天看到朋友仔看这本书，正准备去买的，后来在看《编程珠玑》的时候才发现自己已经有了这本书了。

能让你灵机一动的好书

宏儿 2010-10-31 1

这本书对得起《编程珠玑》这个书名。相比计算机书籍习惯性的几百页这个厚度，这本书很薄。但应了那句话，浓缩就是精华呀。书中对算法的每个大的领域方向都有灵机一动的实用方法，让你会不禁感叹，原来还可以这样的！

连锁书

Vmiyu 2013-02-11 0

耻。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。

写程序就是精雕细琢

fkpwolf 2011-09-01 0

1. 里面有章《文档设计》，谈到如何设计表格，选择字体，还有文字的排版。我记得侯捷有出过一本关于排版的书，当然不以为然，觉得搞技术的人去弄这些雕虫小技，有点赚稿费之嫌。现在我才发现，文档也是用户体验的一部分，简洁明了对与交流是必不可少的，而要做到这点却不那么简单。

没人吐槽这渣翻译么？

学徒 2012-04-09 0

书是好书，内容是好内容，只是看着翻译翻的东西会吐血啊。
我真的很怀疑翻译者自己是不是能很清楚地明白自己到底在翻什么？

书是好书，内容是好内容，只是看着翻译翻的东西会吐血啊。
我真的很怀疑翻译者自己是不是能很清楚地明白自己到底在翻什么？

我要写长评

想读在读读过

标签(多个标签以“，”分开):

保存

编程珠玑II

推荐文章

猜你喜欢

附近的人在看

推荐阅读

拓展阅读