写点什么

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

  • 2011-11-21
  • 本文字数:1629 字

    阅读完需:约 5 分钟

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

最近,我终于有了一个明确的答案,在这些算法相关的书籍中,最让我爱不释手的是《编程珠玑》这本薄薄的小册子,因为它真正激发起了我对学习算法的热情。不愧是培养了 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 的由来原来和早期的打孔卡有关(如果对这个话题感兴趣,可以阅读阮一峰的这篇文章)。

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

2011-11-21 08:297506
用户头像

发布了 135 篇内容, 共 60.2 次阅读, 收获喜欢 43 次。

关注

评论

发布
暂无评论
发现更多内容

浅析 Python 中的 Collections 模块

宇宙之一粟

Python 2月月更

以太坊剖析 - 区块(Block)

起航

区块链 以太坊

以太坊剖析 - 区块头部(BlockHeader)

起航

区块链 以太坊

(2-1/26) 滑雪的准备

mtfelix

300天创作

再解 JavaScript 原型 与原型链

编程三昧

JavaScript 前端 原型 原型链 2月月更

微服务架构实践原则

俞凡

架构 微服务

WebRTC 如何在安卓系统上采集视频数据 | 社区征文

liuzhen007

音视频 新春征文 2月月更

JDK9响应式流使用详解

蜜糖的代码注释

Java Java9 2月月更 响应式流

《卡片笔记写作法》读书笔记 - 重新认知思考和写作

懒时小窝

读书感悟 读书总结

也谈一下Web3.0-01

wood

300天创作 Web3.0

微信朋友圈高性能复杂度分析

唐尤华

架构实战营

使用 React、Solidity 和 Web3.js 构建真实世界的 dApp

devpoint

dapp React Solidity Web3.0 2月月更

树概念总结

en

数据结构

MySQL架构设计

JavaEdge

2月月更

ReactNative进阶(四十五):渐变组件 react-native-linear-gradient

No Silver Bullet

React Native 2月月更

ReactNative进阶(四十七):移动端调试利器 vConsole

No Silver Bullet

ReactNative 2月月更 vconsole

ReactNative进阶(五十):IOS 系统 Crash 日志分析实战

No Silver Bullet

ios React Native 2月月更

ReactNative进阶(五十一): 常见样式梳理

No Silver Bullet

CSS ReactNative 2月月更

Spotify系统架构

俞凡

架构 大厂实践 2月月更 spotify

【拥有新时代的通信协议,引领云原生迈向更高的舞台】解密Dubbo3从微服务升华到云原生 | 社区征文

洛神灬殇

云原生 Cloud Native Dubbo3 新春征文 2月月更

ReactNative进阶(四十八):Mobile App 适配性优化实战

No Silver Bullet

适配 ReactNative 2月月更

Firefox 登录后无法同步书签

TroyLiu

firefox 工具 浏览器 数据同步 书签

精度丢失问题

编程三昧

2月月更

在线格式时间计算时间差

入门小站

工具

Java9特性-响应式流(Reactive Stream)

蜜糖的代码注释

Java 响应式 响应式编程 2月月更

聊聊API安全的重要性及治理思路

陈俊

安全 API 应用架构

原型与原型链

编程三昧

JavaScript 前端 1月月更

怎样设计一个广告系统

俞凡

架构 大厂实践 2月月更

JVM进阶(一):初识 JAVA 栈

No Silver Bullet

Java JVM 2月月更

【技术】谈ServiceMesh落地的三大难题:选型、过渡、多集群

极光一号。

云原生 servicemesh 服务网格 应用交付

Linux之killall命令

入门小站

Linux

阅读者(十七):编程珠玑,字字珠玑_Book Review_丁雪丰_InfoQ精选文章