刘新宇

于1999年和2001年分别获得清华大学自动化系学士和硕士学位,之后长期从事软件研发工作。他关注基本算法和数据结构,尤其是函数式算法,目前就职于亚马逊中国仓储和物流技术团队。

他七年磨一剑,笔耕不辍,写成《算法新解》一书。

《算法新解》总共分4部分——树、堆、队列和序列、排列和搜索,用函数式和传统方法介绍主要的基本算法数据结构,数据结构部分包括二叉树、红黑树、AVL树、Trie、Patricia、后缀树、B树、二叉堆、二项式堆、斐波那契堆、配对堆、队列、序列等;基本算法部分包括各种排序算法、序列搜索算法、字符串匹配算法(KMP等)、深度优先与广度优先搜索算法、贪心算法以及动态规划。


视频访谈:


转录文字:

新宇老师花费七年的业余时间写就这本《算法新解》,足见您对技术的这份执着!但在升职加薪、拼命加班的大环境下,怎么做到“不盲从,有见解”?

我想分享自己的两个想法。第一个想法是关于变化的。面对剧烈变化的时代,飞速发展的技术,绝大多数个体都会感到压力。出于自我保护的本能,我们需要在变化的大潮中找到相对不变的东西。什么是不变的呢? 语言?框架?还是操作系统?在我上大学的时候,实验室中还在广泛使用Fortran语言用于科学计算。但是几年之间,C语言就替代了Fortran成为了主流语言。今天,各种新语言更是层出不穷;框架也是如此,我还记得上学的时候,大家怀着很高的热情学习微软的MFC框架。可是今天,除了在个别场合,很少有人还在用MFC了。各种框架也是如雨后春笋一般出现在各种领域;操作系统呢?我曾经在诺基亚的Symbian操作系统上开发了近10年。在Tanenbaum的经典教科书《现代操作系统》的附录中,Symbian被作为成功的嵌入式操作系统案例加以讲解。可是2011年,Symbian几乎在转瞬之间就轰然倒塌。2014年,当我完成这本书的英文草稿的时候,正逢诺基亚解散。这些经历使得我不断思考这一问题。

如果我们观察一个小孩的行为,会发现非常有趣的现象。大约在3到5岁间的孩子,不管父母怎么向他推荐新鲜的公园,好吃的餐馆和旅游度假计划,孩子却往往拒绝。他坚持重复去自己熟悉的公园,到相同的地方吃饭,假期待在自己的家里,甚至连讲故事都要求不断重复同一个故事。这是因为孩子通过重复相同的、不变的东西,获得安全感。这个世界对他来说太复杂了。我们成人何尝不是如此呢?所以害怕变化是很正常的,没有什么不好意思的。但是如果我们继续观察这个孩子,会发现随着成长,在他逐渐掌握了身边的世界后,那颗好奇心就会驱使他出去探险,去探索未知的世界。

第二个想法是关于求知的。抛开商业产品不算,人类真正在科学技术上的成就,没有一次是功利性的。诺贝尔科学奖中没有任何一位是为了获奖而研究。2006年证明了庞加莱猜想的数学家佩雷尔曼干脆拒绝去领菲尔兹奖。真正驱动我们长久进步的是好奇心。是像小孩子那样的探索世界的欲望,我只是想打开那些黑盒子,看看里面是什么。并把它分享给别人:“嘿,快来看,盒子里原来是这个样子的!”。这就是我这些年来写这本书时的情况。

最后,我用两个例子结束这个问题:一个是数学家陈省身先生的例子,在抗日战争中最艰难的日子,大家朝不保夕,颠沛流离,他却反而静下心来学习研究微分几何,发现陈类(陈省身示性类)。2016年的诺贝尔物理学奖中的一个发现,就是物质的拓扑相中的量子化整数是陈省身数。第二个例子是大学问家钱钟书,他也是在抗日战争中的敌占区上海,每天锱铢积累,写的《围城》。他们都是我的榜样。

您负责的仓储和物流技术中,运用了哪些算法?

亚马逊的仓储和物流系统,是一个非常复杂的系统。其复杂程度会出一般人的想象。这是一个分布在全球的仓储网络,面临着巨大的技术挑战。在每年的第四季度,连续放假、过节,新年、圣诞、感恩节、黑色星期五、双十一时,消费者拼命购物,卖家和供应商拼命进货,这在物理上和数据上都对仓储和物流系统形成了巨大的冲击。出于业务上的挑战,我们把自己的技术架构在亚马逊的云计算平台AWS上,处理大数据下的高可靠性、并发性和一致性的问题。这里会用到很多的算法,包括最优化的算法和机器学习算法,等等。我们会根据库房的容量对货物在仓储网络中做优化的配置,我们会使用机器学习预测进出库的时间,等等。正因如此,亚马逊对于研发团队工程师的算法能力有很高的要求。在亚马逊的面试中,算法与数据结构是一个必考的环节,甚至是一票否决的。

