很多人可能是好莱坞大片看多了，以为计算机神通广大，但事实不是这样的。计算机其实是一种很傻的工具，傻到几乎没有智商（至少目前是这样）。它可以连续几年做同一件事情而毫无怨言，但是如果你不告诉它怎么做，它什么事情也不会做。最有创造性的活动其实是由一种被称为“程序员”的人做的，计算机做的只不过是人类不愿意做的体力活而已。比如图像识别技术，需要一个字节一个字节地处理数据，提取数据的特征值，然后在海量的数据中比较、匹配这些特征值，直到累得两眼昏花，人类才不会干这种傻事儿呢。计算机愿意做，但前提是你要告诉它怎么做。算法可以理解为这样一种技术，它将告诉计算机怎么做。有人将编程理解为搭积木，直接用别人开发好的组件、库，甚至是类或API就行了，并且美其名曰“不用重复发明轮子”。我认为这其实就是所谓的系统集成，如果一个程序员每天的工作就是搭积木，那将是令人十分羡慕的事情，但是我知道，事实并不是这样的。这样搭积木式的编程计算机就可以做，没有必要让人来做，因为人工的成本高于计算机。我遇到的更多的是在论坛里发帖求助的人，比如“求代码，把一个固定格式的文本文件读入内存”，再比如“谁能帮我把这个结构数组排排序啊，书上的例子都是整数数组排序”。他们是如此地无助，如果不是论坛对回帖有积分奖励的话，恐怕不会有人理他们。 我要说的是，大多数程序员并不需要知道各种专业领域里的算法，但是你要会设计能够解决你面临问题的算法。一些领域内的经典问题，在前人的努力之下都有了高效的算法实现，本书的很多章节都介绍了这样的算法，比如稳定匹配问题，比如A*算法，等等。但是更多情况下，你所面临的问题并没有现成的算法实现，需要程序员具有创新的精神。算法设计需要具备很好的数学基础，但数学并不是唯一需要的知识，计算机技术的一些基础学科（比如数据结构）也是必需的知识，有人说：程序＝算法+数据结构，这个虽然不完全正确，但是提到了计算机程序最重要的两点，那就是算法和数据结构。算法和数据结构永远是紧密联系在一起的，算法可以理解为解决问题的思想，这是程序中最具有创造性的部分，也是一个程序有别于另一个程序的关键点，而数据结构就是这种思想的载体。 再次重申一遍，我和大多数人一样，并不是要求每个程序员都精通各种算法。大多数程序员可能在整个职业生涯中都不会遇到像ACM（Association for Computing Machinery）组织的国际大学生程序设计竞赛中的问题，但是说用不到数据结构和算法则是不可想象的。说数据结构和算法没用的人是因为他们用不到，用不到的原因是他们想不到，而想不到的原因是他们不会。请息怒，我不是要打击任何人，很多情况下确实是因为不会，所以才用不到，下面就是一个典型的例子。 1.2.1 一个队列引发的惨案 我所在的团队负责一款光接入网产品的“EPON业务管理模块”的开发和维护工作，这是电信级的网络设备，因此对各方面性能的要求都非常高。有一天，一个负责集成测试的小伙儿跑过来对我说，今天的每日构造版本出现异常，所有线卡（承载数据业务的板卡）的上线时间比昨天的版本慢了4分钟左右。我很惊讶，对于一个电信级网络设备来说，每次加电后的线卡上线时间就是业务恢复时间，业务恢复时间这么慢是不能接受的。于是我检查了一下前一天的代码入库记录，很快就找到了问题所在。原来当前版本的任务列表中有这样一项功能，那就是记录线卡的数据变更日志，需求的描述是在线卡上维护一个日志缓冲区，每当有用户操作造成数据变更时，就记录一条变更信息，线卡上线时的批量数据同步也属于操作数据变更，也要计入日志。因为是嵌入式设备，线卡上日志缓冲区的大小受限制，最多只能存储1000条记录，当记录的日志超过1000条时，新增的日志记录将覆盖旧的记录，也就是说，这个日志缓冲区只保留最近写入的1000条记录。一个新来的小伙儿接受了这个任务，并在前一天下班前将代码签入库中（程序员要记住啊，一定不要在临下班前签入代码）。他的实现方案大致是这样的（注释是我加上的）： #define SYNC_LOG_CNT 1000 #define SYNC_LOG_MEMOVER_CNT 50 typedef struct { INT32U logCnt; EPON_SYNC_LOG_DATA syncLogs[SYNC_LOG_CNT]; }EPON_SYNC_LOG; EPON_SYNC_LOG s_EponSyncLog; void Epon_Sync_Log_Add(EPON_SYNC_LOG_DATA*pLogData) { INT32U i = 0; INT32U syncLogCnt = 0; syncLogCnt = s_EponSyncLog.logCnt; if(syncLogCnt>=SYNC_LOG_CNT) { /*缓冲区已满，向前移动950条记录，为新纪录腾出50条记录的空间*/ memmove(s_EponSyncLog.syncLogs, s_EponSyncLog.syncLogs + SYNC_LOG_MEMOVER_CNT, (SYNC_LOG_CNT-SYNC_LOG_MEMOVER_CNT) * sizeof(EPON_SYNC_LOG_DATA)); /*清空新腾出来的空间*/ memset(s_EponSyncLog.syncLogs + (SYNC_LOG_CNT - SYNC_LOG_MEMOVER_CNT), 0, SYNC_LOG_MEMOVER_CNT * sizeof(EPON_SYNC_LOG_DATA)); /*写入当前一条日志*/ memmove(s_EponSyncLog.syncLogs + (SYNC_LOG_CNT - SYNC_LOG_MEMOVER_CNT), pLogData, sizeof(EPON_SYNC_LOG_DATA)); s_EponSyncLog.logCnt = SYNC_LOG_CNT - SYNC_LOG_MEMOVER_CNT + 1; return; } /*如果缓冲区有空间，则直接写入当前一条记录*/ memmove(s_EponSyncLog.syncLogs + syncLogCnt, pLogData, sizeof(EPON_SYNC_LOG_DATA)); s_EponSyncLog.logCnt++; } 这个方案使用一个长度为1000条记录的数组存储日志，用一个计数器记录当前写入的有效日志条数，数据结构的设计中规中矩，但是当缓冲区满，需要覆盖旧记录时遇到了麻烦，因为每次都要移动数组中的前999条记录，才能为新记录腾出空间，这将使Epon_Sync_Log_Add()函数的性能急剧恶化。考虑到这一点，小伙儿为他的方案设计了一个阈值，就是SYNC_LOG_MEMOVER_CNT常量定义的50。当缓冲区满的时候，就一次性向前移动950条记录，腾出50条记录的空间，避免了每新增一条记录就要移动全部数据的情况。可见这个小伙儿还是动了一番脑子的，在Epon_Sync_Log_Add()函数调用不是很频繁的情况下，在功能和性能之间做了个折中，根据自测的情况，他觉得还可以，于是就在下班前匆匆签入代码，没有来得及安排代码走查和同行评审。但是他没有考虑到线卡上线时需要批量同步数据的情况，在这种情况下，Epon_Sync_Log_Add()函数被调用的频度仍然超出了这个阈值所能容忍的程度。通过对任务的性能进行分析，我们发现大量的时间都花费在Epon_Sync_Log_Add()函数中移动记录的操作上，即便是设计了阈值SYNC_LOG_MEMOVER_CNT，性能依然很差。 其实，类似这样的固定长度缓冲区的读写，环形队列通常是最好的选择。下面我们来看一下环形队列的示意图，如图1-1所示。 计算机内存中没有环形结构，因此环形队列都是用线性表来实现的，当数据指针到达线性表的尾部时，就将它转到0位置重新开始。实际编程的时候，也不需要每次都判断数据指针是否到达线性表的尾部，通常用取模运算对此做一致性处理。设模拟环形队列的线性表的长度是N，队头指针为head，队尾指针为tail，则每增加一条记录，就可用以下方法计算新的队尾指针： tail = (tail + 1) % N 对于本例的功能需求，当tail + 1等于head的时候，说明队列已满，此时只需将head指针向前移动一位，就可以在tail位置写入新的记录。使用环形队列，可以避免移动记录操作，本节开始时提到的性能问题就迎刃而解了。在这里，套用一句广告词：“没有做不到，只有想不到。”看看，我没说错吧？ 1.2.2 我的第一个算法 我的第一份工作是为一个光栅图像矢量化软件编写一个图像预处理系统，这套光栅图像矢量化软件能够将从纸质工程图纸扫描得到的位图图纸识别成能被各种CAD软件处理的矢量化图形文件。在预处理系统中有一个功能是对已经二值化的光栅位图（黑白两色位图）进行污点消除。光栅位图上的污点可能是原始图纸上扫描前就存在的墨点，也可能是扫描仪引入的噪点，这些污点会对矢量化识别过程产生影响，会识别出错误的图形和符号，因此需要预先消除这些污点。 当时我不知道有小波算法，也不知道还有各种图像滤波算法，只是根据对问题的认识，给出了我的解决方案。首先我观察图纸文件，像直线、圆和弧线这样有意义的图形都是最少有5个点相互连在一起构成的，而污点一般都不会超过5个点连在一起（较大的污点都用其他的方法除掉了）。因此我给出了污点的定义：如果一个点周围与之相连的点的总数小于5，则这几个相连在一起的点就是一个污点。根据这个定义，我给出了我的算法：从位图的第一个点开始搜索，如果这个点是1（1表示黑色，是图纸上的点；0表示白色，是图纸背景颜色），就将相连点计数器加1，然后继续向这个点相连的8个方向分别搜索，如果某个方向上的相邻点是0就停止这个方向的搜索。如果搜索到的相连点超过4个，说明这个点是某个图形上的点，就退出这个点的搜索。如果搜索完成后得到的相连的点小于或等于4个，就说明这个点是一个污点，需要将其颜色置为0（清除污点）。 算法实现首先定义搜索过程中存储相连点信息的数据结构，这个数据结构定义如下： typedef struct tagRESULT { POINT pts[MAX_DIRTY_POINT];/*记录搜索过的前5个点的位置*/ int count; }RESULT; 这个数据结构有两个属性，count是搜索过程中发现的相连点的个数，pts是记录这些相连点位置的线性表。记录这些点的位置是为了在搜索结束后，如果判定这些点是污点，可以利用这些记录的位置信息直接清除这些点的颜色。 /*8个方向*/ POINT dir[] = { {-1, 0}, {-1, -1}, {0, -1}, {1, -1}, {1, 0}, {1, 1}, {0, 1}, {-1, 1} }; void SearchDirty(char bmp[MAX_BMP_WIDTH][MAX_BMP_HEIGHT] int x, int y, RESULT *result) { for(int i = 0; i < sizeof(dir)/sizeof(dir[0]); i++) { int nx = x + dir[i].x; int ny = y + dir[i].y; if( (nx >= 0 && nx < MAX_BMP_WIDTH) && (ny >= 0 && nx < MAX_BMP_HEIGHT) && (bmp[nx][ny] == 1) ) { if(result->count < MAX_DIRTY_POINT) { /*记录前MAX_DIRTY_POINT个点的位置*/ result->pts[result->count].x = nx; result->pts[result->count].x = ny; } result->count++; if(result->count > MAX_DIRTY_POINT) break; SearchDirty(bmp, nx, ny, result); } } } 向8个方向搜索使用了预置的矢量数组dir，这是迷宫或棋盘类游戏搜索惯用的模式，本书介绍的算法会多次使用这种模式。SearchDirty()函数递归地调用自己，实现对8个方向的连通性搜索，最后的结果存在result中，如果count的个数大于4，说明[x, y]位置的点是正常图形上的点，如果count的个数小于或等于4，则说明[x, y]位置相邻的这个点是一个污点。污点相邻的点的位置都被记录在pts中，将这些位置的位图数据置0就消除了污点。算法没有做任何优化，不过好在图纸上大部分都是白色背景，需要搜索的点并不多。打开测试图纸一试，速度并不慢，效果也很好，几个故意点上去做测试用的污点都没有了，小的噪点也没有了，图纸一下就变白了。不过这段代码最终并没有成为那个软件的一部分，学过机械制图的同学可能看出来了，这个算法会将一些细小的虚线和点划线一并干掉。 这是一个微不足道的问题，但却是我第一次为解决（当然，未遂）问题而设计了一个算法，并最终用程序将其实现。它让我领悟到了一个道理，软件被编写出来就是为了解决问题的，程序员的任务就是设计解决这些问题的算法。成功固然高兴，失败也没有什么代价，可以随时卷土重来。不要小看这些事情，不要以为只有各种专业领域的程序才会用到算法，每一个微小的设计都是算法创造性的体现，即使失败，也比放弃强。