黑科技盒子介绍（我只是想打开那些黑盒子）
黑科技盒子介绍（我只是想打开那些黑盒子）第二个想法是关于求知的。抛开商业产品不算，人类真正在科学技术上的成就，没有一次是功利性的。诺贝尔科学奖中没有任何一位是为了获奖而研究。2006年证明了庞加莱猜想的数学家佩雷尔曼干脆拒绝去领菲尔兹奖。真正驱动我们长久进步的是好奇心。是像小孩子那样的探索世界的欲望，我只是想打开那些黑盒子，看看里面是什么。并把它分享给别人：“嘿，快来看，盒子里原来是这个样子的！”。这就是我这些年来写这本书时的情况。如果我们观察一个小孩的行为，会发现非常有趣的现象。大约在3到5岁间的孩子，不管父母怎么向他推荐新鲜的公园，好吃的餐馆和旅游度假计划，孩子却往往拒绝。他坚持重复去自己熟悉的公园，到相同的地方吃饭，假期待在自己的家里，甚至连讲故事都要求不断重复同一个故事。这是因为孩子通过重复相同的、不变的东西，获得安全感。这个世界对他来说太复杂了。我们成人何尝不是如此呢？所以害怕变化是很正常的，没有什么不好意思的。但是如
本文为图灵社区对刘新宇的专访，专访时间为2017年1月。
刘新宇，于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之前的比较。这样整个程序就化简成了一个排序算法。只要不断追求简洁优美的代码，就会自然而然产生算法的思想。对比前面的问题，我们谈的主要是如何求真，而这个问题，我们需要的是求美。
图灵：算法无处不在，它可以让我们的生活更轻松，但如果完全把我们的生活外包给计算机，会产生什么样的后果？
刘新宇：我在小学的时候，非常喜欢完井字棋游戏。就是在九宫格里，一人划叉，一人划圈，看谁先连成一条直线的游戏。我对此很是痴迷。后来学习计算机时，讲到人工智能和博弈，才了解到井字棋并不存在必胜的策略。理性的玩家总是打成平手。可是这并不妨碍我继续玩井字棋，我现在也和自己的孩子玩，而且偶尔还会输给他。我想说，我们人类能解决的问题，仅仅占到了全部问题的一小部分。如果计算机、人工智能和算法的进步能帮助我们争取时间，解决更重要的问题，那就太好了。
推荐阅读：
《算法新解》，刘新宇 著
本书同时用函数式方法和传统方法介绍了主要的基本算法和数据结构，数据结构部分包括二叉树、红黑树、AVL树、Trie、Patricia、后缀树、B树、二叉堆、二项式堆、斐波那契堆、Pairing堆、队列、序列等；基本算法部分包括各种排序算法、序列搜索算法，字符串匹配算法（KMP等），深度优先、广度有限搜索算法、贪心算法以及动态规划。
