技术文章

(SCI) Parallel Algorithm for Wireless Data Compression and Encryption

(SCI) Fast Algorithm of Truncated BWT for Data Compression of Sensors

Dr. Qin Jiancheng

龙之梦助力肇庆教育网云计算

Dr. Zhou Yousheng

Dr. Bai Yuan

龙之梦工作室加盟华南理工学术团队

[软件下载] ComZip超级压缩机免费版下载

继续潜行，龙之梦工作室技术研发又一年

[软件交易] “雅典娜”网页密码锁在线购买

[软件交易] Super Prime超级质数机在线购买

[软件交易] ComZip超级压缩机在线购买

[信息安全] “风语者”高强度加密技术

[信息安全] 多层纵深防御体系结构

[合著] 专利：安全事件检测方法及装置

[原创] 利用计算机算法优化提高效益

[ 2007-04-08 13:34:37 ]
　　引言/提要：算法优化是提高效率的一种有效方法，如果使用得当，可以节约成本，提高效益。如果我们每个人在开发的过程中就时时注意算法优化，日积月累，可以节省大量的硬件投资，从而更多地体现出计算机技术的价值。

　　关键词：算法优化，核心技术，节省投资

　　现代社会信息化程度越来越高，计算机技术跟企业的关系密不可分，在运行维护、市场拓展及服务、新产品设计、新业务开发、业务管理等领域，计算机都已成为不可或缺的工具。
　　不过，并不是有了计算机这样的先进工具，就一定能够增强工作效率，提高企业效益。本文主要通过一些实例，论述如何利用计算机的算法优化来提高效益。而这种技术性的增效方法，需要一定的前提条件。
　　首先，计算机并非万能灵药，它不能解决企业的所有问题，而仅仅可以在某些方面提高效率，减轻员工的工作负担。其次，即使有计算机也未必能够提高效率，这跟许多因素有关。
　　计算机能否提高效益，关键在于对计算机的利用是否恰到好处。如果用得不恰当，非但不能得到提高效益的益处，反而有可能舍近求远，造成适得其反的效果。
　　在利用得当的前提下，使用计算机对提高效益所作的贡献大小，跟计算机算法的优劣直接相关。
　　软件是计算机的灵魂，没有软件的计算机硬件是无法创造价值的。而算法是软件的核心，一切代码、文档都是基于算法而写成。计算机系统能够达到怎样的效率，既取决于硬件性能的高低，也取决于软件算法的好坏。
　　无论是整个企业，还是企业中的每一项工作，其显性或隐性的效益，大致上可以按以下公式计算：
　　(1) 效益＝产出－投入
　　(2) 效率＝ (产出－投入) ÷ 投入 × 100％
　　(3) 效益＝效率 × 投入
　　由公式(1)可以看出，提高效益的途径，可以是减少投入，或者是增加产出。但这两者是相互矛盾的，通常情况下，减少投入意味着产出也减少，增加产出则同时拉动投入增加。这种矛盾很大程度上抵消了提高效益的成效。
　　由公式(3)可以看出，提高效率可以在不增加投入的情况下，使效益呈正比例增长。可见，提高效率是增加效益的一种有效途径。
　　具体到计算机的使用，为了使计算机达到某种工作要求，从而能够完成某项任务(产出)，当然需要一定的硬件、软件及人工成本(投入)。那么，这套计算机系统的价值(效益)，根据公式(1)，就等于完成任务的回报，减去所投入的成本。
　　少花钱，多办事，是企业获得效益的基本原则。要使计算机能够达到某种工作要求，可以从硬件和软件两个方面去考虑。前者通过购买性能更高的硬件，获得足够强的处理能力。后者通过算法优化，使软件本身的处理能力得到增强。
　　升级硬件，其实就是按照公式(1)，通过加大投入的方法去提高产出。由于硬件成本是一分钱一分货，这样做对效率的提高十分有限。
　　而软件算法优化，其实是按照公式(3)，通过提高效率的方法去提高效益。这种方法可能也要增加一定的人力成本投入，但得到的效率提高却会视乎情况而不同。好的情况下，算法优化可以得到指数级的速度增长；坏的情况下，也可以使速度提高一定的百分比。而通常情况下，软件算法优化总是能够比硬件升级节约更多的成本，而达到相同甚至更好的效果。
　　我在参加工作前，就已有超过10年的计算机竞赛生涯。在竞赛训练的过程中，掌握了不少算法优化的技术，也对优秀算法的意义有了深刻的体会。我参加工作后，这些技能在工作中发挥了相当大的作用。
　　以下几个实例，是我在工作中做过的项目，均通过优化算法的方式，达到了提高效益的目的。

