《那些年啊，那些事——一个程序员的奋斗史》——51

     本以为英汉字典的程序已经没有什么大问题了，没想到今天段伏枥想查一个单词，却发现事情根本就不是自己所料想的那么顺利：单词的查找速度太慢！这就奇怪了，之前为什么没有发现呢？说起来也让人啼笑皆非。之前之所以没发现这问题，是因为测试的时候，输入的单词都是以“a”开头的，而今天碰巧要查找的单词，却是以“x”开头！就这么一个小差别，导致搜索所花的时间居然要比“a”开头的字母多两分钟！         这也是没有办法的事，因为段伏枥的查找算法，是最最最原始的：从“a”开始，一个一个进行对比，看看哪个单词最符合。换句话来说，如果单词不存在，或是位于字库的后半部分，那么搜索所花费的时间绝对是让人咋舌的。其实一开始写查找算法的时候，段伏枥也担心过这个问题，但没想到的是，当自己将程序写完之后，居然把这码子事给忘了；并且测试的时候，都是以“a”开头，那搜索的速度自然是超快，更让段伏枥完全淡忘了这问题。         怎么办？这样的效率，搁谁身上都受不了啊。总不能查一个“a”开头的单词不到十秒钟，但找个“z”开头的，撒了泡尿回来泡了杯茶后还没结束吧？没辙，修改算法呗。算法？段伏枥一想到这两个词，脑袋就变成两个大。对于高考150分满分只考了60分，看到傅里叶变化就两眼冒金星的段伏枥来说，让他去折腾算法无异于慢性折磨。         这带来一个很有意思的话题：程序员究竟要不要研究算法？其实这在业界中也是一直争论不休。正方的意见是，不懂得算法，那么就不能更好的理解计算机，写出的软件效率就会非常低，因为程序就是代码+算法的结合；而反方的意见呢，无非就是说现在有很多算法库，可以直接拿来就用，根本就不必要去深究，不必要再花费心思去研究轮子如何工作。关于是否需要专研算法的问题，段伏枥没有丝毫的犹豫，义不容辞直接选择反方，这倒不是因为他多么的高瞻远瞩，或是有什么坚定的信仰之类，纯粹是因为他先天不足：从小对数学就不感冒，看着这变化来变化去的公式就头晕，这模样还怎能研究算法？         话又说回来，程序员要不要学算法，这的确要分开两个方面来看，不能一概而论。比如说，如果要到谷歌或百度这样的公司，因为他们是以算法优势起家的，如果你不研究算法，对算法一窍不通，那么进去最多就是打打酱油，说不定哪天主管心情不好了，还会请吃鱿鱼。但如果是到一些主要是做产品的公司，你天天研究算法也不行啊：产品的界面，客户的体验等等杂七杂八都需要你去完善，可你偏偏在研究什么样的算法效率会高一点点，而这些却偏偏是客户无法直观感受到的，那么估计炒鱿鱼这道菜还是免不了的。         盲目崇拜，或是盲目鄙视算法，这两种态度都是不可取的，关键是看自己用算法来做什么。就像一辆法拉利跑车，估计没有人会说它差，开着它在路上狂奔，估计是一个非常惬意的享受。可是如果任务是要从大陆到日本，需要越过海洋，那么这法拉利的价值估计还不如一艘破船。可是这时候，你能说法拉利一无是处吗？一无是处的是使用者，因为他没有将法拉利用在最恰当的场合。算法也是如此，它是否有用，能发挥多大的作用，关键是看用它的人，看用它的场合。         根据对算法的掌握程度，大体上可以将程序员分为三类：第一种是对算法非常精通的，第二种是知道有哪么些算法概念知道相应的算法库该如何使用的，最后一种是对算法一窍不通甚至连算法库都不知道的。这三种人之中，第一种是神一样的人物，适合于从事提升产品竞争力的工作；第二种便是大多数程序员所处的范围，适合产品的应用开发；最后一种嘛，便是菜鸟级别的，遇到和算法有关的问题只能撞得头破血流。很不幸，段伏枥就属于最后一种。         当然，现在是菜鸟，并不代表一无是处，高手嘛，不也是从雏鸟开始的？俺就不信，那些算法高手，在娘胎的时候就懂得傅里叶变换？只听过用柔和的音乐来进行胎教的，可还真没听过念数学公式来进行的。绝对不向困难低头，是段伏枥一贯坚持的信念，也是一直能够进步的原因之一。不就个算法嘛？这还难得了俺？拿本算法书看看不就好了。确实是拿本算法书看看，很多不明白的东西都清晰了，可这也要能看得懂啊。没翻几页，段伏枥就翻白眼了：这是哪门子的邪门歪道？中文每个文字都能看懂，字母才26个字母，可组合起来，咋就跟天书一样了呢？还有还有，这算法的评判标准也太麻烦了吧？不同情况下的表现形式还不同啊？这不折腾老子吗？         算了，管它那么多，还什么算法优劣呢！以自己现在的水平，等研究出来，估计到时候公司在不在还不好说。不用去想那么复杂了，那是不是自己这个水平档次的人所能干的事。自己只要算法比以前的那个逐个逐个比较要快，每个单词查找的时间差不多就行了。         只是，要选哪个呢？这些英文在的排列是按顺序的，如果以二分法的话，直觉上应该可以快很多；并且这二分法的特性，对于已经排序的单词来说，查找的频度应该相差无几。好，那就是它了！就是二分法！其实，如果不选二分法，那也没有其它的选择了，因为对于段伏枥来说，只有这二分法他还能看得懂，还能够比较容易地转化为代码。         因为之前的单词搜索是在DLL文件中，所以要更改算法的话，只需要更改DLL的源文件即可。不仅如此，之前的算法暴露的是一个函数接口，现在只需要更改函数体的内容，而不必重新书写代码。虽然当时段伏枥写程序的时候，并没有考虑到后续可能需要更改算法的状况，但凭借着直觉，觉得有一些东西应该以函数形式封装起来，没想到这给后续的修改省去了不少麻烦。         英文单词是以数组来存储的，如果要更改算法，只需要增加三个指针，分别指向开头，末尾，和中间的序号，然后再和所要查找的单词做比较即可。算法转换为代码，并不是很困难的事，但有一些小细节却需要注意，所以段伏枥花了整整一天时间，才让这算法正常工作。过程是曲折的，但结果是喜人的，这么一更改之后，搜索后半部单词的速度确实比之前要快很多，简直完全是天壤之别。看着改善后的英汉字典程序，段伏枥不禁手舞足蹈：自己终于也能写字典程序了！当年老章所做的事情，自己也能做了！更为重要的是，一向对算法白痴的自己，居然还懂得写了个二分法算法！还有什么能比这更高兴的吗？         只不过当时的段伏枥不知道，如果要写像他现在这种档次要求的字典程序，完全可以不用这么麻烦：不用去考虑如何存储字典数据，不用考虑如何根据返回值查找注释，不用花费心思去考虑查找算法——因为这一切，只需要使用STL的multimap即可解决。multimap的结构很简单，是以key-value的方式存储。如果应用到英汉字典，那么key存储的就是英文单词，而value自然就是注释了。一旦需要查询的时候，那也是非常简单，直接调用find函数即可。那么这STL的效率如何呢？只能说，STL的算法可能并不是最佳的，但绝对不是最差的，不过对于段伏枥的应用而言，完全是绰绰有余。         虽然段伏枥在《C++ primer》见过multimap的身影，但该书对于应用却惜字如金，并没有很好诠释用法。所以段伏枥对此的印象也不是很深，在编写程序的时候自然没有想到使用该容器。如果在此之前段伏枥看过《C++ 标准程序库》的话，可能情形截然不同。该书从最基础开始，给读者介绍了STL的使用，特别是其中的一章，更是以字典为例来进行讲解如何使用multimap，恰好和段伏枥的程序要求不谋而合。         这不能不说，多看书，对于程序员而言，是多么重要。也许看的时候确实一窍不通，但只要你对此有了那么点印象，知道有那么一回事，说不定就这么一个灵感，会让以后的工作省掉很多的麻烦。