BT

如何利用碎片时间提升技术认知与能力? 点击获取答案

阅读者(十七):编程珠玑,字字珠玑

| 作者 丁雪丰 关注 3 他的粉丝 发布于 2011年11月22日. 估计阅读时间: 5 分钟 | GMTC大前端的下一站,PWA、Web框架、Node等最新最热的大前端话题邀你一起共同探讨。

无论你自称是“程序猿”还是“攻城师”,只要在写程序,都免不了要和算法打交道。说起算法,第一本从你的记忆中检索出的图书是什么呢?是经典的大部头《算法导论》?还是之前大红大紫的《编程之美》?以前它们几乎是同时映入我脑海的,分不清谁先谁后,这两本书我都读过,前者是在学校的算法课上,而后者则是在毕业求职前。

编程珠玑(第2版) 最近,我终于有了一个明确的答案,在这些算法相关的书籍中,最让我爱不释手的是《编程珠玑》这本薄薄的小册子,因为它真正激发起了我对学习算法的热情。不愧是培养了James Gosling(Java之父)、Charles Leiserson(《算法导论》作者)等众多大师的“超级大师”的传世之作。与学校里接触的“教材式”的书不同,《编程珠玑》更像是“问答式”的,抛出一个由实际问题简化而来的问题,然后一步步进行分析解答,作者将想要传达给读者的知识与技巧贯穿其中,期间还经常让人发自内心地感叹一下,原来还能这么做。

以书中第8章为例,我把问题简单描述为“输入一个长度为n的数组x,求其中任意连续子元素相加的最大和”。最常规的思路就是写一个三层嵌套的循环,算法的执行时间为O(n3),时间似乎有点长,做点优化,充分利用之前的计算结果,可以节省一层循环,于是得出了一个O(n2)的算法。如果引入“分治”的思路,将数组拆开,分别求解,然后再合并起来,这样只需O(nlogn)的时间。别以为这样就结束了,终极方案总是出现在最后的,直接从头开始扫描数组,一次扫描得出结果(具体算法请允许我卖个关子),O(n)时间内就能解决问题,神奇吧。千万不要以为这是专门用来教授算法知识的假想的“教学问题”,这可是源自布朗大学的Ulf Grenander曾经遇到过的真实问题,可见设计一个好的算法是多么重要。

在日常工作中,估计大多数人都不太有机会遇到太复杂的算法,就算遇到了,也可以侥幸依靠强大的计算和存储能力来解决问题。诚然现在的服务器计算能力越来越强,1个内核可以抵得上从前的几个庞然大物,更何况CPU还是多核的,内存都按GB计算,但不能因为这样就认为现在算法和数据结构的重要性不如从前了。假设上文提到的问题中不是计算数组元素,而是每次循环需要操作数据库或者调用远程服务,一次操作就要耗时几毫秒,甚至是几百毫秒,那么O(n3)和O(n)的区别就显而易见了。加服务器不是唯一的解决方案,有时简单地调整算法能让你省下大把的金钱和时间。

再来说说空间的问题,节省空间似乎已经不再重要了,对某些人来说是这样,但不可否认还是存在很多场景,需要锱铢必较,仔细地设计算法和数据结构。嵌入式设备就不说了,来说说眼下流行的Redis,为了能最大限度地使用好服务器的内存空间,减少浪费,antirez在编写Redis时就煞费苦心地改良数据结构,真的是能省1字节算1字节。HDFS和BigTable面向海量存储,照理说它们都是不缺空间的主,可是其中还是提供了LZO、Snappy等众多压缩算法,用“闲置”的CPU运算时间来换取更多的空间……类似的例子还有很多,所以在编写代码时,如果条件允许,请再多考虑一下自己的实现。

多数Java程序员应该都有GC调优的经历,遇到GC过于频繁,耗时太长的情况,通常会对JVM的堆配置做调整,如果调整的效果都不明显呢?来看看代码吧,也许对代码稍作修改,优化下算法,就能把陡峭的内存增长曲线将下来了。啊哈,算法!