　　一、银行代缴话费接口
　　我和另一同事合作用VC开发出来的银行代缴话费接口，在2000至2003年间承担了计费系统的银行缴费工作。全市每月数以千万元计的话费，绝大部分是通过银行接口缴纳的。承担这一重任的，只是4台普通PC机充当的服务器。而这套接口的软硬件系统，包括其上的程序，运行相当稳定，甚至超过了之后采用的省电信科研院银行接口的稳定性。整套系统，连接4家银行，软硬件投入合计不超过5万元。
　　与此相比的，是省电信科研院开发的银行缴费接口。据称，每个银行接口就要20万。速度上两者基本相同，甚至前者还要比电信科研院的略快。而前者用的是奔腾三CPU 550MHz、128MB内存的PC机，后者却是双奔腾四CPU 2.0GHz、1GB内存的专用PC服务器，硬件性能的差距决不可同日而语。
　　以弱胜强，这其中的差异，关键就在于算法。
　　事实上，银行缴费接口有相当强的性能需求，尤其是在每月的银行成批存折缴费的时候。全月超过一半的话费，在这个时候连续不断地通过接口缴纳，对缴费系统形成一种强大的压力。
　　在接口系统开发完成之初，算法未曾优化的时候，邮政储蓄几十万的话费帐户，需要连续6个晚上的时间，才能完成一轮批量缴费，不够及时。而及时缴费，是降低欠费率的一项关键措施。为此，提高成批缴费的速度，成为优化算法的首要要求。
　　我们分析了成批缴费的接口自动处理流程，找出其中的耗时之所在。结果发现，未优化过的成批缴费采用与现金实时缴费系统的流程，经过6个步骤：
　　1、银行发出查询信息至电信。(耗时t1)
　　2、电信查询数据库，看有无待缴话费。(耗时t2)
　　3、电信返回查询结果至银行。(耗时t3)
　　4、银行判断查询返回信息，如果有待缴话费，则查询数据库，看存折的余额是否够缴费。如果足够，则发出缴费信息至电信。(耗时t4)
　　5、电信在数据库进行缴费操作，将成功或失败的缴费结果返回至银行。(耗时t5)
　　6、银行收到缴费返回信息，如果成功则从存折中扣费。(耗时t6)
　　成批缴费时，这6个步骤反复循环执行，完成一轮就要循环几十万次。由于每个步骤都是顺序执行，因此每个循环的总耗时就是：
　　T1 = t1 + t2 + t3 + t4 + t5 + t6
　　经过分析，我们发现其实上述步骤可以简化，不需要等待那么长的时间。于是，我们创造性地采用了查询兼缴费的算法，将上述流程改写为3个步骤：
　　1、银行发出查询信息至电信，其中附带存折余额。(耗时t1)
　　2、电信查询数据库，看有无待缴话费。如果有，而且存折余额足够的话，进行缴费操作。将成功、失败、无待缴话费或者余额不足的信息，返回至银行。(耗时t5)
　　3、银行判断返回信息，如果是缴费成功，则从存折中扣费。(耗时t6)
　　出于保密的目的，银行方不需要发送存折的真实余额，只要金额值足够缴纳话费即可。
　　优化前后的流程之中，耗时t1基本上相等，t5、t6也是。这是我们根据经验判断而来，实际结果也证明了这一点。于是，改写流程后每个循环的总耗时就是：
　　T2 = t1 + t5 + t6
　　T2比T1少了t2、t3、t4的耗时，并且节省了一半的通讯带宽。结果，算法优化后的接口性能提高了一倍。邮政储蓄完成一轮批量缴费的时间，从6个晚上缩减到3个晚上，达到了及时缴费的要求。
　　事实上，我们还可以进一步去优化，将每个循环中的3个步骤从顺序执行变成流水作业，即A帐户执行步骤1的同时，B帐户执行步骤2，C帐户执行步骤3。这样可以将速度再提高2至3倍。不过，既然已经达到了及时性的要求，也就没有必要再投入人力去做进一步的算法优化。

