Archive for 八月, 2011

iQuit

不必担心,不是《三个傻瓜》里的Joy写的。

今天从科协活动室搬出来了,发文纪念一下。在活动室呆了将近三年, 大学里最美好的时光都是在那里度过的。从404那小小的拥挤的房间,到501宽敞舒适的工作室,这三年,几乎每一件科协发生的事,我都参与和经历,一人一景,仍历历在目。今天走的时候除了帮忙搬东西的室友,没有一个人在活动室。然后给笑笑和胡英晨各打了个电话,告知他们我搬走的事。

今天还有一个人离开了——乔布斯,他辞去了苹果CEO的职务。早上一整开眼,就看到了这条消息, 在想这是不是巧合。晚上回顾乔布斯05年在斯坦福的毕业典礼上的演讲,依然被那句执着的话语打动——stay hungry, stay foolish.

这不是终点,是另一条道路的起点。

2 Comments

编程珠玑,字字珠玑

Programming Pearls跌跌撞撞,连滚带爬地但还算仔细地读完了这本书,感觉身心愉悦、神清气爽,决定还要再度几遍。

首先,这本书的书名好,中文译名更好——《编程珠玑》,正如本书的风格,篇幅精悍短小,行文流畅优美,十五章的正文如十五颗熠熠生辉的珍珠,阐释着编程之道,没有一句话多余,也不必再增,果然字字珠玑。译者显然比我功力深许多,要是我,恐怕就直接译成珍珠了——过于直白,顿失优雅。

概览全书,共分15章,短的仅四五页,长的不过数十页,一本书薄薄200来页,似有K&R《C程序设计语言》一书风格。前十章介绍程序设计的基本原则和基本技能技术,后五章给出运用这些原则、技术的实际应用,“效率”是贯穿全书的主题。每一章开始提出有关本章主题的若干个问题,接下来详细分析,给出解决方案,章末还有总结和拓展习题。语言风格绝非教科书式的“周吴郑王”,更像是在讲故事,如作者在第一版跋中自问自答所述,“本书的章节侧重的是故事情节而不是定理和表格”。源码大多以接近C/C++伪代码写成,也有部分C/C++代码,这样将主要的注意力集中在算法和数据结构上,而不是规范的声明、接口,有些甚至略去了错误检查机制。边栏和深入阅读大大拓宽了读者的视野。

我觉得有必要按章来总结一下这本书。

第一章
开篇提出“怎样给一个磁盘的文件排序”的问题,阐述了正确定义和理解问题的重要性,这是程序设计的第一步。这一章回答了为什么要自己设计数据结构自己设计程序,而不用系统提供的功能。事实上,系统为我们提供了许多有用的程序功能,但是有时候因为一些原因,我们不能使用,更多的时候是因为效率问题,我们需要自己设计。

第二章
通过三个问题揭示算法给程序员带来的好处,一个精妙的算法在时空效率上给程序带来的好处。1.在海量数据中寻找缺失的某个数字;2.字符串的循环左移; 3.寻找“变位词”集合。在本书中第一次正式讲到了二分搜索和排序。

第三章
数据视图决定了我们在程序中应该采用什么样的数据结构,好的数据结构可以简化代码。

第四章
这是非常重要的一章,本章仔仔细细地讨论了二分搜索,从最初用伪代码表示二分搜索的思想,一点一点扩充完善代码,最终形成非常接近C代码的伪代码。后半部分使用程序验证技术讨论了上述代码的正确性,逻辑缜密。

第五章
将第四章的二分搜索的伪代码用C语言实现,使用断言对所实现的程序进行了测试,并介绍了一些测试和程序计时的方法。 第五章的第一条习题讨论了本书的编程风格。

第六章
讨论了程序性能分析,以一个实例讲述了在计算机系统的若干个设计层面上提高程序执行效率的方法,然后给出了系统化观点的总结。

第七章
这一章是有趣的估算。开篇讲述了一些估算的基本技巧,然后介绍了程序性能的估计等问题。

第八章
这一章可以看作是第二章的进一步讲解,突出了算法设计在程序设计中的重要地位。本章的问题是“求和最大的连续子序列”,这是今年淘宝实习生招聘研发类的一道笔试题。对这个问题,本章给出了4种不同的算法,从一个显而易见的算法开始,逐步优化,降低时间复杂度,最终得出最优算法,过程非常详细。

第九章
这一章讲的是代码调优。前半部分讲了四个问题的代码调优。1.整数取模;2.函数、宏和内联代码;3.顺序搜索;4.计算球面距离。后半部分对二分搜索进行了细致的代码调优,书中称之为“大手术”。

第十章
讨论了如何节省空间。前半部分以实例介绍了稀疏疏结构,后半部分给出了数据空间技术和代码空间技术,使用这些技术以节省存储空间和代码空间。

第十一章
这一章详细介绍了插入排序和快速排序,同样从最初简陋的代码逐步优化算法,并使用部分第九章介绍的代码调优技术对代码进行优化。

第十二章
讨论一个有趣的问题——生成随机数。本章给出了三种不同的解决方案。

第十三章
本章介绍了5种表示集合的重要数据结构——数组、链表、二叉搜索树、箱和位向量。对每一种数据结构的实现都做了详细的讲解,并对其性能进行了分析,同时提出了一些优化的方法。

第十四章
介绍了两个重要的数据结构——堆和优先级队列。后半部分介绍了堆排序。

第十五章
这一章围绕字符串进行了一些讨论,统计一本书中每个单词出现的次数,查找字符串中最长的重复子字符串以及随机生成文本,主要涉及的数据结构是散列表和“后缀数组”(字符指针数组)。章末再次讨论了关于使用库组件还是定制组件的问题,一些库组件通用性强,但效率不如定制的专用组件高;有些库组件是非常高效的。

