垃圾回收站

April 27, 2008

10年编程无师自通

[ 分类: 其他技术 ] 由 弗里曼·潘 发表于 3:49 am 评论( 0 )

FooSleeper 翻译   更新:2005-01-12 10:18:06  版本: 1.09   

原文:Teach Yourself Programming in Ten Years
作者:Peter Norvig
翻译:郭晓刚(foosleeper@163.net)
最后修订日期:2004-3-19
2005-01-12增加了新的译本链接。

本中文译本得到了Peter Norvig的许可。

为什么每个人都急不可耐?

走进任何一家书店,你会看见《Teach Yourself Java in 7 Days》(7天Java无师自通)的旁边是一长排看不到尽头的类似书籍,它们要教会你Visual Basic、Windows、Internet等等,而只需要几天甚至几小时。我在Amazon.com上进行了如下搜索:
pubdate: after 1992 and title: days and (title: learn or title: teach yourself)
(出版日期:1992年后 and 书名:天 and (书名:学会 or 书名:无师自通))
我一共得到了248个搜索结果。前面的78个是计算机书籍(第79个是《Learn Bengali in 30 days》,30天学会孟加拉语)。我把关键词“days”换成“hours”,得到了非常相似的结果:这次有253本书,头77本是计算机书籍,第78本是《Teach Yourself Grammar and Style in 24 Hours》(24小时学会文法和文体)。头200本书中,有96%是计算机书籍。
结论是,要么是人们非常急于学会计算机,要么就是不知道为什么计算机惊人地简单,比任何东西都容易学会。没有一本书是要在几天里教会人们欣赏贝多芬或者量子物理学,甚至怎样给狗打扮。
让我们来分析一下像《Learn Pascal in Three Days》(3天学会Pascal)这样的题目到底是什么意思:

学会:在3天时间里,你不够时间写一些有意义的程序,并从它们的失败与成功中学习。你不够时间跟一些有经验的程序员一起工作,你不会知道在那样的环境中是什么滋味。简而言之,没有足够的时间让你学到很多东西。所以这些书谈论的只是表面上的精通,而非深入的理解。如Alexander Pope(译注:英国诗人、作家,1688-1744)所言,一知半解是危险的(a little learning is a dangerous thing)

Pascal:在3天时间里你可以学会Pascal的语法(如果你已经会一门类似的语言),但你无法学到多少如何运用这些语法。简而言之,如果你是,比如说一个Basic程序员,你可以学会用Pascal语法写出Basic风格的程序,但你学不到Pascal真正的优点(和缺点)。那关键在哪里?Alan Perlis(译注:ACM第一任主席,图灵奖得主,1922-1990)曾经说过:“如果一门语言不能影响你对编程的想法,那它就不值得去学”。另一种观点是,有时候你不得不学一点Pascal(更可能是Visual Basic和JavaScript之类)的皮毛,因为你需要接触现有的工具,用来完成特定的任务。但此时你不是在学习如何编程,你是在学习如何完成任务。

3天:不幸的是,这是不够的,正如下一节所言。

10年编程无师自通

一些研究者(Hayes、Bloom)的研究表明,在许多领域,都需要大约10 年时间才能培养出专业技能,包括国际象棋、作曲、绘画、钢琴、游泳、网球,以及神经心理学和拓扑学的研究。似乎并不存在真正的捷径:即使是莫扎特,他4 岁就显露出音乐天才,在他写出世界级的音乐之前仍然用了超过13年时间。再看另一种音乐类型的代表–披头士,他们似乎是在1964年的Ed Sullivan节目中突然冒头的。但其实他们从1957年就开始表演了,即使他们很早就显示出了巨大的吸引力,他们第一次真正的成功之作《Sgt. Peppers》也要到1967年才发行。Samuel Johnson(译注:英国诗人)认为10 年还是不够的:“任何领域的卓越成就都只能通过一生的努力来获得;稍低一点的代价也换不来。”(Excellence in any department can be attained only by the labor of a lifetime; it is not to be purchased at a lesser price.) 乔叟(译注:Chaucer,英国诗人,1340-1400)也抱怨说:“生命如此短暂,掌握技艺却要如此长久。”(the lyf so short, the craft so long to lerne.)
下面是我在编程这个行当里获得成功的处方:

对编程感兴趣,因为乐趣而去编程。确定始终都能保持足够的乐趣,以致你能够将10年时间投入其中。

跟其他程序员交谈;阅读其他程序。这比任何书籍或训练课程都更重要。