书中还时不时地回顾下历史,比如二分搜索,相信大多数人都知道是怎么回事,可是你知道么,第一篇二分搜索的论文1946年就发表了,可是直到1962年才有人写出了第一个完全正确的二分搜索程序,太让人惊讶了,这个可是如今算法教材上的标配啊。还有那些在编码规范中经常出现的最长不要超过80个字符,其中80的由来原来和早期的打孔卡有关(如果对这个话题感兴趣,可以阅读阮一峰的这篇文章)。

薄薄的《编程珠玑》,两百多页捧在手上完全没有板砖的压力,可以将其作为教材以外的辅助读物,工具书以外的休闲读物,亦或者是和我一样,将其作为睡前读物,每晚睡前读上几页,和算法聊上几句,和数据结构打个招呼。

评价本文

专业度
风格

您好,朋友!

您需要 注册一个InfoQ账号 或者 才能进行评论。在您完成注册后还需要进行一些设置。

获得来自InfoQ的更多体验。

告诉我们您的想法

允许的HTML标签: a,b,br,blockquote,i,li,pre,u,ul,p

当有人回复此评论时请E-mail通知我

中文翻译如何? by 王 辉

确实是一个好书,限于本人外语水平,估计是要看中文版的,但网上的反应是本书的翻译好像不是很好,你读的是原著还是中文版的呢?

一遍扫描好像不算太复杂 by 徐 平胜

一遍扫描好像不算太复杂,因为连续,记录首尾数值就可以求和。
有空试试看这个想法对不对。
楼主下次可以挑一个更难的例子:)

Re: 中文翻译如何? by Ding Xuefeng

这本书的版本比较多,我读的是图灵的《编程珠玑》(第2版),就是插图的那本,感觉翻译整体上来说还行。

多谢分享,已加入书单! by 高 翌翔

确实,书中的算法不过是特定上下文的具体实现,
重点在于,理解算法背后的解题思路,并归纳总结核心设计思想
而且须要通过不断实践加深理解,进而达到融汇贯通、为我所用之境界!

说了一大堆,都是嘴把式,先去买书,嘿嘿

这本书共有两册 by Kraft Bai

学算法要正奇相辅的,这两本书算是奇路上比较出色的。要想走得远,内功深厚也重要,CLRS必不可少。

Re: 一遍扫描好像不算太复杂 by qi wei

兄弟,你理解错了吧。连续不是指自然数连续,而是位置连续。你记录首尾数值求和干嘛用啊。

Re: 一遍扫描好像不算太复杂 by 徐 平胜

-_-!!! 偶傲慢了……
如果是计算位置连续的数值,的确蛮复杂的。
我又想了一会儿,感觉像是求最大积分值啊,应该可以通过合并正负区间去优化。
我自己做的话还是会缓存很多值,不过复杂到想不清到底要存哪些了。

好吧,看来以前借这本书的时候的确只是当了枕头,回家买一本去。
楼上同学说的思路、方法是王道。

多谢推荐了本好书 by Jin Warren

工作时间越长,越感觉到算法的重要性了,机器的性能诚然重要,但往往一个参数的改变就能节约好几台机器。

Re: 多谢推荐了本好书 by zhou yaguo

工作时间越长,越感觉到算法的重要性了,机器的性能诚然重要,但往往一个参数的改变就能节约好几台机器。
有点夸张

允许的HTML标签: a,b,br,blockquote,i,li,pre,u,ul,p

当有人回复此评论时请E-mail通知我

允许的HTML标签: a,b,br,blockquote,i,li,pre,u,ul,p

当有人回复此评论时请E-mail通知我

9 讨论

登陆InfoQ,与你最关心的话题互动。


找回密码....

Follow

关注你最喜爱的话题和作者

快速浏览网站内你所感兴趣话题的精选内容。

Like

内容自由定制

选择想要阅读的主题和喜爱的作者定制自己的新闻源。

Notifications

获取更新

设置通知机制以获取内容更新对您而言是否重要

BT