　　二、市场部统计报表
　　市场部统计报表的各种综合数据指标，对制定市场策略，有针对性地开展业务所起到的指导作用，不言而喻。而现在的统计报表，早已不可能依靠人手计算，都需要借助计算机程序的自动功能。
　　统计报表的程序化早已实现，但并不足够。当企业产生的数据量迅速增长，需要的统计指标越来越多，越来越细的时候，当每月统计数据的人员守着计算机，等着程序一整天都还没有出结果，被人催促得心急如焚的时候，程序算法的优化就会显得尤为重要。
　　旧有的统计程序，虽然也是用效率较高的C语言，虽然直接用Alpha小型机来进行统计，但速度仍然跟不上。2002年新的统计报表格式出台后，旧程序功能上已经无法满足要求。即使在上面增加功能，1个月的报表用12个小时都算不完。因此，我和同事用C语言全新开发了统计程序，采用优化的算法来运行。
　　优化算法，需要综合考虑软硬件因素和数据本身的特点。1千条数据的统计，和1千亿条数据的统计不可同日而语，一做起大数据量的运算来，算法的优劣就会有明显的体现。算法的改进对速度的提高，可以是几何级以至指数级的。
　　我们开发出来的新统计程序，采用了优化的算法，统计时间从12小时以上，缩短到1个小时左右，速度提高了一个数量级。
　　新程序也采用C语言，运行在单CPU奔腾三500MHz、512MB内存的PC机上，性能比不上双CPU Alpha 600MHz、2GB内存的小型机。速度能有如此的提高，这就是优化算法的力量。
　　算法的优化，紧扣PC机的特点。
　　首先，程序不直接连接庞大的计费数据库，而是把需要的数据一次性提取出来，以文件形式保存在PC机上。这种从数据库提取记录的方式花费的时间较少，并且大量清单文件无须经过数据库存放，节省了SQL语句编译、数据库检索的时间。不要小看了这些消耗的时间，如果每条记录多消耗千分之一秒的时间，1千万条记录就要多耗掉1万秒。
　　其次，程序简化了纷繁复杂的统计过程，使每个数据文件只需要扫描1次。这是提高速度的重要手段，因为需要统计的数据量庞大，以GB计，多扫描1次，需要的时间就会成倍增加。而统计报表有数百个指标，相当复杂，要在1次扫描中计算出全部结果，没有好的算法是做不到的。
　　最后，程序算法配合PC机的硬件特点，充分发挥出它的性能。纯理论上的优化算法，未必能够提高速度，或者提高得不彻底。而结合了硬件特点之后，速度还能进一步翻倍。
　　现代PC机的特点，一个是内存较大。内存大，就可以存放大量数据，尤其是频繁使用的数据。统计用的计算机有512M内存，容纳所有7位电话号码的用户性质，总共1千万个号码的数据，还绰绰有余，根本不需要考虑空号码占用多余的空间。因此，采用简单的线性数组访问方式，比散列法、索引法等紧缩空间式的访问，来得更直接，速度也更快。
　　现代PC机的另一个特点，是CPU主频较高，流水线长。这就意味着，顺序执行的效率高，而程序分支对速度的影响相当大，因为分支跳转意味着流水线内部的指令损失。为此，程序中要尽量避免使用条件分支。
　　有不少可行的方法，能代替条件分支。例如，当变量A的值只能是0或1时，可以把条件语句：
　　“若A为1则B=C，否则B=0。”
　　直接改写成：
　　“B=C*A”
　　同样的，统计程序中每条记录的用户分类，都需要进行多重条件判断，相当耗时。我们用矩阵代替了多重条件判断，通过直接访问矩阵来获取结果。这样，多步复杂的条件运算就简化为一步直接的内存访问，这部分关键程序就变成了顺序执行，使PC机得以全速计算。

