• <legend id="z1gx4"></legend>
      1. <em id="z1gx4"><ruby id="z1gx4"><u id="z1gx4"></u></ruby></em><li id="z1gx4"><acronym id="z1gx4"></acronym></li>
        <span id="z1gx4"></span>

        专业解读

        程序员与算法的羁绊,是几世以前就定下的

        专业解读 admin 306℃

        程序员

        与算法

        本章的标题既然是“程序员与算法”,就必然要涉及一个基本问题,那就是“程序员是否必须会算法”。

        这是一个充满争议的问题,虽然并不像“生存还是毁灭”之类的选择那样艰难而沉重,但也绝不是一个轻松的话题。

        朋友们在我的“算法系列”博客专栏上发表的评论和回复,并不都是我所期待的赞美和鼓励,也常常会有一些冷言冷语。比如,“穷举也算是算法吗”或者“请你说明一下算法在 XX 系统中能起到什么作用”。

        有一次,一个网友通过邮件问我:“你写的都是小儿科的东西,几十行代码就能搞定,能不能整一点高深的算法?”我反问他什么是他所理解的高深的算法,他答复说:“像遗传算法、蚁群算法之类的。”

        于是我给了他一个遗传算法求解0-1背包问题的例子(参见第16章),并告诉他,这也就是几十行代码的算法,怎么理解成是高深的算法?他刚开始不承认这是遗传算法,直到我给了他 Denis Cormier 公开在北卡罗来纳州立大学服务器上的遗传算法的源代码后,他才相信他一直认为深不可测的遗传算法的原理原来是这么简单。

        还有一个网友直言我写的“用三个水桶等分8升水”之类的问题根本就称不上算法,他认为像“深蓝”那样的人工智能才算是算法。我告诉他计算机下棋的基本理论就是博弈树,或者再加一个专家系统。但是他认为博弈树也是很高深的算法,于是我给了他一个井字棋游戏(参见第23章),并告诉他,这就是博弈树搜索算法,非常智能,你绝对战胜不了它(因为井字棋游戏很简单,这个算法会把所有的状态都搜索完)。我相信他一定很震惊,因为这个算法也不超过100行代码。

        对于上面提到的例子,我觉得主要原因在于大家对算法的理解有差异,很多人对算法的理解太片面,很多人觉得只有名字里包含“XX 算法”之类的东西才是算法。

        而我认为算法的本质是解决问题,只要是能解决问题的代码就是算法。在讨论程序员与算法这个问题之前,我们先探讨一个最基本的问题:什么是算法。

        什么是算法

        《算法导论》一书将算法(algorithm)描述为定义良好的计算过程,它取一个或一组值作为输入,并产生一个或一组值作为输出。Knuth 在《计算机程序设计艺术》一书中将算法描述为从一个步骤开始,按照既定的顺序执行完所有的步骤,最终结束(得到结果)的一个过程。Weiss 在《数据结构与算法分析》一书中将算法描述为一系列的计算步骤,将输入数据转换成输出的结果。

        虽然没有被普遍接受的“算法”的正式定义,但是各种著作中对算法的基本要素或基本特征的定义都是明确的,Knuth 总结了算法的四大特征。

        确定性。算法的每个步骤都是明确的,对结果的预期也是确定的。

        有穷性。算法必须是由有限个步骤组成的过程,步骤的数量可能是几个,也可能是几百万个,但是必须有一个确定的结束条件。

        可行性。一般来说,我们期望算法最后得出的是正确的结果,这意味着算法中的每一个步骤都是可行的。只要有一个步骤不可行,算法就是失败的,或者不能被称为某种算法。

        输入和输出。算法总是要解决特定的问题,问题来源就是算法的输入,期望的结果就是算法的输出。没有输入的算法是没有意义的,没有输出的算法是没有用的。

        算法需要一定的数学基础,但是没有任何文献资料将算法限定于只解决数学问题。

        设计模式

        算法需要一定的数学基础,但是没有任何文献资料将算法限定于只解决数学问题。

        有些人将贪婪法、分治法、动态规划法、线性规划法、搜索和枚举(包括穷尽枚举)等方法理解为算法,其实这些只是设计算法常用的设计模式(Knuth 称之为设计范式)。

        实现方法

        同样,计算机程序只是算法的一种存在形式,伪代码、流程图、各种符号和控制表格也是常见的算法展示形式。而顺序执行、并行执行(包括分布式计算)、递归方法和迭代方法则是常用的算法实现方法。

        综上定义

        综合以上分析和引述,本人将算法定义为:算法是为解决一个特定的问题而精心设计的一套数学模型以及在这套数学模型上的一系列操作步骤,这些操作步骤将问题描述的输入数据逐步处理、转换,并最后得到一个确定的结果。

        使用“精心设计”一词,是因为我将算法的设计过程理解为人类头脑中知识、经验激烈碰撞的过程,将算法理解为最终“小宇宙爆发”一般得到的智力结果。

        程序员必须要会算法吗?

        很多人可能是好莱坞大片看多了,以为计算机神通广大,但事实不是这样的。计算机其实是一种很傻的工具,傻到几乎没有智商(至少目前是这样)。

        它可以连续几年做同一件事情而毫无怨言,但是如果你不告诉它怎么做,它什么事情也不会做。最有创造性的活动其实是由一种被称为“程序员”的人做的,计算机做的只不过是人类不愿意做的体力活而已。

        比如图像识别技术,需要一个字节一个字节地处理数据,提取数据的特征值,然后在海量的数据中比较、匹配这些特征值,直到累得两眼昏花,人类才不会干这种傻事儿呢。计算机愿意做,但前提是你要告诉它怎么做。

        算法可以理解为这样一种技术,它将告诉计算机怎么做。

        有人将编程理解为搭积木,直接用别人开发好的组件、库,甚至是类或 API 就行了,并且美其名曰“不用重复发明轮子”。

        我认为这其实就是所谓的系统集成,如果一个程序员每天的工作就是搭积木,那将是令人十分羡慕的事情,但是我知道,事实并不是这样的。这样搭积木式的编程计算机就可以做,没有必要让人来做,因为人工的成本高于计算机。

        我遇到的更多的是在论坛里发帖求助的人,比如“求代码,把一个固定格式的文本文件读入内存”,再比如“谁能帮我把这个结构数组排排序啊,书上的例子都是整数数组排序”。

        他们是如此地无助,如果不是论坛对回帖有积分奖励的话,恐怕不会有人理他们。

        我想说的

        大多数程序员并不需要知道各种专业领域里的算法,但是你要会设计能够解决你面临问题的算法。

        一些领域内的经典问题,在前人的努力之下都有了高效的算法实现,本书的很多章节都介绍了这样的算法,比如稳定匹配问题、A*算法等。

        但是更多情况下,你所面临的问题并没有现成的算法实现,需要程序员具有创新的精神。

        算法设计需要具备很好的数学基础,但数学并不是唯一需要的知识,计算机技术的一些基础学科(比如数据结构)也是必需的知识,有人说:程序=算法+数据结构,这个虽然不完全正确,但是提到了计算机程序最重要的两点,那就是算法和数据结构。

        算法和数据结构永远是紧密联系在一起的,算法可以理解为解决问题的思想,这是程序中最具有创造性的部分,也是一个程序有别于另一个程序的关键点,而数据结构就是这种思想的载体。

        并不是要求每个程序员

        都要精通各种算法

        再次重申一遍,我和大多数人一样,并不是要求每个程序员都精通各种算法。

        大多数程序员可能在整个职业生涯中都不会遇到像ACM(Association for Computing Machinery)组织的国际大学生程序设计竞赛中的问题,但是说用不到数据结构和算法则是不可想象的。

        说数据结构和算法没用的人是因为他们用不到,用不到的原因是他们想不到,而想不到的原因是他们不会。请息怒,我不是要打击任何人,很多情况下确实是因为不会,所以才用不到,下面就是一个典型的例子。

        一个队列引发的惨案

        我所在的团队负责一款光接入网产品的“EPON 业务管理模块”的开发和维护工作,这是电信级的网络设备,因此对各方面性能的要求都非常高。

        有一天,一个负责集成测试的小伙儿跑过来对我说,今天的每日构造版本出现异常,所有线卡(承载数据业务的板卡)的上线时间比昨天的版本慢了4分钟左右。

        我很惊讶,对于一个电信级网络设备来说,每次加电后的线卡上线时间就是业务恢复时间,业务恢复时间这么慢是不能接受的。于是我检查了一下前一天的代码入库记录,很快就找到了问题所在。

        原来当前版本的任务列表中有这样一项功能,那就是记录线卡的数据变更日志,需求的描述是在线卡上维护一个日志缓冲区,每当有用户操作造成数据变更时,就记录一条变更信息,线卡上线时的批量数据同步也属于操作数据变更,也要计入日志。

        因为是嵌入式设备,线卡上日志缓冲区的大小受限制,最多只能存储1000条记录,当记录的日志超过1000条时,新增的日志记录将覆盖旧的记录,也就是说,这个日志缓冲区只保留最近写入的1000条记录。

        一个新来的小伙儿接受了这个任务,并在前一天下班前将代码签入库中(程序员要记住啊,一定不要在临下班前签入代码)。

        他的实现方案大致是这样的(注释是我加上的):

        这个方案使用一个长度为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,性能依然很差。

        其实,类似这样的固定长度缓冲区的读写,环形队列通常是最好的选择。

        注意

        计算机内存中没有环形结构,因此环形队列都是用线性表来实现的,当数据指针到达线性表的尾部时,就将它转到0位置重新开始。

        实际编程的时候,也不需要每次都判断数据指针是否到达线性表的尾部,通常用取模运算对此做一致性处理。设模拟环形队列的线性表的长度是 N,队头指针为head,队尾指针为tail,则每增加一条记录,就可用以下方法计算新的队尾指针:

        tail = (tail + 1) % N

        对于本例的功能需求,当tail + 1等于head的时候,说明队列已满,此时只需将head指针向前移动一位,就可以在tail位置写入新的记录。使用环形队列,可以避免移动记录操作,本节开始时提到的性能问题就迎刃而解了。

        在这里,套用一句广告词:“没有做不到,只有想不到。”看看,我没说错吧?

        算法的乐趣在哪里

        算法有很多种存在形式,编写计算机程序只是其中一种,是程序员惯用的方式,本书要介绍的内容就是如何以计算机程序的方式研究算法。

        1.2节介绍的两个例子都是我亲身经历过的事情,程序员在大部分时间里都是处理一些平凡而琐碎的程序,但有时候也需要做一些创造性的工作。

        记住,程序员就是计算机的“上帝”,计算机能解决问题是因为它的“上帝”告诉它怎么做。那么,当问题来临的时候,“上帝”是到各种论坛上发帖子求代码,还是自己解决问题?

        如果要自己解决问题,应该如何解决问题?为什么要自己解决问题?先来回答第一个问题——如何设计算法解决问题?

        过程

        人类解决问题的方式是当遇到一个问题时,首先从大脑中搜索已有的知识和经验,寻找它们之间具有关联的地方,将一个未知问题做适当的转换,转化成一个或多个已知问题进行求解,最后综合起来得到原始问题的解决方案。

        编写计算机程序实现算法,让计算机帮我们解决问题的过程也不例外,也需要一定的知识和经验。为了让计算机帮我们解决问题,就要设计计算机能理解的算法程序。而设计算法程序的第一步就是要让计算机理解问题是什么。这就需要建立现实问题的数学模型。

        建模过程就是一个对现实问题的抽象过程,运用逻辑思维能力,抓住问题的主要因素,忽略次要因素。建立数学模型之后,第二个要考虑的问题就是输入输出问题,输入就是将自然语言或人类能够理解的其他表达方式描述的问题转换为数学模型中的数据,输出就是将数学模型中表达的运算结果转换成自然语言或人类能够理解的其他表达方式。

        最后就是算法的设计,其实就是设计一套对数学模型中的数据的操作和转换步骤,使其能演化出最终的结果。

        三大关键因素

        数学模型、输入输出方法和算法步骤是编写计算机算法程序的三大关键因素。对于非常复杂的问题,建立数学模型是非常难的事情,比如天文物理学家研究的“宇宙大爆炸”模型,再比如热力学研究的复杂几何体冷却模型,等等。

        不过,这不是本书探讨的范围,程序员遇到的问题更多的不是这种复杂的理论问题,而是软件开发过程中常用和常见的问题,这些问题简单,但并不枯燥乏味。对于简单的计算机算法而言,建立数学模型实际上就是设计合适的数据结构的问题。

        这又引出了前面提到的话题,数据结构在算法设计过程中扮演着非常重要的角色。输入输出方式和算法步骤设计都是基于相应的数据结构设计的,相应的数据结构要能很方便地将原始问题转换成数据结构中的各个属性,也要能很方便地将数据结构中的结果以人们能够理解的方式输出,同时,也要为算法转换过程中各个步骤的演化提供最便利的支持。

        使用线性表还是关联结构,使用树还是图,都是在设计输入输出和算法步骤时就要考虑的问题。

        为什么要自己解决问题?

        爱因斯坦说过:“兴趣是最好的老师。”这就是说,只要一个人对某事物产生兴趣,就会主动去学习、去研究,并在学习和研究的过程中产生愉快的情绪。

        我把从算法中体会到的乐趣分成三个层次:

        初级层次是找到特定的算法解决特定的实际问题,这种乐趣是解决问题后的成就感;

        中级层次是有些算法本身就是充满乐趣的,搞明白这种算法的原理并写出算法的程序代码,能为自己今后的工作带来便利;

        高级层次是自己设计算法解决问题,让其他人可以利用你的算法享受到初级层次的乐趣。

        有时候问题可能是别人没有遇到过的,没有已知的解法,这种情况下只能自己解决问题。这是本书一直强调算法的乐趣的原因。只有体会到乐趣,才有动力去学习和研究,而这种学习和研究的结果是为自己带来正向的激励,为今后的工作带来便利。

         

        转载请注明:广东技工学校招生网 » 程序员与算法的羁绊,是几世以前就定下的

        上一篇:

        下一篇:

        相关产品

        联系我们

        020-85566215

        在线咨询:

        邮件:800015221@qq.com

        工作时间:

        QR code
        群英会开奖视频 <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <文本链> <文本链> <文本链> <文本链> <文本链> <文本链>