听说,您曾经在去匈牙利出差的飞机上,居然看了一路的数学书,还是英文版的?这不免让我们回到老生常谈的问题——“算法跟数学的关系”。

其实我还看了一本中文的,名叫《斐波那契数列》。算法是数学的分支。

我想分享一下,“算法” 这个词的来历。公元9世纪,也就是中国的唐朝,在阿拉伯文明的中心——巴格达,有一位来自东方的大学者刚刚完成了一本著作,书名叫《还原与对消的科学》(Kitab al-Jabr wa-l-Muqabala),讲述了如何解二次以内的方程。人们用这本书的拉丁文简称Al-Jab,创造了词Algebra。1859年,李善兰与英国传教士伟列亚力创造性地将其翻译为“代数”。

遗憾的是,没有人知道这位侨居在巴格达的数学家的真正名字。人们只知道他来自一个名叫花剌子模的东方国家。金庸先生写的《射雕英雄传》让这个国家的名字在华人圈得以普及(就是郭靖与黄蓉帮助成吉思汗攻破的国家)。如今的乌兹别克斯坦的撒马尔罕,至今仍立有这位数学家的雕像。于是来自(Al)花剌子模(Khwarimi)的人,Al-Khwarimi(阿尔-花剌子密)就成了这位数学家的名字。它的拉丁文译法为Algorithm,中文译作“算法”。

为什么用这位数学家的名字来命名算法呢?这要谈谈花剌子密是怎样描述解方程的。在著作中,他使用了详细的文字来描述解方程的步骤。这和我们现在描述计算机算法的的方式几乎一模一样。其实,我们的前辈在发展代数时,大约经历了三个阶段:文辞代数、简字代数、和符号代数。早期的各个文明,绝大多数都采用详细的文字来记述解决问题的过程和步骤。我们中国的老祖先在很早以前就使用算筹,实现了多元线性方程组的求解。如果阅读《九章算术》,就会发现它也是用文字描述,讲解了方程组的解法(本质上就是高斯消元法)。直到16世纪,文辞代数仍然是主流的代数描述手段。后来古希腊的丢番图,逐渐使用了一些符号简记方法,发展了简字代数。现代的符号代数在莱布尼茨时达到了顶峰。极大提高了数学语言的严谨性和表达能力。可是反观我们现在的算法描述和很多计算机语言,似乎仍然停留在文辞代数阶段。一段算法或者程序写下来,更像一段文章,而不是一组简约的符号化、形式化的公式或者图形。这一想法也是我在写这本书时逐渐形成的,我也一直在思考这个问题。

《算法新解》里的“新”字怎么解释?

新是相对的,新的东西可以变成旧的,旧的东西也会焕发新生。这本书中大量介绍的函数式算法,对于很多传统程序员来说,也许比较陌生,是需要了解的新东西。其实它的历史却并不短。在20世纪30年代,人们就开始研究可计算性问题,这是一个关于数学基础的问题。我们计算机行业的老祖师图灵,和美国普林斯顿的丘奇(Alonzo Church)分别独立地提出了各自的模型(同时代的其他研究者还包括哥德尔(Kurt G?del)和克莱尼(Kleene),这一问题后来被称为丘奇——图灵论题)。其中图灵使用了图灵机的想法,而丘奇则使用了Lambda演算(波斯特还给出过递归函数的模型)。这些模型后来被证明都是等价的。

当然可计算性问题最终给出的是一个否定的答案,著名的图灵停机就是一个反例。其中丘奇的Lambda演算,成为了后来函数式计算模型的理论基础,直接孕育了Lisp语言,就是世界上第二早的高级语言。对于函数式编程和算法的研究也一直在学术领域进行。由于基于传统的命令式的方法,包括我们熟知的面向对象方法在工业和商业上取得了巨大的成功,因此函数式方法对于大多数程序员比较陌生,属于“新鲜事物”。但是最近这一情况正在改变,越来越多的主流编程语言开始加入一些函数式的特性,如C++、Java 8都加入了对lambda的支持。

