锐客网

  1. 首页 > it技术 > >

第057封信|第057封信 | 什么是好的计算机算法（对效率影响有多大？）

☆怦然*%心☆_☆动，你好！
几周前有些读者朋友讲，第二季的课程似乎不够深，其实我倒从来不担心计算机的课程讲得不够深，而担心讲得不够浅。其实，所有诺贝尔奖得主的技术报告做得都非常浅，稍微有些专业背景的人都能听得懂，然后回味出其中的妙处的。而我自己讲课多年的实践也证明最大的问题是难以把知识往浅里讲，以至于很多人没有听明白，而不是深奥的内容讲得不够多。因此，为了把内容讲浅，前几周作了铺垫，从这周开始，我们会讲理论性相对强的内容了。当然，我依然要争取让它听起来非常轻松。
今天我们先介绍一个计算机科学的基本做事原则，就是首先要构建可比较的理想、容易对比的平台，明确一个公平的比较标准，也就是说事先要讲好游戏规则，然后再开始做研究，确定基线，对比这种方法的优缺点。 这种方法其实对所有的科学都适用，但是并非人们自发性的做事情方法，因此，在计算机科学的发展过程中，科学家们认识到这一点也是花了20年左右的时间。
我们在前面讲了，计算机里面控制部分很重要，而控制硬件运行的是程序。在第2周的问答环节中，史元春教授讲了计算机思维的本质是翻译，也就是把人想要做的具体事情，翻译成计算机能够懂得的程序语言。很多时候，张三希望计算机做的一件事，和李四希望它做的一件事，有一些共性的地方，久而久之大家发现使用计算机工作的流程是相似的，于是科学家们在翻译现实世界的需求和计算机虚拟过程时，就提炼出一些高效的、不断被验证过的标准流程，这些流程就是我们所说的计算机算法。
因此你可以将计算机算法理解成盖房子时打地基，砌墙，上房梁屋顶和安装门窗的标准流程。我们在前面讲过模块化是计算机思维很重要的思想，而在软件中，那些模块就是一个个算法。因此算法构成了计算机科学的基础。
我经常讲，人和人水平的差别，东西和东西质量的差别，是数量级的，这个认识恰恰来自于计算机算法。因为在计算机算法上稍微差了一点，最后计算机执行的效率很容易差出千万倍，当然我的这个体会是亲身经历的教训换来的。
我在大学四年级暑假的时候，和几个同学到外地一个工厂去实习，给对方开发了一个财务软件。我们教会工厂的会计使用方法，然后他把工厂一个月的财务数据用我们的软件管理起来，一切都运行得非常好，我们就放心地回北京了。一年后，对方反映软件中的对账功能变得越来越慢，我就询问了在项目中开发这个模块的同学，发现他在编写对账程序时用了一个笨办法，以至于当数据量大10倍之后，对账时间多出好几十倍。当初对一次账是几秒钟时间，后来就变成了半小时，工厂的财务觉得这个软件慢得难以忍受了。最后，我们不得不派家在当地的一个同学去小作修改，一共改了十几行程序，问题就解决了。从这以后，我在计算机算法上就非常在意效率，这让我从清华，到约翰·霍普金斯，再到Google都非常受益。
我在之前的来信中讲，人本能地对大数没有概念，其实对超过我们生活经验的小数也是如此，计算机算题的速度很快，以至于人们对一毫秒（千分之一秒）和一微秒的差别是无感的，但是，计算机要处理的数据量也是非常大的，因此累计起来，后者就比前者快了很多（一千倍）。很多计算机从业者对计算机资源的数量没有概念，总觉得是无穷大，因此无端浪费很多资源，这样做事情，在行业里是很难出人头地的。即使在Google，软件工程师因为水平不行，无意中多用掉十倍的计算资源的事情也时常发生。
既然讲到了算法的好坏，就必须先要明确衡量算法的标准，以及测试的方法，这和任何科学都一样。什么是好算法呢？很多人首先会想到"速度快"，当然还有人会想到占用内存空间不要太大。制定这样两个标准，大方向本身都没有问题，但用多少数据来测试算法的速度和空间却是一个问题，因为用不同数量的数据测试时，两个算法的相对表现可能会完全不一样。
我们不妨看这样两个场景下，A、B两种算法的速度：
场景一：使用1万个数据进行测试，算法A的运行时间是1毫秒，算法B则需要运行10毫秒。
场景二：使用100万个数据测试，算法A运行10000毫秒，算法B运行6000毫秒。
这时我问你，哪一个算法好？如果单纯从第一个场景作判断，显然是算法A好，但是如果单纯看场景二，似乎算法B更好一点。按照人的思维，可能会说，数量小的时候算法A好，数量大的时候算法B好，然后还津津乐道自己懂得辩证法。计算机则不同，它比较笨，比较直接，不会辩证法，它要求你最好制定一个明确的标准，不要一会儿这样，一会儿那样。那么，这时候，我们应该用什么标准来评判呢？
在计算机科学发展的早期，其实科学家们对这件事情也不是很清楚。1965年哈特马尼斯（Juris Hartmanis）和斯坦恩斯（Richard Stearns）提出了算法复杂度的概念（二人后来因此获得了图灵奖），计算机科学家们开始考虑一个公平的、一致的评判算法好坏的方法。不过，最早将复杂度严格量化衡量的是著名计算机科学家、算法分析之父高德纳（Don Knuth）。今天，全世界计算机领域都以高德纳的思想为准。
高德纳的思想主要包括这三个部分：
【第057封信|第057封信 | 什么是好的计算机算法（对效率影响有多大？）】1. 在比较算法的快慢时，需要考虑数据量特别特别大，大到近乎无穷大时的情况。为什么要比大数的情况，而不比小数的情况呢？因为计算机的发明就是为了处理大量数据的，而且数据越处理越多。比如我和同学们做砸了的那件事，就是没有考虑数据量会迅速剧增。
2. 决定算法快慢的因素虽然可能很多，但是所有的因素都可以被分为两类。第一类是不随数据量变化的因素，第二类是随着数量变化的。
比如说，有一种大小排序的算法，它的运算次数是10倍的N平方，其中N是要排序的数字的数量。前面的那个10倍是个常数，和N的大小显然没有关系，10个数排序是如此，一亿个数排序时也是如此。而后面的N平方自然和N有关系了。高德纳讲，我们在研究算法时，不必考虑前面那个不变的常数，它是10倍，还是1倍，或者是100倍，只需要看后面那个变化的因素即可。
因为N这个数趋近于无穷大时，前面那个不变的常数的影响是微乎其微的，算法的速度主要由后面一个因素决定。比如，当N＝10的时候，N平方就是100；N＝100，N平方就是1万；N＝1万，N平方就是一亿……总之，N平方这个因子的变化非常快。更广泛地讲，任何随着N变化的因素，通常会造成量级的差异。关于量级，我们在第005封来信里讲了。量级就如同芝麻和西瓜的差异，西瓜和地球的差异。100个芝麻是无法和一个西瓜去对比的。
3. 如果两种算法在量级上相当，在计算机科学里，就认为它们是一样好的，也就是计算机科学家并不关心三五倍的差别，这就好比1粒芝麻和5粒芝麻都是芝麻量级的东西，大家就不要比了。只有当科学家们不关心几倍的差异后，才可能集中精力考虑量级的差异。也就是说，计算机科学家要尽可能地去捡西瓜。事实上在计算机科学领域，如果谁说自己把目前最好的算法速度提升了一倍，这种论文是无法发表的。
我在第005封信中讲量级的重要性，事实上我是受到高德纳这些思想的启发。高德纳关于算法复杂度的思想，其实又是建立在一个相对理想状态之下的，也就是说计算机要解决的问题都近乎无限大。很显然，现实世界并非如此，那么高德纳这样理想化的假设是否有意义呢？非常有意义，而且非常重要。
回顾一下科学发展的历史，那些能总结出理论的人要做的第一件事，就是过滤掉所有次要的因素，构建一个理想的环境（或者虚拟的环境）。
当年亚里士多德就是因为无法滤除空气阻力对重力加速度的影响，得到了重物比轻物下降速度快的荒唐结论。而后来伽利略和牛顿在研究运动时，也是假设空气阻力和摩擦力可以忽略不计的，那就是构建理想状态。
类似地，和牛顿同时代的科学家波义耳和马略特在研究气体压强和空间大小的关系时，也构造出理想的气体状态。
将世界理想化的目的在于，找到真正的主要矛盾，过滤出那些相对次要的噪音，先把主要问题解决了再说。这些人的思维方式，比普通人是高出一大截的。我们都同意艺术上要有想象力，其实在科学上也是如此，抽象的想象力很重要。
高德纳比同时代的人高出一筹的地方也在于，他构建出了计算机科学的理想状态。
当然，凡事不能走极端，我们有时发现一些科学家想法非常天真，他们把整个世界全都理想化了，这当然也不行。
从明天开始，我们通过实际例子，说明在计算机这个行业里，成千上万倍的效率是如何差出来的，那些不同的做法对我们有什么启发。
最后请你思考一下：能否就如何将问题抽象出来，以便于抓住本质，发表你的看法？

    推荐阅读


    上一篇：最近的一点读书感悟

    下一篇：谣言和传闻