　　三、绩效考核后台支撑系统
　　在省电信科研院开发客户营销管理系统(过渡版)之前，我和同事已经开发了一套功能类似的绩效考核后台支撑系统。这套系统以ASP开发，后台采用旧的Oracle 8数据库，以Web方式提供了计费帐单、九七业务、欠费、其他运营商业务等方面的查询功能。员工可以用浏览器查询到自己承包电话的总话费、ARPU值、欠费额、欠费率、流失率、离网率等指标，以及详细记录并排序。
　　由于选用了个性化配置的PC服务器，整套系统软硬件投入只不过6万元。数据库及ASP程序都经过精心设计，系统运行快速稳定，有力地支持了企业的绩效营销管理。
　　据说电信科研院的客户营销管理系统，每个点要投入15万，20个点就需要300万元。这两套系统在功能上差距较远，不具有可比性，但至少可以证明，要用计算机实现营销指导和绩效考核的工作，未必需要巨大的投入。在2002年306大会战中，这套绩效考核后台支撑系统就为前线人员提供了竞争对手业务的详细情报，为全市完成3亿多元收入提供了有价值的信息。
　　这套系统从硬件选型开始，就立足于节约成本，尽量强大的原则，软硬件结合，努力要让优化算法的性能得到最大限度的发挥。
　　由于系统要用到数据仓库，特意将内存扩充到2GB。内存容量的大小，对数据仓库的性能有至关重要的作用。
　　磁盘采用4个15000转，4MB缓存的SCSI硬盘，并且要组成磁盘阵列，以进一步提高性能。在选用何种RAID的时候，我们没有按通常的做法选用RAID5，而是认真比较了几种RAID的算法，挑选其中性能最好的一种。结果，我们发现RAID0+1是性能最好的。
　　RAID0+1由于采用了并行和镜像阵列，读写速度都相当快。而RAID5采取每4个数据块加1个校验块的形式，校验运算影响了性能。因此，我们选择了牺牲一定容量，使用性能最好的RAID0+1。
　　CPU选用两个奔腾四至强1.8GHz，超线程算法将它们虚拟成4个并行执行的CPU，高达2MB的三级缓存，对大数据量运算的性能有着至关重要的影响。
　　数据库优化方面，除了启用多线程，开辟尽量大的内存作为缓存，并使用大块数据块以提高大量数据查询性能之外，又特意增大了用来存放散列表、索引及进行排序的区域，努力使查询能够在最短的时间内完成。
　　至于程序的算法，更是影响性能的重中之重。我们对数据表结构进行了精心设计，努力使关键性的查询性能得到优化。让每个大数据量查询都有最有效的索引，让表连接不超过两个表，让关键性的表都不超过4个字段，等等，都是精心设计的成果。
　　我们采用最简单、最直接的工号对应电话号码表，解决了各人承包电话的问题，也因为简洁而表现出较高的性能。
　　由于是Web应用，无论数据库操作是否完成，都必须在1分钟之内作出响应，否则浏览器会超时出错。为此，我们在程序中引入了进度条机制。对于长时间的数据库操作，每隔半分钟就更新一次进度条，从而避免了超时出错的问题。同时，进度条也使人在主观上感觉到程序在运行，速度不慢。

　　四、近期算法优化展望
　　上述三个示例，是我做过的算法优化工作的一部分。有机会的话，我还会做更多这方面的优化工作。我已经有了一些新的思路，近期之内可能会进行以下优化：
　　1、客户资料整理。
　　我们先通过用户名进行自动的客户归并，再进行人工的细化。自动归并的工作由计算机完成，可以通过用户名的模糊匹配来实现。即：对用户名字符串按一定的算法进行相似度的计算，当相似度超过给定的阀值(例如90%)时，则认为两者匹配。
　　对所有用户两两进行模糊匹配，尽量放在内存中进行，预先对用户名进行排序，并且通过一些特征值的比较来减轻匹配的工作量，这样可以大大提高匹配运算的性能。
　　2、KPI成绩的标准分计算。
　　绩效考核KPI成绩由于跟奖金挂钩，除了按现在的算法计算出原始分之外，还可以参照高考标准分的算法，将原始分折算成标准分。标准分即排名分，符合人群的高斯正态分布规律(中间的人多，两端的人少)，用来计算奖金有一定的科学性。
　　以下算法仅供参考：假设人均奖金500元，最高奖金900元，最低100元。由原始分计算出排名，第一名900元，有1人，同时最后一名100元，有1人。第二名899元，有2人，同时倒数第二名101元，有2人。依此类推，整个分布形成高斯曲线，其中500元的人最多。
　　该算法只要根据总人数进行一次计算，形成高斯曲线，以后就可以直接按名次对号入座，得出相应的标准分。技术上并没有什么问题，问题在于这种标准分的计算方法是否适合我们的实际情况。

　　综上所述，算法优化是提高效率的一种有效方法，如果使用得当，可以节约成本，提高效益。这固然需要一定的技术水平和经验积累，但也绝不是非常困难的事情。如果我们每个人在开发的过程中就时时注意算法优化，日积月累，可以节省大量的硬件投资，从而更多地体现出计算机技术的价值。

参考文献：
1. 楚屏、陈慧南《数据结构》，人民邮电出版社，1994年
2. 严慧敏、吴伟民《数据结构》，清华大学出版社，1987年
3. 王玉孝、姜炳麟、王友仁《概率论、随机过程与数理统计》，电子工业出版社，1993年

龙之梦
2003.10.22