| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 3749 人关注过本帖
标题:GGJJ们给小弟指点迷经
只看楼主 加入收藏
蓝色神话
Rank: 2
等 级:论坛游民
威 望:1
帖 子:404
专家分:24
注 册:2006-5-11
收藏
得分:0 
回复 37# VxWorks 的帖子
看你的说法,你好像对OS很了解,那么问你下,windows的结构模式是什么样的?
2008-06-29 21:18
蓝色神话
Rank: 2
等 级:论坛游民
威 望:1
帖 子:404
专家分:24
注 册:2006-5-11
收藏
得分:0 
李开复:算法的力量

算法是计算机科学领域最重要的基石之一,但却受到了国内一些程序员的冷落。许多学生看到一些公司在招聘时要求的编程语言五花八门就产生了一种误解,认为学计算机就是学各种编程语言,或者认为,学习最新的语言、技术、标准就是最好的铺路方法。其实大家都被这些公司误导了。编程语言虽然该学,但是学习计算机算法和理论更重要,因为计算机算法和理论更重要,因为计算机语言和开发平台日新月异,但万变不离其宗的是那些算法和理论,例如数据结构、算法、编译原理、计算机体系结构、关系型数据库原理等等。在“开复学生网”上,有位同学生动地把这些基础课程比拟为“内功”,把新的语言、技术、标准比拟为“外功”。整天赶时髦的人最后只懂得招式,没有功力,是不可能成为高手的。


算法与我

当我在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://labs.)。这个算法能够在很多种计算中达到相当高的效率,而且是可扩展的(也就是说,一千台机器就算不能达到一千倍的效果,至少也可以达到几百倍的效果)。 Map and Reduce的另外一大特色是它可以利用大批廉价的机器组成功能强大的server farm。最后,它的容错性能异常出色,就算一个 server farm宕掉一半,整个fram依然能够运行。正是因为这个天才的认识,才有了Map and Reduce算法。借助该算法,Google几乎能无限地增加计算量,与日新月异的互联网应用一同成长。


算法并不局限于计算机和网络

举一个计算机领域外的例子:在高能物理研究方面,很多实验每秒钟都能几个TB的数据量。但因为处理能力和存储能力的不足,科学家不得不把绝大部分未经处理的数据丢弃掉。可大家要知道,新元素的信息很有可能就藏在我们来不及处理的数据里面。同样的,在其他任何领域里,算法可以改变人类的生活。例如人类基因的研究,就可能因为算法而发明新的医疗方式。在国家安全领域,有效的算法可能避免下一个911的发生。在气象方面,算法可以更好地预测未来天灾的发生,以拯救生命。

所以,如果你把计算机的发展放到应用和数据飞速增长的大环境下,你一定会发现;算法的重要性不是在日益减小,而是在日益加强。
2008-06-29 21:21
蓝色神话
Rank: 2
等 级:论坛游民
威 望:1
帖 子:404
专家分:24
注 册:2006-5-11
收藏
得分:0 
我最近在做编译原理的课程设计,我最深的一个感触是,没有算法,就没有编译技术,编译技术是以算法为基础的。
2008-06-29 21:24
simpley
Rank: 1
等 级:新手上路
帖 子:262
专家分:0
注 册:2005-2-23
收藏
得分:0 
我认为算法有广义和狭义之分,狭义就是编程中的算法;广义的包括计算机软硬件中只要以数学为基础或涉及数学的因素,都可以称为算法。逻辑电路、编译原理、计算机原理中都存在大量算法。比如,CPU中的布斯乘法,就很巧妙。

    从运用的角度说,算法一是正好可以帮助解决遇到的问题,但更多的作用在于训练思维,通过这种训练,不仅可以解决编程中的问题,还可以开拓思路,灵活地、创造性地解决更多的技术上的问题。

     通常,我们如果在某一个领域内比较在行,是因为我们对这个领域内的东西比较熟悉。但如果两个人都很熟悉的话,那差距就在于灵活性、创造性。

myQQ::445750010
2008-06-29 21:26
VxWorks
Rank: 3Rank: 3
来 自:WindRiver
等 级:论坛游民
威 望:6
帖 子:859
专家分:68
注 册:2007-11-24
收藏
得分:0 
不要给我看这个
我知道算法有多重要。我只是看不惯有些人对计算机狭隘的理解,在他们看来学计算机就是学算法,学算法就是做ACM

找了张NT内核结构图
图片附件: 游客没有浏览图片的权限,请 登录注册

为了防止世界被破坏,为了守护世界的和平,贯彻爱与真实的邪恶,可爱又迷人的反派角色,VxWorks!
Don't ask me any question.I'm just here to buy soy sauce.
2008-06-29 21:26
中学者
Rank: 16Rank: 16Rank: 16Rank: 16
等 级:版主
威 望:20
帖 子:3554
专家分:80
注 册:2007-9-14
收藏
得分:0 
回复 45# VxWorks 的帖子
我认为是你的理解有问题...........
计算机领域这么广,在理论建立好的基础上,最终还是算法的实现.....没谁说算法就是A下ACM....

樱花大战,  有爱.
2008-06-29 21:30
蓝色神话
Rank: 2
等 级:论坛游民
威 望:1
帖 子:404
专家分:24
注 册:2006-5-11
收藏
得分:0 
[bo][un]simpley[/un] 在 2008-6-29 21:26 的发言:[/bo]

我认为算法有广义和狭义之分,狭义就是编程中的算法;广义的包括计算机软硬件中只要以数学为基础或涉及数学的因素,都可以称为算法。逻辑电路、编译原理、计算机原理中都存在大量算法。比如,CPU中的布斯乘法,就很巧 ...

支持!
2008-06-29 21:30
蓝色神话
Rank: 2
等 级:论坛游民
威 望:1
帖 子:404
专家分:24
注 册:2006-5-11
收藏
得分:0 
[bo][un]VxWorks[/un] 在 2008-6-29 21:26 的发言:[/bo]

不要给我看这个
我知道算法有多重要。我只是看不惯有些人对计算机狭隘的理解,在他们看来学计算机就是学算法,学算法就是做ACM

找了张NT内核结构图
35948

不用找,windows系统内幕那本书就有,写的不错,推荐看看!
2008-06-29 21:31
VxWorks
Rank: 3Rank: 3
来 自:WindRiver
等 级:论坛游民
威 望:6
帖 子:859
专家分:68
注 册:2007-11-24
收藏
得分:0 
27楼不就是张口就给我提ACM吗?
看我45楼回复,我是看不惯有人把计算机和算法理解的太狭隘了

为了防止世界被破坏,为了守护世界的和平,贯彻爱与真实的邪恶,可爱又迷人的反派角色,VxWorks!
Don't ask me any question.I'm just here to buy soy sauce.
2008-06-29 21:32
蓝色神话
Rank: 2
等 级:论坛游民
威 望:1
帖 子:404
专家分:24
注 册:2006-5-11
收藏
得分:0 
其实思考很重要,算法就是用来训练思考能力的。
2008-06-29 21:33
快速回复:GGJJ们给小弟指点迷经
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.030086 second(s), 8 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved