算法的力量
算法的力量—李开复
算法的力量
李开复 2006 年5 月
算法是计算机科学领域最重要的基石之一,但却受到了国内一些程序员的冷落。许多学生看到一些公司在招聘时要求的编程语言五花八门,就产生了一种误解,认为学计算机就是学各种编程语言,或者认为,学习最新的语言、技术、标准就是最好的铺路方法。其实,大家被这些公司误导了。编程语言虽然该学,但是学习计算机算法和理论更重要,因为计算机语言和开发平台日新月异,但万变不离其宗的是那些算法和理论,例如数据结构、算法、编译原理、计算机体系结构、关系型数据库原理等等。在“开复学生网”上,有位同学生动地把这些基础课程比拟为“内功”,把新的语言、技术、标准比拟为“外功”。整天赶时髦的人最后只懂得招式,没有功力,是不可能成为高手的。
算法与我
当我在1980 年转入计算机科学系时,还没有多少人的专业方向是计算机科学。有许多其他系的人嘲笑我们说: “知道为什么只有你们系要加一个?科学?,而没有?物理科学系?或?化学科学系?吗?因为人家是真的科学,不需要画蛇添足,而你们自己心虚,生怕不?科学?,才这样欲盖弥彰。” 其实,这点他们彻底弄错了。真正学懂计算机的人(不只是“编程匠”)都对数学有相当的造诣,既能用科学家的严谨思维来求证,也能用工程师的务实手段来解决问题——而这种思维和手段的
算法的力量—李开复
最佳演绎就是“算法”。 记得我读博时写的Othello 对弈软件获得了世界冠军。当时, 得第二名的人认为我是靠侥幸才打赢他,不服气地问我的程序平均每秒能搜索多少步棋,当他发现我的软件在搜索效率上比他快60 多倍时,才彻底服输。为什么在同样的机器上,我可以多做60 倍的工作呢?这是因为我用了一个最新的算法,能够把一个指数函数转换成四个近似的表,只要用常数时间就可得到近似的答案。在这个例子中,是否用对算法才是能否赢得世界冠军的关键。 还记得1988 年贝尔实验室副总裁亲自来访问我的学校,目的就是为了想了解为什么他们的语音识别系统比我开发的慢几十倍,而且,在扩大至大词汇系统后,速度差异更有几百倍之多。他们虽然买了几台超级计算机,勉强让系统跑了起来,但这么贵的计算资源让他们的产品部门很反感,因为“昂贵” 的技术是没有应用前景的。在与他们探讨的过程中,我惊讶地发现一个O(n*m)的动态规划(dynamic
programming) 居然被他们做成了O(n*n*m)。更惊讶的是,他们还为此发表了不少文章,甚至为自己的算法起了一个很特别的名字, 并将算法提名到一个科学会议里,希望能得到大奖。当时, 贝尔实验室的研究员当然绝顶聪明,但他们全都是学数学、物理或电机出身,从未学过计算机科学或算法,才犯了这么基本的错误。我想那些人以后再也不会嘲笑学计算机科学的人了吧!
网络时代的算法
有人也许会说:“今天计算机这么快,算法还重要吗?” 其实永远不会
算法的力量—李开复
有太快的计算机,因为我们总会想出新的应用。虽然在摩尔定律的作用下,计算机的计算能力每年都在飞快增长,价格也在不断下降。可我们不要忘记,需要处理的信息量更是呈指数级的增长。现在每人每天都会创造出大量数据(照片,视频,语音,文本等等)。日益先进的记录和存储手段使我们每个人的信息量都在爆炸式的增长。互联网的信息流量和日志容量也在飞快增长。在科学研究方面,随着研究手段的进步,数据量更是达到了前所未有的程度。无论是三维图形、海量数据处理、机器学习、语音识别,都需要极大的计算量。在网络时代,越来越多的挑战需要靠卓越的算法来解决。 再举另一个网络时代的例子。在互联网和手机搜索上,如果要找附近的咖啡店, 那么搜索引擎该怎么处理这个请求呢? 最简单的办法就是把整个城市的咖啡馆都找出来,然后计算出它们的所在位置与你之间的距离,再进行排序,然后返回最近的结果。但该如何计算距离呢?图论里有不少算法可以解决这个问题。 这么做也许是最直观的,但绝对不是最迅速的。如果一个城市只有为数不多的咖啡馆,那这么做应该没什么问题,反正计算量不大。但如果一个城市里有很多咖啡馆,又有很多用户都需要类似的搜索,那么服务器所承受的压力就大多了。在这种情况下,我们该怎样优化算法呢? 首先, 我们可以把整个城市的咖啡馆做一次“预处理”。比如,把一个城市分成若干个“格子(grid)”,然后根据用户所在的位置把他放到某一个格子里,只对格子里的咖啡馆进行距离排序。 问题又来了,如果格子大小一样,那么绝大多数结果都可能出现在市中心的一个格子里,而郊区的格子里只有极少的结果。在这
算法的力量—李开复
种情况下,我们应该把市中心多分出几个格子。更进一步,格子应该是一个“树结构”,最顶层是一个大格——整个城市,然后逐层下降,格子越来越小,这样有利于用户进行精确搜索——如果在最底层的格子里搜索结果不多,用户可以逐级上升,放大搜索范围。 上述算法对咖啡馆的例子很实用,但是它具有通用性吗?答案是否定的。把咖啡馆抽象一下,它是一个“点”,如果要搜索一个“面”该怎么办呢?比如,用户想去一个水库玩, 而一个水库有好几个入口,那么哪一个离用户最近呢?这个时候,上述“树结构”就要改成“r-tree”,因为树中间的每一个节点都是一个范围,一个有边界的范围(参考:
http://www.cs.umd.edu/~hjs/rtrees/index.html)。 通过这个小例子,我们看到,应用程序的要求千变万化, 很多时候需要把一个复杂的问题分解成若干简单的小问题,然后再选用合适的算法和数据结构。 并行算法:Google 的核心优势 上面的例子在Google 里就要算是小case 了! 每天Google 的网站要处理十亿个以上的搜索,GMail 要储存几千万用户的2G 邮箱,Google Earth 要让数十万用户同时在整个地球上遨游,并将合适的图片经过互联网提交给每个用户。如果没有好的算法,这些应用都无法成为现实。 在这些的应用中,哪怕是最基本的问题都会给传统的计算带来很大的挑战。例如,每天都有十亿以上的用户访
算法的力量—李开复
问Google 的网站,使用Google 的服务,也产生很多很多的日志(Log)。因为Log 每分每秒都在飞速增加,我们必须有聪明的办法来进行处理。我曾经在面试中问过关于如何对log 进行一些分析处理的问题,有很多面试者的回答虽然在逻辑上正确,但在实际应用中是几乎不可行的。按照他们的算法,即便用上几万台机器,我们的处理速度都跟不上数据产生的速度。 那么Google 是如何解决这些问题的呢? 首先,在网络时代,就算有最好的算法,也要能在并行计算的环境下执行。在Google 的数据中心,我们使用的是超大的并行计算机。但传统的并行算法运行时,效率会在增加机器数量后迅速降低,也就是说,十台机器如果有五倍的效果,增加到一千台时也许就只有几十倍的效果。这种事倍功半的代价是没有哪家公司可以负担得起的。而且,在许多并行算法中,只要一个结点犯错误,所有计算都会前功尽弃。 那么Google 是如何开发出既有效率又能容错的并行计算的呢? Google 最资深的计算机科学家Jeff Dean 认识到, Google 所需的绝大部分数据处理都可以归结为一个简单的并行算法: Map and Reduce ( http://wendang.chazidian.com/papers/mapreduce.html )。 这个算法能够在很多种计算中达到相当高的效率,而且是可扩展的(也就是说,一千台机器就算不能达到一千倍的效果,至少也可以达到几百倍的效果)。Map and Reduce 的另外一大特色是它可以利用大批廉价的机器组成功能强大的server farm。最后,它的容错性能异常出色,就算一个server farm 里面的机器down 掉一半,整个farm 依然能够运行。正是因为这个天才的认识,才有了Map and Reduce 算法。
下载文档
热门试卷
- 2016年四川省内江市中考化学试卷
- 广西钦州市高新区2017届高三11月月考政治试卷
- 浙江省湖州市2016-2017学年高一上学期期中考试政治试卷
- 浙江省湖州市2016-2017学年高二上学期期中考试政治试卷
- 辽宁省铁岭市协作体2017届高三上学期第三次联考政治试卷
- 广西钦州市钦州港区2016-2017学年高二11月月考政治试卷
- 广西钦州市钦州港区2017届高三11月月考政治试卷
- 广西钦州市钦州港区2016-2017学年高一11月月考政治试卷
- 广西钦州市高新区2016-2017学年高二11月月考政治试卷
- 广西钦州市高新区2016-2017学年高一11月月考政治试卷
- 山东省滨州市三校2017届第一学期阶段测试初三英语试题
- 四川省成都七中2017届高三一诊模拟考试文科综合试卷
- 2017届普通高等学校招生全国统一考试模拟试题(附答案)
- 重庆市永川中学高2017级上期12月月考语文试题
- 江西宜春三中2017届高三第一学期第二次月考文科综合试题
- 内蒙古赤峰二中2017届高三上学期第三次月考英语试题
- 2017年六年级(上)数学期末考试卷
- 2017人教版小学英语三年级上期末笔试题
- 江苏省常州西藏民族中学2016-2017学年九年级思想品德第一学期第二次阶段测试试卷
- 重庆市九龙坡区七校2016-2017学年上期八年级素质测查(二)语文学科试题卷
- 江苏省无锡市钱桥中学2016年12月八年级语文阶段性测试卷
- 江苏省无锡市钱桥中学2016-2017学年七年级英语12月阶段检测试卷
- 山东省邹城市第八中学2016-2017学年八年级12月物理第4章试题(无答案)
- 【人教版】河北省2015-2016学年度九年级上期末语文试题卷(附答案)
- 四川省简阳市阳安中学2016年12月高二月考英语试卷
- 四川省成都龙泉中学高三上学期2016年12月月考试题文科综合能力测试
- 安徽省滁州中学2016—2017学年度第一学期12月月考高三英语试卷
- 山东省武城县第二中学2016.12高一年级上学期第二次月考历史试题(必修一第四、五单元)
- 福建省四地六校联考2016-2017学年上学期第三次月考高三化学试卷
- 甘肃省武威第二十三中学2016—2017学年度八年级第一学期12月月考生物试卷
网友关注
- 北京大学医学部100232重症医学考研目录
- 国家工程实验室落户郑州大学一附院
- 民间乐器在民间舞蹈当中的体现—以维吾尔族民间舞蹈为例0102
- 法国高中排名的评定标准
- 2016最新最全互联网+大时代众创空间新型孵化器运营策划方案Word
- 两学一做001-Word2013
- 如何管理育留90后员工Word
- 如何树立主管的形象Word
- 税法与税收实务讲义——消费税Word
- 如何管理育留90后员工Word
- 肖临骏:民法执行程序中债权平等性与物权优先性的体现
- 循环荷载频率对高速铁路有砟道床累积变形行为的影响
- 结算培训080312Word
- 《文学理论教程》童庆炳课件第十二章Word
- 北京大学医学部100217麻醉学考研目录
- 2016最新最全中国虚拟现实行业发展前景及趋势分析Word
- 心记
- JavaEE首期学员最高薪资25000 看千锋如何做到的?
- 幼儿园门卫安全工作责任书
- 2016全国最新两会精神最全最新完整版本Word
- 化学品危险性鉴别与分类Word
- 国考资格证考前押题预测-小学综合素质-华图教师网
- 包装培训Word
- 朗诵比赛校长致词
- 拜访细节Word
- 新闻写作培训课件Word
- 税法与税收实务讲义——消费税Word
- 消防联动系统工程施工组织设计可行性方案
- 第8章 作业调度、第9章设备管理答案Word
- 移动互联网+时代 互联网+金融创新与发展Word
网友关注视频
- 冀教版小学英语五年级下册lesson2教学视频(2)
- 冀教版小学数学二年级下册第二周第2课时《我们的测量》宝丰街小学庞志荣.mp4
- 【获奖】科粤版初三九年级化学下册第七章7.3浓稀的表示
- 第五单元 民族艺术的瑰宝_16. 形形色色的民族乐器_第一课时(岭南版六年级上册)_T3751175
- 冀教版小学数学二年级下册1
- 冀教版英语三年级下册第二课
- 精品·同步课程 历史 八年级 上册 第15集 近代科学技术与思想文化
- 冀教版小学数学二年级下册第二单元《租船问题》
- 【部编】人教版语文七年级下册《老山界》优质课教学视频+PPT课件+教案,安徽省
- 七年级下册外研版英语M8U2reading
- 冀教版小学数学二年级下册第二周第2课时《我们的测量》宝丰街小学庞志荣
- 第五单元 民族艺术的瑰宝_15. 多姿多彩的民族服饰_第二课时(市一等奖)(岭南版六年级上册)_T129830
- 外研版英语三起5年级下册(14版)Module3 Unit1
- 冀教版英语四年级下册第二课
- 化学九年级下册全册同步 人教版 第18集 常见的酸和碱(二)
- 人教版历史八年级下册第一课《中华人民共和国成立》
- 第4章 幂函数、指数函数和对数函数(下)_六 指数方程和对数方程_4.7 简单的指数方程_第一课时(沪教版高一下册)_T1566237
- 苏科版八年级数学下册7.2《统计图的选用》
- 外研版英语三起6年级下册(14版)Module3 Unit2
- 冀教版小学数学二年级下册第二单元《有余数除法的整理与复习》
- 19 爱护鸟类_第一课时(二等奖)(桂美版二年级下册)_T3763925
- 北师大版数学四年级下册3.4包装
- 30.3 由不共线三点的坐标确定二次函数_第一课时(市一等奖)(冀教版九年级下册)_T144342
- 二次函数求实际问题中的最值_第一课时(特等奖)(冀教版九年级下册)_T144339
- 沪教版牛津小学英语(深圳用) 四年级下册 Unit 7
- 苏科版数学 八年级下册 第八章第二节 可能性的大小
- 【部编】人教版语文七年级下册《过松源晨炊漆公店(其五)》优质课教学视频+PPT课件+教案,辽宁省
- 沪教版牛津小学英语(深圳用) 六年级下册 Unit 7
- 8.对剪花样_第一课时(二等奖)(冀美版二年级上册)_T515402
- 北师大版小学数学四年级下册第15课小数乘小数一
精品推荐
- 2016-2017学年高一语文人教版必修一+模块学业水平检测试题(含答案)
- 广西钦州市高新区2017届高三11月月考政治试卷
- 浙江省湖州市2016-2017学年高一上学期期中考试政治试卷
- 浙江省湖州市2016-2017学年高二上学期期中考试政治试卷
- 辽宁省铁岭市协作体2017届高三上学期第三次联考政治试卷
- 广西钦州市钦州港区2016-2017学年高二11月月考政治试卷
- 广西钦州市钦州港区2017届高三11月月考政治试卷
- 广西钦州市钦州港区2016-2017学年高一11月月考政治试卷
- 广西钦州市高新区2016-2017学年高二11月月考政治试卷
- 广西钦州市高新区2016-2017学年高一11月月考政治试卷
分类导航
- 互联网
- 电脑基础知识
- 计算机软件及应用
- 计算机硬件及网络
- 计算机应用/办公自动化
- .NET
- 数据结构与算法
- Java
- SEO
- C/C++资料
- linux/Unix相关
- 手机开发
- UML理论/建模
- 并行计算/云计算
- 嵌入式开发
- windows相关
- 软件工程
- 管理信息系统
- 开发文档
- 图形图像
- 网络与通信
- 网络信息安全
- 电子支付
- Labview
- matlab
- 网络资源
- Python
- Delphi/Perl
- 评测
- Flash/Flex
- CSS/Script
- 计算机原理
- PHP资料
- 数据挖掘与模式识别
- Web服务
- 数据库
- Visual Basic
- 电子商务
- 服务器
- 搜索引擎优化
- 存储
- 架构
- 行业软件
- 人工智能
- 计算机辅助设计
- 多媒体
- 软件测试
- 计算机硬件与维护
- 网站策划/UE
- 网页设计/UI
- 网吧管理