图灵奖获得者,迪杰斯特拉(Dijsktra) 说过:“程序=数据结构+算法”。使用函数式编程,如果不了解函数式算法就只能停留在表面,写出像“hello world”这样的简单程序。 这也是《算法新解》这本书希望能够帮助读者的一点。

这本书的章节安排和传统的大多数算法书不同,这也算是“新”的一个体现吧。按照函数式的思维,许多在命令式算法中比较复杂、困难的东西,一下子变得简单了,“红黑树”就是这样一个例子。使用函数式算法后,红黑树的实现只需要16行。这样按照难度来算,红黑树就排在了前面 。相反,有些看似容易的东西,想用函数式的方式实现却并不简单,例如队列和序列。我把这些比较难的内容安排在了后面。如果讲解完一个函数式的数据结构后,我们发现能立即用来实现某个算法,就穿插着讲一章算法。例如插入排序被安排在二叉树后,选择排序被安排在堆的后面就是这个原因。函数式算法的最底层、最基础的数据结构是链表,反复斟酌后,我把它作为附录列在书后。有一些函数式编程基础的读者可以随时参考,而零基础的读者可以先集中看一下。

命令式编程中的算法多使用状态记录,对于无状态的函数式编程该怎样找到对应的算法?

对这个问题,我想打个比方。这就好比代数和几何的关系。大家在上学时一定有这样的体会:有些代数问题,一旦转化成几何问题,就变得特别简单直观。一个简单的图形,加上一条辅助线,瞬间就解决一个复杂的问题。相反,有些特别难的几何问题,一旦用解析几何转换成方程,一下子就变得很简单了。

命令式编程和函数式编程也是如此。我们并非说一种方法就一定比另一种方法好,而是说某些问题,一旦转换思路反而比较容易。有时是函数式算法容易一些(例如红黑树),有时是命令式算法直观容易一些(例如KMP匹配算法)。

其实函数式的方法并不那么难理解。我是在中学接触到计算机编程的,当我第一次看到x=x+1这样式子时,着实花费了很大的功夫来理解。因为按照数学课上的思维,我会不自觉地想要把等式两边的x消去,这样不就成了0=1了么?当然,按照命令式的思维,我们是把一个盒子里的东西取出来,加上1后再装进去。所以函数式的思维,强调不变性,也许更加符合我们长久以来形成的解决问题的习惯呢。当然,也有一些地方是命令式思维更加自然。例如一位同学绕着操场跑步,手里拿着计数器,每跑完一圈就按一下使得计数器加一。这样用命令式的方式思考就更加自然。因此,我们不要强求一定找到一个对应的函数式算法或者命令式算法,而是不断地转换思维,用最有效的方法来解决问题。

设计算法时,通常使用顺序模型,很少考虑算法的并行化扩展。但是在实际应用中,很多难以并行扩展的算法由于时间上不能满足要求而被放弃。您认为设计算法时是不是应该考虑并行扩展的因素?

是的,我们要考虑并行。由于摩尔定律不再适用,人们不得不发展并行计算。而函数式方法具有一些特点,如强调不变性,无副作用。对于任何一个函数,在相同的时间、地点、用相同的参数调用,总是能得到同样的结果。这些特性特别有利于并行计算,因为现代编译器和运行系统,可以方便地对这种无副作用的计算进行并行。这也是为何近年来Erlang、Scala等函数式编程语言流行的一个原因。

市面上大部分的算法书虽然给出了具体算法和效率分析,但很少对算法的正确性给出证明。您认为证明算法的过程在算法学习中是否重要?

我想从更宽泛的角度谈谈证明的意义。证明不在于确认或者推翻一个结论,而在于在证明过程中发展出来的方法和工具。例如,人们探求5次以上的方程是否存在根式解的过程中,这里有两个非常感人和值得我们深思的故事,一个是丹麦的阿贝尔,一位是法国的伽罗瓦。在他们之前,人们虽然攻克了4次以下方程的求根公式,但是在5次方程上持续了几百年都没有进展。阿贝尔和伽罗瓦独立发展出了群论,最终证明了5次以上方程没有根式解。虽然这是个否定的结论,但是在这一证明过程中发展出的群论和抽象代数,成为了特别强大的工具,可以帮助我们解决更多的问题。现代计算机科学的前沿:设计安全的编程语言,就在使用范畴论,而范畴论正式从抽象代数的基础上进一步发展出来的。 另一个例子是著名的费马大定理,证明采用了椭圆函数论,现在我们知道,这是现代密码学的理论前沿。

