一点琐碎感想

zxchaos
2018-04-06 21:35:19

这是工作七年来读完的第一本大部头. 这本书是2014年买的, 买完后一直没下决心去读, 放了两年多才开始读.

为什么要读这本书呢? 首先我是Java程序员, 而这本书中的算法就是用Java语言描述的. 其次, 我认为算法是每一个coder都绕不过去的基础, 不管用什么语言, 算法都是以后能力提升的瓶颈. 大学时学数据结构和算法这门课就是为了通过考试, 学完就都忘了. 工作以后很少有机会自己去实现算法, 都是调用已有的库, 因此导致算法这一块很薄弱, 每当看技术书或者是面试问到算法时心里都很虚.

我对自己技术成长路线规划是: 算法->技术->架构. 算法是重中之重. 之前在读具体技术书籍的时候总感觉我的知识体系里面缺了一块儿, 而这一块儿就是算法.

读这本书用了一年多的时间. 开始读这本书没有给自己规定多久要看完, 只是想仔仔细细的读, 所以每一节我都会读3-4遍, 但读到后面的时候发现前面很多也都忘掉了. 这本书一定不能像我这样拖得时间太长, 4-6个月读完一遍比较好. 一定要耐心去读这本书.

读这本书的过程中发现带着目的去读一本书是一种很好的读书方法. 对于算法这本书, 我读这本书的目的:

...
显示全文

这是工作七年来读完的第一本大部头. 这本书是2014年买的, 买完后一直没下决心去读, 放了两年多才开始读.

为什么要读这本书呢? 首先我是Java程序员, 而这本书中的算法就是用Java语言描述的. 其次, 我认为算法是每一个coder都绕不过去的基础, 不管用什么语言, 算法都是以后能力提升的瓶颈. 大学时学数据结构和算法这门课就是为了通过考试, 学完就都忘了. 工作以后很少有机会自己去实现算法, 都是调用已有的库, 因此导致算法这一块很薄弱, 每当看技术书或者是面试问到算法时心里都很虚.

我对自己技术成长路线规划是: 算法->技术->架构. 算法是重中之重. 之前在读具体技术书籍的时候总感觉我的知识体系里面缺了一块儿, 而这一块儿就是算法.

读这本书用了一年多的时间. 开始读这本书没有给自己规定多久要看完, 只是想仔仔细细的读, 所以每一节我都会读3-4遍, 但读到后面的时候发现前面很多也都忘掉了. 这本书一定不能像我这样拖得时间太长, 4-6个月读完一遍比较好. 一定要耐心去读这本书.

读这本书的过程中发现带着目的去读一本书是一种很好的读书方法. 对于算法这本书, 我读这本书的目的: 不查阅手册就能够写出基本算法的实现. 所谓基本算法就是这本书中出现的算法. 对于书中的算法分析看不懂的话直接跳过, 只看结论, 留着以后再看. 记住算法实现就够了.

这本书不能只是看懂就好, 里面的算法一定要自己敲一遍才行.

第一章的1.2 数据抽象和1.4 算法分析一定要仔细读, 是全书的基础. 第二章到第五章要仔细看, 涉及到的算法一定要敲一遍. 第六章过一遍就好, 看不懂也不用太纠结. 第四章图论是个相对独立的一章和前后关联不是很强, 只有在第五章正则表达式的NFA的构造会用到有向图中的知识, 里面涉及到的算法不是很难理解, 但就是忘得比较快, 需要经常回顾.

对于我来说这本书里面最难理解的是KMP算法中的DFA数组的构造, 豆瓣的里面LastK的回答对我的帮助很大: https://book.douban.com/subject/19952400/discussion/59623403/

这本书的翻译质量一般. 阅读时需要查看出版社已经确认的勘误: http://www.ituring.com.cn/book/875 . 小tip: 如果嫌不方便, 可以写个简单的爬虫.

下载原版的pdf来作对比阅读也是个不错的方式.

这本书的在线网站提供的ppt也是理解一些知识点的很好的参考: https://algs4.cs.princeton.edu/lectures/

吐个槽. 有一点我一直不能理解, 为什么不能像原版一样把这本书印成彩色的? 这本书本来定价就是99块钱不算便宜, 如果是彩印的话很多人也不会介意再多花几十块, 这样阅读体验会提升很多, 不用总往前面的彩图翻了.

三月初读完的这本书, 又花了大概一个月时间复习了一遍所有算法. 写了这些并不意味着这本书以后就束之高阁了. 每过一段时间就还要把这本书的基础算法拿出来再刷一遍.

