《算法(第4版)》导读(下)

2017 年 12 月 19 日 图灵教育 算法时空
 
  第五章 字符串

对很多程序员更有用的其实是字符串的处理,一般算法书讲得少,觉得似乎不是特别高端,不如动态规划炫酷,但《算法(第4版)》着重讲解了这部分内容。

5.1 字符串排序,一开始讲的可以认为是针对多键(multiple keys)或者多个数据域的排序。对于字符串来说,低位优先(LSD)可以更快地对等长的字符串来排序,而不会去用快速排序这些普适算法,这样处理字符串更快,而字符串的取值空间有限特性很重要。而不等长的可以采用高位优先(MSD),后面进一步改进成字符串的三路快速排序,深入探讨了字符串排序。

Bentley和Sedgewick的论文Fast Algorithms for Sorting and Searching Strings可以深入研究(http://www.cs.princeton.edu/~rs/strings/paper.pdf),阐述了Multikey Quicksort的原理并分析了性能。

另外,Sedgewick的讲义Advanced Topics in Sorting(https://www.cs.princeton.edu/~rs/AlgsDS07/05AdvTopicsSorting.pdf)有关于排序的一些高级主题。

5.2 trie,也就是单词查找树。搜索框就是简单的tire,比如想输入abstract,那么依次输入a-b-s-t,先从树上走a这个分支,再走b随后走s继续走t分支,最后剩下的以abst为前缀的单词也没剩几个了,很容易找到abstract这个单词,注意这种实现需要26叉树(可用ternary search trie改进之)。trie非常有用,还有后缀树和后缀数组等内容也可以作为选学材料。

字符串的查找,所谓模式匹配,Sedgewick强调的是后面的一系列算法(当然不能绕过他老师的KMP算法),例如Boyer-Moore算法和Rabin-Karp算法,这两种更有用而且更快。KMP强烈依赖于自我的模式,要自身重复,但很多字符串不具备这些特性,而Boyer-Moore或Rabin-Karp更适合于一般的字符串查找。

讲完上述内容就开始讨论正则表达式。又一次说明了字符串这章对实际程序员更有用,一般算法教材讲的图算法还有动态规划对于普通程序员来说,要想用好其实很难,而字符串却经常能感受到。

5.5 数据压缩,这部分是非常好的算法应用场景。像CMU的"真实世界的算法"这门课程里讲了很多数据压缩的算法(还有纠错编码和线性规划),也就是实际算法可以看到很多字符串的处理,又比如Huffman编码用到了优先级队列,处理数据可以用到trie还有散列,形形色色算法的应用让你亲身体验算法之大用。其实,数据压缩不是太难,自己如果可以很快实现压缩软件会有一定成就感。我讲信息论课程的时候会让学生做一般文本文件的数据压缩,看看压缩和解压的效率与常用软件如Winzip或者7zip有什么性能差异,这样能极大地提升学习兴趣。此外,文本压缩还有一些字典系列的编码(7zip的体系),还会有更多算法与数据结构的应用,特别是散列还有滑动窗的设置,如果能实现基本的LZ77和LZ78,那么算法了解和应用又能上一个台阶。我也借鉴《算法(第4版)》的一些特点,让学生实现DNA序列的压缩,这样会有趣味性,也更有针对性。

CMU的15-853: Algorithms in the Real World这门课程(http://www.cs.cmu.edu/~guyb/realworld.html)非常值得一看,非常适合进阶学习。

 
 第六章 实境

《算法(第4版)》前五章的内容很精炼,和其他算法书都不一样,也许称之为《数据结构与算法》更合适一点,因为讲数据结构的内容较多。

第6章就是讲真实的问题,并由此引出前面的算法和指导读者应该学习什么样的内容。在真实问题的背景下把前面的内容拿出来再讲,其实效果非常好。

典型例子是离散事件仿真(DES),例如公交车的调度仿真要考虑某个线路何时发车。发车相当于一个"事件",有很多车会发车但时间不同,我们不是按照固定时间间隔(例如分钟)向前逐个处理和方针,而是处理"事件"并将其放入优先级队列,只需按照事件发生时间先后取出并处理,最早出现的事件肯定最先出队,这样能够极大提升算法仿真速度。不能按时间间隔去逐个处理,这样特别慢,比如当前时间为6:30而如果下一个事件7:10出现,那么时间点直接推进到7:10即可。

 
 语言选用

《算法》这个系列的书最开始用C语言,可能是想让他老师Knuth的书更简单容易读,另外那个年代C还是比较流行的。后来大家用C++,Sedgewick也推出了相关版本,并且也推进到Java版本。但《算法(第4版)》不标注语言版本直接用Java,也说明Java的热度,实际上没有提到什么语言也说明不想写别的语言版本了。

不过,现在用Python也很多而且也更接近于机器学习和数据处理,这个其实很合理,一门语言学好了能做很多事情,所以都去学Python。而Sedgewick紧跟时代,又出了专门讲Python的教材,我本来觉得第5版很可能就是Python版(假设有第5版)。因为前期的Python基础的书已经有了,程序设计的知识讲过了,后面直接用Python讲算法课而且还可以做机器学习,这也是MIT多年讲《算法导论》的首选语言,大势所趋嘛,而且实现起来方便。最关键的是,很多人不愿意用复杂的语言解决问题,现在的人越来越懒:-)而且重度依赖于机器,没事不用C和C++写程序。

为了求证这个Python版本的猜测,我邮件求证了Wayne,他说暂无Python版本的写作计划,其原因是用Python写的代码远远慢于Python自身提供的库函数,这样起不到展示算法和数据结构效率的目的。

 
 排版

实际上排版是《算法(第4版)》的一大特色,第3版用LaTeX排版,而第4版居然用InDesign排版,但是双色印刷相当精美细致。主要是公式很少,所以用了InDesign。

我邮件咨询过Wayne,这么复杂的图能用LaTeX排出来么?他的回复让我很诧异,居然是用InDesign排版,另外这些精美的插图矢量图是拿AI画的,所以融合起来用Adobe一家的产品更好,保持一致。实际上从成书效果来看,排版确实美轮美奂,非常满意。

当然也是因为《算法(第4版)》的公式少,实际上这本书基本不讲公式,能不用就不用,这点节约了大家的脑力。因为数学确实会给很多人带来困扰,实际上数学让人会有特别深的恐惧感。算法再加数学更让人害怕了,所以《算法(第4版)》用到了算法运行实况(到底如何运行,一步步告诉大家)和可视化的方法。

《算法(第4版)》和前3版有将近40年的传承,而第二作者Wayne为这一版本付出了相当大的心血,这点很难得(绝大多数高校教师因为要做科研所以做不到这点,而且也没有这么多精力来精心编撰教材),而Wayne投入了很多精力放在这本书上。不过,从绘图和排版软件的选择上来说,还是比较符合这本书的目的,主要能更好服务于普通读者,一看就不是特别难,而且又是彩色印刷,所以很能吸引眼球。

 
  Q&A

1. 先修课程是什么?有一点离散数学知识就可以了,《算法导论》后面的附录基本也就够了,可以放心学《算法(第4版)》。

2. 要学什么数学?学别的算法书,离散数学是要学的,高等数学也是要学的,概率论也是不能丢的,线性代数也得非常好才行,矩阵如果不会好多东西用不成。但《算法(第4版)》里基本没有什么矩阵,哈哈。当然,多学一点离散数学更好,但是要看个人能力而定。既然不能学复杂的内容,那就吸收点有用的东西让程序提升吧,一定要养成很好的品味,有好坏的算法之分,这点很重要。

3. 多久能看完?不要指望很快看完。

4. 应该买中文版还是英文版?英文教材和课程其实学起来还是有点难度,所以大家根据自己需要和能力范围选择购买中文版或英文版。

5. 写程序的态度应该如何?尽量少写低效的算法,甚至于低效的程序,要尽量提高程序的性能。

《算法(第4版)》,帮助你在平常而又不平凡的程序设计里找到更多乐趣!

如果你想和谢老师一起学习算法,那么你可以扫码加入谢老师的知识星球哦~ (图灵友情推荐需付费168,大家按需选择哦)

福利时间

本期为大家送出3本《算法(第4版)》,小伙伴们说说自己在平时的工作中都会用到算法的哪些知识。或者说说你在学习算法时遇到哪些困难都是怎么解决的。欢迎大家畅所欲言。

本期小鹿和大家玩一个新玩法。精选留言我们会选出2位读者获得赠书,在文章一条、二条、三条下留言都可以参与哦~ 剩下的1本,我们用微信小程序来抽出。

请大家扫描识别下图中的二维码,点击参与就能在小程序上参加抽奖啦!注:完成抽奖后会自动发送通知,获奖的小伙伴别忘了填写地址哟~ 留言和小程序同时开奖,截止日期2017年12月21日,10:00。


点击【阅读原文】购买《算法(第4版)》

登录查看更多
7

相关内容

排序是计算机内经常进行的一种操作,其目的是将一组“无序”的记录序列调整为“有序”的记录序列。分内部排序和外部排序。若整个排序过程不需要访问外存便能完成,则称此类排序问题为内部排序。反之,若参加排序的记录数量很大,整个序列的排序过程不可能在内存中完成,则称此类排序问题为外部排序。内部排序的过程是一个逐步扩大记录的有序序列长度的过程。
【干货书】机器学习Python实战教程,366页pdf
专知会员服务
329+阅读 · 2020年3月17日
【反馈循环自编码器】FEEDBACK RECURRENT AUTOENCODER
专知会员服务
22+阅读 · 2020年1月28日
最全Python算法实现资源汇总!
AI100
3+阅读 · 2019年5月13日
GitHub超2.7万星,最全Python入门算法来了
新智元
5+阅读 · 2019年4月28日
用OpenCV实现八种不同的目标跟踪算法
论智
7+阅读 · 2018年8月2日
从示例中理解SVM算法(附代码)
论智
8+阅读 · 2018年5月10日
一文综述人脸检测算法(附资源)
数据派THU
7+阅读 · 2018年5月8日
已删除
生物探索
3+阅读 · 2018年2月10日
2017年度图灵最受欢迎算法图书TOP10
图灵教育
10+阅读 · 2017年12月27日
循环神经网络的介绍、代码及实现
AI研习社
3+阅读 · 2017年11月21日
一文了解各种卷积结构原理及优劣
量子位
9+阅读 · 2017年7月29日
干货 | 情感分析语料库
机器学习算法与Python学习
69+阅读 · 2017年7月3日
A Modern Introduction to Online Learning
Arxiv
19+阅读 · 2019年12月31日
Arxiv
6+阅读 · 2018年4月4日
Arxiv
3+阅读 · 2018年3月21日
Arxiv
12+阅读 · 2018年1月20日
VIP会员
相关资讯
最全Python算法实现资源汇总!
AI100
3+阅读 · 2019年5月13日
GitHub超2.7万星,最全Python入门算法来了
新智元
5+阅读 · 2019年4月28日
用OpenCV实现八种不同的目标跟踪算法
论智
7+阅读 · 2018年8月2日
从示例中理解SVM算法(附代码)
论智
8+阅读 · 2018年5月10日
一文综述人脸检测算法(附资源)
数据派THU
7+阅读 · 2018年5月8日
已删除
生物探索
3+阅读 · 2018年2月10日
2017年度图灵最受欢迎算法图书TOP10
图灵教育
10+阅读 · 2017年12月27日
循环神经网络的介绍、代码及实现
AI研习社
3+阅读 · 2017年11月21日
一文了解各种卷积结构原理及优劣
量子位
9+阅读 · 2017年7月29日
干货 | 情感分析语料库
机器学习算法与Python学习
69+阅读 · 2017年7月3日
Top
微信扫码咨询专知VIP会员