编程。最好的学习是从实践中学习。用更加技术性的语言来讲,“个体在特定领域最高水平的表现不是作为长期的经验的结果而自动获得的,但即使是非常富有经验的个体也可以通过刻意的努力而提高其表现水平。”(p. 366),而且“最有效的学习要求为特定个体制定适当难度的任务,有意义的反馈,以及重复及改正错误的机会。”(p. 20-21)《Cognition in Practice: Mind, Mathematics, and Culture in Everyday Life》(在实践中认知:心智、数学和日常生活的文化)是关于这个观点的一本有趣的参考书。

如果你愿意,在大学里花上4年时间(或者再花几年读研究生)。这能让你获得一些工作的入门资格,还能让你对此领域有更深入的理解,但如果你不喜欢进学校,(作出一点牺牲)你在工作中也同样能获得类似的经验。在任何情况下,单从书本上学习都是不够的。“计算机科学的教育不会让任何人成为内行的程序员,正如研究画笔和颜料不会让任何人成为内行的画家”,Eric Raymond,《The New Hacker’s Dictionary》(新黑客字典)的作者如是说。我曾经雇用过的最优秀的程序员之一仅有高中学历;但他创造出了许多伟大的软件,甚至有讨论他本人的新闻组,而且股票期权让他达到我无法企及的富有程度(译注:指Jamie Zawinski,XEmacs和Netscape Navigator的作者)。

跟别的程序员一起完成项目。在一些项目中成为最好的程序员;在其他一些项目中当最差的一个。当你是最好的程序员时,你要测试自己领导项目的能力,并通过你的洞见鼓舞其他人。当你是最差的时候,你学习高手们在做些什么,以及他们不喜欢做什么(因为他们让你帮他们做那些事)。

接手别的程序员完成项目。用心理解别人编写的程序。看看在没有最初的程序员在场的时候理解和修改程序需要些什么。想一想怎样设计你的程序才能让别人接手维护你的程序时更容易一些。

学会至少半打编程语言。包括一门支持类抽象(class abstraction)的语言(如Java或C++),一门支持函数抽象(functional abstraction)的语言(如Lisp或ML),一门支持句法抽象(syntactic abstraction)的语言(如Lisp),一门支持说明性规约(declarative specification)的语言(如Prolog或C++模版),一门支持协程(coroutine)的语言(如Icon或Scheme),以及一门支持并行处理(parallelism)的语言(如Sisal)。

记住在“计算机科学”这个词组里包含“计算机”这个词。了解你的计算机执行一条指令要多长时间,从内存中取一个word要多长时间(包括缓存命中和未命中的情况),从磁盘上读取连续的数据要多长时间,定位到磁盘上的新位置又要多长时间。(答案在这里。)

尝试参与到一项语言标准化工作中。可以是ANSI C++委员会,也可以是决定自己团队的编码风格到底采用2个空格的缩进还是4个。不论是哪一种,你都可以学到在这门语言中到底人们喜欢些什么,他们有多喜欢,甚至有可能稍微了解为什么他们会有这样的感觉。

拥有尽快从语言标准化工作中抽身的良好判断力。

抱着这些想法,我很怀疑从书上到底能学到多少东西。在我第一个孩子出生前,我读完了所有“怎样……”的书,却仍然感到自己是个茫无头绪的新手。30个月后,我第二个孩子出生的时候,我重新拿起那些书来复习了吗?不。相反,我依靠我自己的经验,结果比专家写的几千页东西更有用更靠得住。
Fred Brooks在他的短文《No Silver Bullets》(没有银弹)中确立了如何发现杰出的软件设计者的三步规划:

尽早系统地识别出最好的设计者群体。

指派一个事业上的导师负责有潜质的对象的发展,小心地帮他保持职业生涯的履历。

让成长中的设计师们有机会互相影响,互相激励。

这实际上是假定了有些人本身就具有成为杰出设计师的必要潜质;要做的只是引导他们前进。Alan Perlis说得更简洁:“每个人都可以被教授如何雕塑;而对米开朗基罗来说,能教给他的倒是怎样能够不去雕塑。杰出的程序员也一样”。
所以尽管去买那些Java书;你很可能会从中找到些用处。但你的生活,或者你作为程序员的真正的专业技术,并不会因此在24小时、24天甚至24个月内发生真正的变化。

参考文献

Bloom, Benjamin (ed.) Developing Talent in Young People, Ballantine, 1985.
Brooks, Fred, No Silver Bullets, IEEE Computer, vol. 20, no. 4, 1987, p. 10-19.
Hayes, John R., Complete Problem Solver, Lawrence Erlbaum, 1989.
Lave, Jean, Cognition in Practice: Mind, Mathematics, and Culture in Everyday Life, Cambridge University Press, 1988.

答案

