访谈嘉宾：
刘新宇, 于1999年和2001年分别获得清华大学自动化系学士和硕士学位，之后长期从事软件研发工作。他关注基本算法和数据结构，尤其是函数式算法，目前就职于亚马逊中国仓储和物流技术团队。
他七年磨一剑，笔耕不辍，写成《算法新解》一书。
《算法新解》总共分4部分——树、堆、队列和序列、排列和搜索，用函数式和传统方法介绍主要的基本算法和数据结构，数据结构部分包括二叉树、红黑树、AVL树、Trie、Patricia、后缀树、B树、二叉堆、二项式堆、斐波那契堆、配对堆、队列、序列等；基本算法部分包括各种排序算法、序列搜索算法、字符串匹配算法（KMP等）、深度优先与广度优先搜索算法、贪心算法以及动态规划。
视频访谈：
https://v.qq.com/x/page/x0367...
转录文字：
新宇老师花费七年的业余时间写就这本《算法新解》，足见您对技术的这份执着！但在升职加薪、拼命加班的大环境下，怎么做到“不盲从，有见解”？
我想分享自己的两个想法。第一个想法是关于变化的。面对剧烈变化的时代，飞速发展的技术，绝大多数个体都会感到压力。出于自我保护的本能，我们需要在变化的大潮中找到相对不变的东西。什么是不变的呢? 语言？框架？还是操作系统？在我上大学的时候，实验室中还在广泛使用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的深蓝计算机战胜国际象棋大师卡斯帕罗夫的时候也有类似的感叹。
我在小学的时候，非常喜欢完井字棋游戏。就是在九宫格里，一人划叉，一人划圈，看谁先连成一条直线的游戏。我对此很是痴迷。后来学习计算机时，讲到人工智能和博弈，才了解到井字棋并不存在必胜的策略。理性的玩家总是打成平手。可是这并不妨碍我继续玩井字棋，我现在也和自己的孩子玩，而且偶尔还会输给他。我想说，我们人类能解决的问题，仅仅占到了全部问题的一小部分。如果计算机、人工智能和算法的进步能帮助我们争取时间，解决更重要的问题，那就太好了。