无论你自称是“程序猿”还是“攻城师”,只要在写程序,都免不了要和算法打交道。说起算法,第一本从你的记忆中检索出的图书是什么呢?是经典的大部
头《算法导论》?还是之前大红大紫的《编程之美》?以前它们几乎是同时映入我脑海的,分不清谁先谁后,这两本书我都读过,前者是在学校的算法课上,而后者则是在毕业求职前。
最近,我终于有了一个明确的答案,在这些算法相关的书籍中,最让我爱不释手的是《编程珠玑》这本薄薄的小册子,因为它真正激发起了我对学习算法的热
情。不愧是培养了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的由来原来和早期的打孔卡有关(如果对这个话题感兴趣,可以阅读阮一峰的这篇文章
)。
薄薄的《编程珠玑》,两百多页捧在手上完全没有板砖的压力,可以将其作为教材以外的辅助读物,工具书以外的休闲读物,亦或者是和我一样,将其作为睡前读物,每晚睡前读上几页,和算法聊上几句,和数据结构打个招呼。
P.S.之前一篇文章说了要把一些自己原创发表在InfoQ上的内容放到自己的博客里,这就是第一篇
。
[首发于InfoQ中文站:http://www.infoq.com/cn/news/2011/11/programming-pearls
]
分享到:
相关推荐
编程珠玑书后源代码编程珠玑书后源代码编程珠玑书后源代码编程珠玑书后源代码编程珠玑书后源代码编程珠玑书后源代码
我觉得不错,和大家分享! 编程珠玑 编程珠玑 编程珠玑
编程珠玑编程珠玑
《编程珠玑(续)》是计算机科学方面的经典名著《编程珠玑》的姊妹篇,讲述了对于程序员有共性的知识。书中涵盖了程序员操纵程序的技术、程序员取舍的技巧、输入和输出设计以及算法示例,这些内容组成一个有机的整体,...
编程珠玑和编程珠玑续两本,上传赚点分,填充填充填充
编程珠玑续、编程珠玑续本、编程珠玑续本、编程珠玑续本
编程珠玑II(编程珠玑·续) 扫描版6.56M pdf格式
《编程珠玑》第一版是我早期职业生涯中阅读过的对我影响较大的书籍之一,在书中首次接触到的很多观点都让我长期受益。作者在这一版本中做了重要更新。新增加的很多例子让我耳目一新。 ——Steve McConnell,《代码...
编程珠玑,编程珠玑续以及源码,本书针对程序设计人员探讨了一系列的实际问题,这些问题是对现实中常见问题的归纳总结。作者虽然没有给出解决这些问题的具体代码,但始终非常富有洞察力和创造力地围绕着这些折磨...
编程珠玑是一本提升coding能力不可多得的好书,看书时,可以结合这个笔记,突出重点。
编程珠玑(第二版)答案
相信这本书不用解释吧。。成为高手必备之。字字珠玑。这个可以有
这本书是《编程珠玑》高清pdf,如有侵权请告知。
编程珠玑高清pdf版.pdf
《编程珠玑》读书笔记
编程珠玑+续
编程珠玑第二版及源代码实现(C/C++) 如果让程序员们列举他们喜欢的书籍,Jon Bentley的《编程珠玑》一定可以归于经典之列。如同精美的珍珠出自饱受沙砾折磨的牡蛎,程序员们的精彩设计也来源于曾经折磨他们的实际...
编程珠玑 很好的资料 能加强对对算法和数据结构的理解