各种操作的计时,2001年夏天在一台典型的1GHz PC上完成:
执行单条指令 1 纳秒 = (1/1,000,000,000) 秒
从L1缓存中取一个word 2 纳秒
从主内存中取一个word 10 纳秒
从连续的磁盘位置中取一个word 200 纳秒
从新的磁盘位置中取一个word(寻址) 8,000,000纳秒 = 8毫秒

脚注

T. Capey指出Amazon上面《Complete Problem Solver》的页面中,《Teach Yourself Bengali in 21 days》和《Teach Yourself Grammar and Style》被列在了“购买此书的顾客还买了以下书籍”栏目里面。我猜其中一大部分察看这两本书的人都是从我这里过去的。

译本

感谢以下作者将本文翻译成其他语言:
日文(Yasushi Murakawa),中文(郭晓刚),繁体中文(Jason Chen),西班牙文(Carlos Rueda),德文(Stefan Ram),法文(P. E. Allary),土耳其文(Çağıl Uluşahin)。

Peter Norvig (Copyright 2001)


July 29, 2007

算法:百度试题mp3搜索问题

[ 分类: 其他技术 ] 由 弗里曼·潘 发表于 3:40 am 评论( 1 )

发信人: bbinn (明天的明天), 信区: Algorithm
标 题: 百度试题 mp3搜索问题
发信站: 水木社区 (Wed Jul 25 18:03:14 2007), 站内

1. 假设一个 mp3 搜索引擎收录了 2^24 首歌曲,并记录了可收听这些歌曲的 2^30 条 URL,但每首歌的 URL 不超过 2^10 个。系统会定期检查这些 URL,如果一个 URL 不可用则不出现在搜索结果中。现在歌曲名和 URL 分别通过整型的 SONG_ID 和 URL_ID 唯一确定。对该系统有如下需求:
1) 通过 SONG_ID 搜索一首歌的 URL_ID,给出 URL_ID 计数和列表
2) 给定一个 SONG_ID,为其添加一个新的 URL_ID
3) 添加一个新的 SONG_ID
4) 给定一个 URL_ID,将其置为不可用

限制条件:内存占用不超过 1G,单个文件大小不超过 2G,一个目录下的文件数不超过 128 个。

为获得最佳性能,请说明设计的数据结构、搜索算法,以及资源消耗。如果系统数据量扩大,该如何多机分布处理?


- 不谈金钱,不谈妇女,不谈琐事


※ 来源:·水木社区 newsmth.net·[FROM: 218.249.22.*]

[本篇全文] [回复文章] [本篇作者:forcey] [回信给作者] [进入讨论区] [返回顶部]2发信人: forcey (爱到无可救药), 信区: Algorithm
标 题: Re: 百度试题 mp3搜索问题
发信站: 水木社区 (Wed Jul 25 18:11:24 2007), 站内

每个SONG_ID对应一个文本文件,文件里面每行一个URL_ID
这样前3个需求都很容易满足

然后把SONG_ID写成24位二进制,每6位一组分成4组,建立4级目录结构
这样限制条件也满足了

【 在 bbinn (明天的明天) 的大作中提到: 】
: 1. 假设一个 mp3 搜索引擎收录了 2^24 首歌曲,并记录了可收听这些歌曲的 2^30 条 URL,但每首歌的 URL 不超过 2^10 个。系统会定期检查这些 URL,如果一个 URL 不可用则不出现在搜索结果中。现在歌曲名和 URL 分别通过整型的 SONG_ID 和 URL_ID 唯一确定。对该系统有如
: 1) 通过 SONG_ID 搜索一首歌的 URL_ID,给出 URL_ID 计数和列表
: 2) 给定一个 SONG_ID,为其添加一个新的 URL_ID
: 3) 添加一个新的 SONG_ID
: 4) 给定一个 URL_ID,将其置为不可用
内存里放个bitset就解决了
: 限制条件:内存占用不超过 1G,单个文件大小不超过 2G,一个目录下的文件数不超过 128 个。
: 为获得最佳性能,请说明设计的数据结构、搜索算法,以及资源消耗。如果系统数据量扩大,该如何多机分布处理?



Only two things are infinite, the universe and human stupidity,
and I am not sure about the former.

– Albert Einstein


※ 修改:·forcey 于 Jul 25 18:11:43 修改本文·[FROM: 202.106.180.*]
※ 来源:·水木社区 newsmth.net·[FROM: 202.106.180.*]

[本篇全文] [回复文章] [本篇作者:godking] [回信给作者] [进入讨论区] [返回顶部]3发信人: godking (岁月如梭), 信区: Algorithm
标 题: Re: 百度试题 mp3搜索问题
发信站: 水木社区 (Wed Jul 25 18:27:45 2007), 站内

