算法是核算机科学范畴最重要的柱石之一，但却受到了国内一些程序员的萧瑟。许多学生看到一些公司在招聘时要求的编程言语形形色色就产生了一种误解，以为学核算机便是学各种编程言语，或许以为，学习最新的言语、技能、规范便是最好的铺路方法。其实咱们都被这些公司误导了。编程言语尽管该学，可是学习核算机算法和理论更重要，由于核算机算法和理论更重要，由于核算机言语和开发渠道一日千里，但万变不离其宗的是那些算法和理论，例如数据结构、算法、编译原理、核算机体系结构、联系型数据库原理等等。在“开复学生网”上，有位同学生动地把这些根底课程比拟为“内功”，把新的言语、技能、规范比拟为“外功”。整天赶时髦的人最终只懂得招式，没有功力，是不行能成为高手的。
算法与我
当我在1980年转入核算机科学系时，还没有多少人的专业方向是核算机科学。有许多其他系的人讪笑咱们说：“知道为什么只需你们系要加一个‘科学’，而没有‘物理科学系’或‘化学科学系’吗？由于人家是真的科学，不需求弄巧成拙，而你们自己心虚，生怕不‘科学’，才这样相得益彰。”其实，这点他们完全弄错了。真实学懂核算机的人（不只是“编程匠”）都对数学有适当的造就，既能用科学家的谨慎思想来求证，也能用工程师的务实手法来处理问题——而这种思想和手法的最佳演绎便是“算法”。
记住我读博时写的Othello对弈软件获得了世界冠军。其时，得第二名的人以为我是靠幸运才打赢他，不服气地问我的程序均匀每秒能查找多少步棋，当他发现我的软件在查找功率上比他快60多倍时，才完全服输。为什么在相同的机器上，我能够多做60倍的作业呢？这是由于我用了一个最新的算法，能够把一个指数函数转换成四个近似的表，只需用常数时刻就可得到近似的答案。在这个比方中，是否用对算法才是能否赢得世界冠军的要害。
还记住1988年贝尔试验室副总裁亲身来拜访我的校园，意图便是为了想了解为什么他们的语音辨认体系比我开发的慢几十倍，并且，在扩展至大词汇体系后，速度差异更有几百倍之多。他们尽管买了几台超级核算机，牵强让体系跑了起来，但这么贵的核算资源让他们的产品部分很恶感，由于“贵重”的技能是没有运用远景的。在与他们讨论的过程中，我惊奇地发现一个O(n*m)的动态规划(dynamic programming)竟然被他们做成了O(n*n*m)。更惊奇的是，他们还为此宣布了不少文章，甚至为自己的算法起了一个很特别的姓名，并将算法提名到一个科学会议里，希望能得到大奖。其时，贝尔试验室的研讨员当然绝顶聪明，但他们全都是学数学、物理或电机身世，从未学过核算机科学或算法，才犯了这么根本的过错。我想那些人今后再也不会讪笑学核算机科学的人了吧！
网络时代的算法
有人或许会说：“今日核算机这么快，算法还重要吗？”其实永久不会有太快的核算机，由于咱们总会想出新的运用。尽管在摩尔定律的作用下，核算机的核算才能每年都在飞快添加，价格也在不断下降。可咱们不要忘掉，需求处理的信息量更是呈指数级的添加。现在每人每天都会创造出许多数据（相片，视频，语音，文本等等）。日益先进的纪录和存储手法使咱们每个人的信息量都在爆破式的添加。互联网的信息流量和日志容量也在飞快添加。在科学研讨方面，跟着研讨手法的前进，数据量更是到达了史无前例的程度。无论是三维图形、海量数据处理、机器学习、语音辨认，都需求极大的核算量。在网络时代，越来越多的应战需求靠杰出的算法来处理。
再举另一个网络时代的比方。在互联网和手机查找，假如要找邻近的咖啡店，那么查找引擎该怎样处理这个恳求呢？最简略的方法便是把整个城市的咖啡馆都找出来，然后核算出它们的地点方位与你之间的间隔，再进行排序，然后回来最近的成果。但该怎么核算间隔呢？图论里有不少算法能够处理这个问题。
这么做或许是最直观的，但肯定不是最敏捷的。假如一个城市只需为数不多的咖啡馆，那么这么做应该没什么问题，横竖核算量不大。但假如一个城市里有许多咖啡馆，又有许多用户都需求相似的查找，那么服务器所接受的压力就大多了。在这种情况下，咱们该怎样优化算法呢？
首要，咱们能够把整个城市的咖啡馆做一次“预处理”。比方，把一个城市分红若干个“格子(grid)”，然后依据用户地点的方位把他放到某一个格子里，只对格子里的咖啡馆进行间隔排序。
问题又来了，假如格子巨细相同，那么绝大多数成果都或许出现在市中心的一个格子里，而市郊的格子里只需很少的成果。在这种情况下，咱们应该把市中心多分出几个格子。更进一步，格子应该是一个“树结构”，最顶层是一个大格——整个城市，然后逐层下降，格子越来越小，这样有利于用户进行准确查找——假如在最底层的格子里查找成果不多，用户能够逐级上升，扩大查找规模。
上述算法对咖啡馆的比方很有用，可是它具有通用性吗？答案是否定的。把咖啡馆笼统一下，它是一个“点”，假如要查找一个“面”该怎样办呢？比方，用户想去一个水库玩，而一个水库有好几个进口，那么哪一个离用户最近呢？这个时分，上述“树结构”就要改成“r-tree”，由于树中心的每一个节点都是一个规模，一个有鸿沟的规模（参阅:~hjs/rtrees/index.html）。
通过这个小比方，咱们看到，运用程序的要求千变万化，许多时分需求把一个杂乱的问题分解成若干简略的小问题，然后再选用适宜的算法和数据结构。
并行算法：Google的中心优势
上面的比方在Google里就要算是小case了！每天Google的网站要处理十亿个以上的查找，GMail要贮存几千万用户的2G邮箱，Google Earth要让数十万用户一起在整个地球上漫游，并将适宜的图片通过互联网提交给每个用户。假如没有好的算法，这些运用都无法成为实践。
在这些的运用中，哪怕是最根本的问题都会给传统的核算带来很大的应战。例如，每天都有十亿以上的用户拜访Google的网站，运用Google的服务，也产生许多许多的日志(Log)。由于Log每份每秒都在飞速添加，咱们必须有聪明的方法来进行处理。我曾经在面试中问过关于怎么对Log进行一些剖析处理的问题，有许多面试者的答复尽管在逻辑上正确，可是实践运用中是简直不行行的。依照它们的算法，即运用上几万台机器，咱们的处理速度都根不上数据产生的速度。
那么Google是怎么处理这些问题的？
首要，在网络时代，就算有最好的算法，也要能在并行核算的环境下履行。在Google的数据中心，咱们运用的是超大的并行核算机。但传统的并行算法运转时，功率会在添加机器数量后敏捷下降，也便是说，十台机器假如有五倍的作用，添加到一千台时或许就只需几十倍的作用。这种事半功倍的价值是没有哪家公司能够负担得起的。并且，在许多并行算法中，只需一个结点犯过错，一切核算都会前功尽弃。
那么Google是怎么开宣布既有功率又能容错的并行核算的呢？
Google最资深的核算机科学家Jeff Dean知道到，Google所需的绝大部分数据处理都能够归结为一个简略的并行算法：Map and Reduce（）。这个算法能够在许多种核算中到达适当高的功率，并且是可扩展的（也便是说，一千台机器就算不能到达一千倍的作用，至少也能够到达几百倍的作用）。Map and Reduce的别的一大特征是它能够使用大批廉价的机器组成功能强大的server farm。最终，它的容错功能反常超卓，就算一个server farm宕掉一半，整个fram仍然能够运转。正是由于这个天才的知道，才有了Map and Reduce算法。凭借该算法，Google简直能无限地添加核算量，与一日千里的互联网运用一起生长。
算法并不局限于核算机和网络
举一个核算机范畴外的比方：在高能物理研讨方面，许多试验每秒钟都能有几个TB的数据量。但由于处理才能和存储才能的缺乏，科学家不得不把绝大部分未经处理的数据丢掉掉。可咱们要知道，新元素的信息很有或许就藏在咱们来不及处理的数据里边。相同的，在其他任何范畴里，算法能够改动人类的日子。例如人类基因的研讨，就或许由于算法而创造新的医疗方法。在国家安全范畴，有用的算法或许防止下一个911的产生。在气候方面，算法能够更好地猜测未来天灾的产生，以解救生命。
所以，假如你把核算机的开展放到运用和数据飞速添加的大环境下，你一定会发现；算法的重要性不是在日益减小，而是在日益加强。
