黑铁时代的算法“悖论”
www.dreamland.org.cn 2007-2-18 Dreamland
黑铁时代的算法“悖论”
在我的印象里，从来也没有哪件事情能像算法在国内程序员心中的“映射”那样奇特和复杂。套用古希腊人的说法，历史的演进总要以秩序日趋混乱和话语权逐渐分散为代价。1970年以前，当那些令人景仰的IT先驱们沉浸于计算技术的美妙绝伦时，算法在为数不多的程序员心中，也许就和克洛诺斯在天国中的地位一样，是足以统治整个黄金时代的精神力量。在随之而来的白银时代（大概以UNIX的兴起和繁荣为起迄时间吧）和青铜时代（当然是Windows和桌面计算一统天下的时代）中，算法仍足以与其他蓬勃兴起的技术要素（比如语言和平台）分庭抗礼。但在网络时代的中国，算法却陷入了颇为尴尬的境地：有关算法重要性的话题竟然成了展开BBS论战的最好诱因；“算法无用论”居然被用做了网络“砖家”们赖以出名的金字招牌；在主流技术媒体中，算法的位置也早已被难以计数的“新框架”和“新标准”所取代——对算法而言，这是一个不折不扣的黑铁时代。在这样的时代里讨论算法的价值并介绍相关的学习方法，这并不是一件十分招人喜欢的事。幸好，我是一个不太愿意关心或追随“主流”[屏蔽]的程序员，又是一个没事儿时总想提高程序效率和可用性的工程师——很愿意结合自己的感受谈些与算法相关的话题。祝大家阅读愉快！
算法的重要性 ——这真有讨论的必要吗？作为旁观者（AKA潜水员），我看过许多有关算法重要性的网上口水战。说实话，我一直都不觉得这件事真有讨论的必要，直到有一天，我读到了这样一条有关算法的“悖论”:因为算法很重要，所以，在我们想要设计或封装某种高水平的算法之前，总已经有人把类似的事情做得很好很好了；于是，程序员只要知道算法库的接口就可以了；由此可知，算法一点儿也不重要。这则“悖论”出自一位经常帮别人扣上“重新发明轮子”的大高帽的网友，或许我们可以把它看做“轮子帮”的看家本领之一。要[屏蔽]这种所谓的“悖论”其实不算太难，细心的读者应该很容易发现其中不符合逻辑或曰无法“自洽”的地方。不过在这里，我并不想把这篇“漫话”性质的文章变成论证严密的逻辑辨析，还是用一句引语和两个实例来藐视这种不负责任的“悖论”吧。在MIT那本颇有分量的《算法导论》第二版中，作者是这样描述算法的重要性的:是否在算法知识和算法技能方面拥有扎实的基础，这是区分真正的编程高手与编程菜鸟的一个标志。借助现代计算技术，即便对算法知之甚少，你也可以完成某些任务；但是，如果有一个良好的算法基础，你所能做的事情就会更多、更多。在《JOEL说软件》一书中，著名的Joel Spolsky先生在全书的开头就抛给了所有程序员一个巨大的问号：C语言中处理字符串的方式是最优的解决方案吗？我知道99.99%程序员都会熟练使用strcpy或是strcat，但一定有相当多的程序员无法[屏蔽]回答这样一个看似简单的问题。既然C语言的运行库已经为我们提供了处理字符串的基本数据结构和基本算法（没错，算法无处不在，即便是获取字符串长度这样极简单的操作，不同的算法实现也有效率高低的差别），我们还有必要仔细测量这些可复用的“轮子”是圆是方吗？很遗憾，Joel告诉我们，C语言对字符串的处理是“最差的方法之一”；在许多情况下，“用户应该像躲避瘟疫一样地避开使用ASCIZ字符串”。Joel还很得意地告诉我们，他参与开发的Excel软件在内部使用Pascal格式的字符串，这是“Excel的速度快得出奇的一个原因”。如果说Joel与Excel的故事还不足以说明算法知识或算法技能在我们身边的重要性，那么，我这里还有一个和大家更近一些的真实案例。2003年，我们为上海一家银行开发一套企业级报表管理软件。当时，银行每天打印的报表超过10万页，此外还有大约1万余份的PDF或XLS报表需要存储、索引和管理。程序员们的工作十分顺利，系统很快上线运行，客户对产品还算满意。到了2003年底，每日产生的报表量翻了一番。按说，这样的潜在需求增长原本是签在合同里的，程序员设计系统时也“充分”考虑了软硬件的冗余处理能力。但不幸还是发生了：业务量增加以后，原本只需要40分钟即可完成的报表导入、解析和索引流程硬是延长到了5个小时，在磁盘阵列和永久存储设备（主要是DVD库）之间同步数据的操作也要多花上4个小时。客户每天日终处理之后留给系统的可支配时间被大大超支，其结果自然是第二天上班的业务人员在中午吃饭前多半查不到头一天的任何报表——用客户方项目负责人的话说就是:“后果很严重，[屏蔽]很生气。”一名项目经理立即被派往现场解决问题。实地考察之后，项目经理拍着胸脯对客户说:“只要增加3台服务器和1部DVD库，并将原有服务器的内存扩大1倍，系统效率就可以满足设计要求。”客户方项目负责人十分爽快地说:“好呀，好呀，给你们一周时间采购和部署，下周一我一定要看到一套健康、稳定、合格的系统。”项目经理说:“可是……新设备的采购费用呢？难道不需要新签一份合同吗？”客户一脸诧异地说:“合同？不是去年就签过了吗？费用？夏天我们就把款付给你们了！我们现在需要的是满足合同约定的系统。是不是要采购新设备，那是你们的事情，好像与我们无关吧？”很显然，国内许多设计师和程序员都有这样一种思维定式:计算机的处理速度越来越快，程序员不需要也不应当绞尽脑汁以提高代码的运行效率，而是应把更多的精力放在架构设计和过程管理方面；当业务量成倍增加时，程序员要做的第一件事不是优化代码，而是申请更多、更好的硬件设备。客观地说，这样的想法有一定的道理，但千万别把它绝对化。因为更加残酷的事实是，硬件的发展似乎总也无法满足新应用的增长需要。无论硬件速度多么惊人，总会有新的应用将CPU、内存、硬盘或是带宽资源消耗得一干二净——为了新版游戏而不断升级显卡的玩家对此一定深有体会。另一方面，项目经理在上海的遭遇也证明，如果你把所有希望都押在硬件括容上面，你一定会碰到被客户逼着自掏腰包的窘迫场面。其实，任何有算法或数学基础的程序员都很容易判断出，如果一套系统在2003年的典型硬件环境中无法处理每日20万页左右的报表数据，那么，该系统使用的算法几乎一定存在极大的改进空间。事实也的确如此，当我们的项目经理不得不潜下心来，仔细审读和调试源代码后，他很快就找到了两个要命的算法问题：为了简化设计，报表解析程序选用了更容易实现的多遍扫描和递归下降算法，而存储模块使用的索引文件也仅仅采用了最为简单的二叉有序树。那些天生对O(g(n))敏感的程序员一定可以找到许多有效的解决方法，我们的项目经理也不例外。在这里，我想说的只不过是:学习和掌握算法知识，这并不意味着程序员一定要亲自设计或实现特定的算法；但如果缺少这些知识，你可能会在面临一大堆可用算法的时候不知道该怎样择善而从。
一点声明 ——误会是这样产生的算法很重要，这一点毫无疑问。但必须严正声明的是:我从来都没有说过算法是程序设计领域里惟一重要的东西。对一个程序员来说，与算法同等重要的还有好几件事情，比如数学，比如英语，比如逻辑推理和判断能力，比如合作与沟通能力，比如语言和设计模式，比如……这些事情共同构成了程序员之所以能成为一gate职业的知识基础。如果一定要说几件不那么重要的事，我大概会说，一个具体的类库（比如Log4j），一项具体的技术（比如AJAX），一个具体的技巧（比如解决JavaScript的Closure问题），或是诸如此类的东西都是相对而言不那么重要的事情；因为一个基础过硬的程序员完全可以在两三周的时间内学通、学会它们中的任何一个——我知道这样的说法很容易产生误会，但我还是希望借此提醒更多的程序员深入思考相关问题。
一个常见错误——企业级应用必然排斥自主创新吗？不小心看到过这样一段文字:长期以来，国内的软件开发领域过分关注所谓“企业级开发”，导致了目前中国软件开发人员.对于算法基础越来越不重视，这势必造成软件产业发展缺乏创新的动力。因为自己此前做了将近八年的企业级应用开发，所以对这样的断言十分敏感:难道企业级应用一定会排斥自主创新吗？难道优秀的算法只能诞生在微软或是CMU吗？难道在中国程序员中占绝大多数的行业软件开发队伍就永远没有机会享受设计或实现顶尖算法的愉悦了吗？或者，换个角度考虑，即便国内软件开发人员不重视算法基础的事实的确存在，它与企业级开发之间存在必然的因果关系吗？据我所知，IBM是为世界各地提供企业级软件及服务最多的公司之一，即便在IBM专为企业而设计的应用软件（比如DB2 Content Manager）中，也隐藏着许许多多精妙的算法（比如工作流模块中的任务调度算法）。另一个真实的例子是，以前的一位同事负责过一个电信行业的系统集成项目。在项目早期，他简单地将Oracle，Crystal Report Server，Oracle ApplicationServer Portal等几种软件集成在一起，自己只开发了少量的存储过程和控制脚本就实现了所有功能。但随后他逐渐发现，这种简单集成的做法无法有效推广到其他类似的应用中。为提高软件的适应能力，他亲自编写了一个从多个异构系统中采集数据并重新包装、分发的小模块。就是为了更好地实现这样一个小巧的“数据粘接”模块，他几乎查阅和尝试了所有流行的数据归并和排序算法，以至于他在做完项目后骄傲地对我说：“现在如果让我回学校再考一次《数据结构》或是《算法导论》，准保95分！”我知道，国内有很多开发企业级应用的程序员每天多半是在Struts或Spring的框架里填写一些“模式化”的代码。他们也许会认为，自己的工作离算法很远很远，与其抓耳挠腮地研读算法源码，还不如在Hibernate大虾的Blog上多泡两个钟点。对此我想说的是:程序员的工作并没有高低贵贱之分，但如此多的程序员集中在简单应用中的事实却正好折射出中国软件产业的尴尬现状：是产业本身缺乏自主创新意识（或曰层次不高）造成了国内企业级软件开发的过度“简单化”和“蓝领化”，而不是企业级应用的存在影响了自主创新或是算法本身的生命力。我想，即便一时无法改变这样的现状，聪明的程序员仍然可以利用算法知识大幅提升自己的开发经验和设计水平。比如，同样是使用SQL Server+ASP.NET的组合，熟悉数据库的索引和查询机制，了解.NET中的对象调度和事务处理算法的程序员总是可以编出更加高效，更容易适应不同规模应用的程序来；再比如，尽管大多数人都可以把内存回收的重任交给Java或.NET环境提供的垃圾收集机制，但熟悉垃圾收集算法的程序员总能比较清楚地知道，自己编写的程序可能在什么样的情况下占用更多的内存，这样的内存消耗会不会成为系统的瓶颈之一。所以，即便你是一个从事企业级软件开发的程序员，你也应该对自己有足够的自信:每个人都有权利享受算法本身的乐趣，每个人都有权利参与到创新中来！
两种学习方法——你是数学家还是工程师？学习算法至少有两种方法，一种是数学家的方法，一种是工程师的方法。很可惜，很多人只知道第一种方法，对第二种方法几乎闻所未闻。以至于许多程序员一提“算法”或类似的字眼儿，就会皱起眉头说：“可恶！又是算法！数不清的公式，蜘蛛网一样的图示，烦都烦死了！”其实，对于很多只需要在实际应用领域使用某种算法的程序员来说，学习一种算法并不意味着你一定要懂得算法背后的数学原理，也不意味着你一定要背会若干公式和代码，我们完全可以用更加便捷也更加有效的方式学习复杂的算法。例如，数据结构或算法类教材讲到最短路径搜索算法时，总会先用有向图或无向图的知识精确定义最短路径问题，然后用集合或矩阵的术语详细描述Dijkstra算法、A*算法等常用的搜索算法。这样的教学形式很难对一个身处紧张工作中的程序员产生多大的吸引力。与此相反，在斯坦福大学博士生Amit Patel的个人主页上，我们可以找到一份更加适于工程师学习的最短路径搜索算法指南“Amit's Thoughts on Path-Finding andA-Star”（
http://theory.stanford.edu/~amitp/GameProgramming/）。在这份指南中，我们看不到晦涩的概念引入，找不到繁杂的数学证明。大家所能见到的只是一段段从实际应用（游戏）出发的，有趣而浅易的讲解，以及一幅幅描述搜索路径的，形象而明白的示意图。建议大家（无论对游戏编程是否有兴趣）都去看一看Amit的教程。最重要的不在于Amit教会了我们多少算法，而在于Amit很好地展示了学习算法的另一种有效途径——从实践出发的方法，或曰工程师的方法。给自己和自己从事的工作一个准确定位，然后寻找一种学习算法的最佳道路——我自己就一直是这么做的。用数学家的方法学习算法当然不错，如果有可能，我甚至愿意重新回到大学校园温习相关的数学和算法知识；但只要我还在从事具体的编程工作，只要我的需求重在使用算法而不是发明算法，我就会沿着属于工程师的道路一直走下去。
几句结束语◆ 算法很重要——但没有程序员本人更重要。◆ 算法很有用——这与你的工作类型关系不大。◆ 算法不难学——当然，这取决于你的学习态度和学习方法。◆ 希望和大家一起把算法学得好一些，再好一些——如果有时间的话。