SONG_ID都放入内存,
SONG_ID对应的URL_ID列表节点分两种类型,
类型1小的放入内存,大的对应文件,文件偏移
是否有效,用bit域表示

【 在 bbinn (明天的明天) 的大作中提到: 】
: 1. 假设一个 mp3 搜索引擎收录了 2^24 首歌曲,并记录了可收听这些歌曲的 2^30 条 URL,但每首歌的 URL 不超过 2^10 个。系统会定期检查这些 URL,如果一个 URL 不可用则不出现在搜索结果中。现在歌曲名和 URL 分别通过整型的 SONG_ID 和 URL_ID 唯一确定。对该系统有如
: 1) 通过 SONG_ID 搜索一首歌的 URL_ID,给出 URL_ID 计数和列表
: 2) 给定一个 SONG_ID,为其添加一个新的 URL_ID
: ……………….

※ 来源:·水木社区 newsmth.net·[FROM: 202.106.180.*]

[本篇全文] [回复文章] [本篇作者:bbinn] [回信给作者] [进入讨论区] [返回顶部]4发信人: bbinn (明天的明天), 信区: Algorithm
标 题: Re: 百度试题 mp3搜索问题
发信站: 水木社区 (Wed Jul 25 21:00:48 2007), 站内

太牛了!


【 在 forcey (爱到无可救药) 的大作中提到: 】
: 标 题: Re: 百度试题 mp3搜索问题
: 发信站: 水木社区 (Wed Jul 25 18:11:24 2007), 站内
:
: 每个SONG_ID对应一个文本文件,文件里面每行一个URL_ID
: 这样前3个需求都很容易满足
:
: 然后把SONG_ID写成24位二进制,每6位一组分成4组,建立4级目录结构
: 这样限制条件也满足了
:
: 【 在 bbinn (明天的明天) 的大作中提到: 】
: : 1. 假设一个 mp3 搜索引擎收录了 2^24 首歌曲,并记录了可收听这些歌曲的 2^30 条 URL,但每首歌的 URL 不超过 2^10 个。系统会定期检查这些 URL,如果一个 URL 不可用则不出现在搜索结果中。现在歌曲名和 URL 分别通过整型的 SONG_ID 和 URL_ID 唯一确定。对该系统有如
: : 1) 通过 SONG_ID 搜索一首歌的 URL_ID,给出 URL_ID 计数和列表
: : 2) 给定一个 SONG_ID,为其添加一个新的 URL_ID
: : 3) 添加一个新的 SONG_ID
: : 4) 给定一个 URL_ID,将其置为不可用
: 内存里放个bitset就解决了
: : 限制条件:内存占用不超过 1G,单个文件大小不超过 2G,一个目录下的文件数不超过 128 个。
: : 为获得最佳性能,请说明设计的数据结构、搜索算法,以及资源消耗。如果系统数据量扩大,该如何多机分布处理?
:
:
: –
: Only two things are infinite, the universe and human stupidity,
: and I am not sure about the former.
:
: — Albert Einstein
:
:
: ※ 修改:·forcey 于 Jul 25 18:11:43 修改本文·[FROM: 202.106.180.*]
: ※ 来源:·水木社区 newsmth.net·[FROM: 202.106.180.*]



- 不谈金钱,不谈妇女,不谈琐事


※ 来源:·水木社区 newsmth.net·[FROM: 211.99.222.*]

[本篇全文] [回复文章] [本篇作者:SeeKee] [回信给作者] [进入讨论区] [返回顶部]5发信人: SeeKee (寻找梦起飞的地方), 信区: Algorithm
标 题: Re: 百度试题 mp3搜索问题
发信站: 水木社区 (Wed Jul 25 21:25:40 2007), 站内

太多io操作了。

【 在 bbinn (明天的明天) 的大作中提到: 】
: 太牛了!


※ 来源:·水木社区 newsmth.net·[FROM: 61.148.100.*]

[本篇全文] [回复文章] [本篇作者:forcey] [回信给作者] [进入讨论区] [返回顶部]6发信人: forcey (爱到无可救药), 信区: Algorithm
标 题: Re: 百度试题 mp3搜索问题
发信站: 水木社区 (Wed Jul 25 21:30:08 2007), 站内

系统会自动把剩下的内存用来缓存频繁访问的文件的

如果按照楼上某位兄弟的做法,把小列表放内存把大列表放硬盘,
不能保证小列表都是频繁访问的列表

【 在 SeeKee (寻找梦起飞的地方) 的大作中提到: 】
: 太多io操作了。


Next Page »