最后说说我觉得这本书不足的地方。本书把习题提示和习题答案分开了,我觉得没有必要,这反而给读者带来了阅读困难,实际上某些习题提示已经非常接近最终答案了,而某些习题答案只是给出了提示性的语言,所以两部分合并起来为好,也方便阅读。本书一些章节的标题起的不好,这似乎和一个我非常赞赏的书名很矛盾,比如第十三章,章标题是“搜索”,而主要内容将的却是几种数据结构,虽然这章开始交代了本章内容有一个搜索问题引发,可我怎么也看不出那是一个搜索问题。前面有些章节的标题也不够好,看不出本章的内容到底是什么。个人见解,仅供参考。

2 Comments

竞技体育何时讲过同情

我是在知道结果后才看的林李大战的比赛录像,可即便是这样,在看到决胜局的最后几分,我仍然手心出汗,心跳加快。尽管赛前李宗伟的夺冠呼声很高,而且本届世锦赛之前的比赛中,李一路全数2-0战胜对手,还有重要的一点——李从未在世界大赛上获得冠军,但结果,李还是输了比赛。

李宗伟在这场比赛中的精彩表现给我很深的印象,这场比赛可以称作艺术演绎了。一个突击后场的发球,林仓促过渡,李半场直线扣杀;一个接发球的假动作,球拍下压,手腕一变勾出个对角。最为精彩的一分是第一局的后半程,林后场起跳杀直线,李反手接球挡在网前,林紧接着第二拍扑杀,处于被动的李胯下接球,林上前挡网,本来已经很被动,但李连贯回应将球挑至后场,赢得调整时间,随后迅速攻防转换,网前扑杀拿下一分。李振臂握拳,向观众致意。解说洪刚称李宗伟的防守“简直是绝了”,并回忆说世锦赛上胯下接球并且能拿下这一分的,“上一次还是1987年”。

竞技体育之残酷就在于它从不讲同情。你是无冕的世界第一也好,在公开赛上表现完美也好,渴望胜利无人能敌也好,甚至观众的“轮也该轮到李宗伟了”的心理也罢,竞技体育才不管这些,不会因为林丹已经拿过14个世界冠军就把这次的金牌安排给李宗伟,这种情节未免太剧情化了。站在领奖台上,眼角依然挂着泪痕的黯然神伤的李宗伟尽显悲情。这让我想起08年北京奥运会上的男花三剑客,最后一枪打在别人靶位上的埃蒙森,他们离最高荣誉那么近但依然没有够得着。

竞技体育之美丽也在于它从不讲同情。期待下一场林李大战。

(图片来源:网易体育

No Comments

估计与速算

通常我们对于自己一时难以给出问题的精确答案的时候会冠以“大概”或者“我估计”的字眼,比如一个月吃饭花了多少钱,南京地铁二号线有多长这样的问题。这类问题的回答中蕴含了一项工程技术的神奇方法——估算。估算代表了我们对问题的解的粗略计算,是从宏观的性质和范围上的把握。然而估算也不能是瞎算,虽然不精确,但也要靠谱。如果有人告诉你9999×9999的结果是99990001的话,你应当可以在3秒钟之内告诉他结果是错的。有些技巧在进行估算和速算时很有用。

一、快速检验

1、量纲检验
量纲检验有两条法则——第一,和式中各项的量纲必须相同,这个量纲就是最终求和结果的量纲;第二,乘积的量纲是各乘数量纲的乘积。比如,

(英里+英里)×英里×英里/天=英里3/天

在我高中的时候,我经常使用量纲检验来做物理的选择题,有时我未必要考虑给出的答案到底表达了什么意思,但我可以通过给定的答案中每个字母的量纲得出表达式的量纲,初步判断是否为问题的解的量纲。

2、舍九法
舍九法用于验证整数计算结果是否正确。对于加法,每个加数各位数字之和的总和与结果各位数字之和关于模9同余;对于乘法,每个乘数各位数字之和的乘积与结果各位数字之和关于模9同余。舍九法的正确性是由同余的基本性质保证的。

来看一个例子。a=28997,b=39495,如果计算a和b的乘积结果是p=1145236415,按照舍九法,a≡8(mod 9),b≡3(mod 9),p≡5(mod 9),但8×3与5并不关于模9同余,所以这个计算结果是错误的。文章开头说到的9999×9999≠99990001就是根据舍九法判断的。

二、经验法则

1、72法则
假设以年回报率r%投资一笔钱y年,如果r×y=72,那么投资额差不多会翻倍,或者说得到了和投资额差不多的回报额。比如以年回报率6%投资1000元12年,投资额就变成了2012元。

2、翻倍经验法则
210=1024,翻倍10次就大约是1000倍,20次就大约是100万倍。

3、π秒法则
也许记住3.155×107秒就是一年是件很困难的事情,但是,在误差不超过千分之五的情况下,记住“π秒就是一纳世纪”还是很容易的。107秒也就是差不多4个月的时间。

三、Little定律

任意一个带有输入输出的系统,系统中物体的平均数量=物体离开系统的平均速率×每天物体在系统中停留的平均时间。我要是在上海世博会之前知道这条定律就好了,就可以运用这条定律来估计排队时间,合理安排而去更多的展馆参观了。Little定理和流平衡的原理可以证明多用户系统的响应时间公式。

 

程序员在很多时候也需要进行估计和速算,估计与速算能力的是要靠平时实践来提高的,平常通过做一些小实验来积累关键操作的时间或者空间开销是很值得的,这些关键的参数可以在估算和速算中起到重要的作用,从而帮助程序员作出明智的决策。

最后提一个有趣的估算问题:密西西比河一天流出多少水?

1 Comment