现在想想这本书的阅读并不是一个快乐的过程, 因为都是零碎的时间去读的再加上很多知识需要去补, 阅读速度很慢, 有时候两节之间要隔上好几个星期, 有过一次想要放弃, 但最后我想通了: 再厚的书也是有厚度的, 不管以什么阅读速度去读, 总有一天你都能读完它!

在阅读这本书的过程中对自己思考能力以及coding能力也是一个训练, 我会把读书中的碰到的很多好的经验用到实际工作中.

读完这本书并理解掌握了基础算法之后再去看那些讲技术或者架构方面的书根本就不叫事儿了, 原因是理解难度会比算法书小很多, 阅读效率会提高, 有了扎实的算法基础心里也有底气了.

以下是我总结的读完这本书需要掌握的基本算法:

## 最基本算法
二分查找. P28, P241的基于有序数组的二分查找.
队列的链表实现. 算法 1.3 P95
栈的链表实现. 算法 1.2 P94; 栈的数组实现(动态调整数组). 算法 1.1 P88
背包的链表实现. 算法 1.4 P98
## 排序相关算法
插入排序. 算法 2.2 P157 部分有序和小规模数组有效
希尔排序. 算法 2.3 P163
自顶向下归并排序. 算法 2.4 P171 算法框架, 主要是P170 merge 方法的实现
快速排序. 算法 2.5 P182 算法框架, 着重看P184切分(partition)算法.
三向切分快速排序. P189
基于堆的优先队列. 算法 2.6 P202 需要看P200 swim方法和P201的sink方法的实现.
索引优先队列. API P203, 具体实现需要看github源码
堆排序. 算法 2.7 P206
## 符号表相关算法
基于二叉查找树的符号表. 算法 3.3 P252 算法框架. 主要看 P252算法3.3(续1)中的get和put方法实现; P261算法3.3(续4)deleteMin和delete方法实现
红黑树插入算法, P281; 还需要看红黑树的右旋和左旋算法, P277; 颜色转换, P279; 删除最小键和删除算法需要看书对应的代码实现.
字符串的hash算法, P294; Horner算法, P506
链表法散列表, 算法 3.5 P297
线性探测符号表, 算法 3.6; 还需要看P302 delete方法实现; P304 resize方法实现.
## 图相关算法
无向图数据类型实现, P336
深度优先搜索, P339; 解决问题: 两个顶点连通性问题.
使用 深度优先 搜索查找无向图中的路径, 算法 4.1, P343; 解决问题: 单点路径问题.
使用 广度优先 搜索查找无向图中的路径, 算法 4.2, P346; 解决问题: 单点最短路径问题.
使用 深度优先 搜索找出无向图中的所有连通分量, 算法 4.3, P349
union-find(加权quick-union)算法. 算法 1.5续 P145
无环图的判断以及二分图的判断, P352
有向图数据类型的实现, P366
有向图的可达性(DFS), P367
寻找有向环. P372
拓扑排序(逆后序). P375
Kosaraju算法(强连通分量), 算法4.6 P380, 用到了union-find算法.
加权无向图 和 加权无向边 的数据结构, P395
Prim算法即时实现(MST), 算法4.7 P403
Kruskal算法(MST), 算法4.8 P406
边松弛relax方法实现, P418; 顶点松弛, P419
Dijkstra算法(最短路径), 算法 4.9 P423
无环加权有向图的最短路径算法(拓扑排序), 算法 4.10 P427
Bellman-Ford算法, 算法4.11 P438
## 字符串相关算法
键索引计数法(步骤要搞清楚), P458
低有效位排序(LSD), 算法 5.1 P459
高位优先字符串排序(MSD), 算法 5.2 P462
三向字符串快速排序, 算法 5.3 P469
基于单词查找树的符号表(R向Trie树), 算法 5.4 P479
三向单词查找树. 算法 5.5 P486
最长键(longestPrefixOf), P481; delete操作, P482
KMP算法. 算法 5.6 P500; DFA数组构造, P499
正则表达式模式匹配(NFA理解). 算法 5.9 P524
Huffman压缩算法. 算法 5.10 P547
LZW压缩算法. 算法5.11 P552; LZW展开算法. 算法 5.11(续) P554

1
0

查看更多豆瓣高分好书

回应(7)

查看更多回应(7)

算法(第4版)的更多书评

推荐算法(第4版)的豆列

了解更多图书信息

豆瓣
免费下载 iOS / Android 版客户端