证明对于算法学习有促进作用,证明迫使我们更加深入思考,甚至从不同视角看待一个问题。例如,我们熟知的喝醉酒的狱卒问题。典狱长第一次将所有灯的开关板动一次;第二次把第2、4、6……这样的偶数开关板动一次;第三次把所有被三整除的开关扳动一次……问最后哪些灯亮着?当解决这个问题后,观察答案,就会发现它们都是完全平方数?为什么是这样的结论呢?有没有可能证明这个结论呢?深入思考就会发现这个问题的本质是思考哪些数有奇数个因子。这样就加深了我们的理解。因此,证明的过程对于学习算法是非常有帮助的。

对于初学者来说,学习算法很枯燥。有哪些方法可以发现算法的乐趣?

我想做一个类比,在学校学习数学和物理时,你觉得哪一门不那么枯燥呢?是数学还是物理?我想可能选物理的同学会更多一些。这是因为物理老师很会讲故事,就是现在我们网络上常说的“段子手”。物理中有太多精彩的故事了,伽利略的比萨斜塔实验故事,阿基米德和王冠的故事,牛顿的苹果和万有引力的故事(虽然有人说是牛顿侄女杜撰的),法拉第发现电磁感应的故事,居里夫人发现镭的故事,爱因斯坦的故事和逸闻趣事就更多了。可是相比起来,数学教科书的故事就少的可怜。印象中只有神童高斯解决1加到100的故事。其实数学里面也有很多精彩的故事,例如希帕索斯发现了无理数被谋杀的故事, 阿基米德死前还在地上绘图的故事,牛顿和莱布尼茨争论谁先发明了微积分的故事,希尔伯特讲的无穷旅馆的故事。还有伽罗瓦死于决斗的悲剧故事。

学习算法时,我们同样需要有趣的故事。有许多算法来自历史上的著名趣题。例如约瑟夫环问题,讲述的是犹太——罗马战争中约瑟夫和其他总共41人被困后,每间隔一人就自杀,问想幸存下来,要站在哪个位置上的问题。又比如五猴分桃问题,讲述五只猴子采桃后,每只猴子都偷偷醒来,吃掉自己的一份,然后在平分桃子,问一共有多少桃子的问题。还有汉诺塔问题、野人修道士问题、嫉妒的三对夫妻问题、华容道问题,等等。思考和解决这些趣题是充满乐趣的。

还有相当一部分人学习算法的时候,主要靠“背算法”。实际工作中,无法把问题很好地抽象到算法层面。该如何训练这种算法思维呢?

有很多程序员标榜自己是完美主义者,是代码洁癖。我觉得这很好,但是我们不能仅仅把洁癖停留在缩进、括号、和空格上;也不能仅仅停留在final和const这些关键字的使用上。当看到代码不美,不简洁,有重复时,通过抽象、改进,会慢慢发展算法思维。我以前曾经开发过这样一个程序,在社交app的列表中要显示用户的好友,产品上设计了很复杂的业务逻辑。比如,在线的好友在前面显示,离线的在后面显示,VIP在前面显示,最近聊过天的在前面显示,等等。代码中有很多if-else来实现这些复杂的逻辑。经过思考,最终把这些复杂的业务逻辑抽象成了当给定好友A和好友B时,如何决定A在B之前的比较。这样整个程序就化简成了一个排序算法。只要不断追求简洁优美的代码,就会自然而然产生算法的思想。对比前面的问题,我们谈的主要是如何求真,而这个问题,我们需要的是求美。

算法无处不在,它可以让我们的生活更轻松,但如果完全把我们的生活外包给计算机,会产生什么样的后果?

最近谷歌的AlphaGo战胜了人类的围棋大师李世石,接着又横扫了中日韩的围棋高手,有人哀叹,围棋从我们最感兴趣的游戏变成了没人愿意玩的游戏?其实,多年前IBM的深蓝计算机战胜国际象棋大师卡斯帕罗夫的时候也有类似的感叹。

我在小学的时候,非常喜欢完井字棋游戏。就是在九宫格里,一人划叉,一人划圈,看谁先连成一条直线的游戏。我对此很是痴迷。后来学习计算机时,讲到人工智能和博弈,才了解到井字棋并不存在必胜的策略。理性的玩家总是打成平手。可是这并不妨碍我继续玩井字棋,我现在也和自己的孩子玩,而且偶尔还会输给他。我想说,我们人类能解决的问题,仅仅占到了全部问题的一小部分。如果计算机、人工智能和算法的进步能帮助我们争取时间,解决更重要的问题,那就太好了。


——更多访谈


更多精彩,加入图灵访谈微信!