我参加的第一次workshop

Verified Software Workshop原本昨天就有了,但是昨天因为学校对硕士有歧视所以没赶上校车最终没去(不过今天才听说假期就没有接送学生的校车,而校车只为接送老师;我们能上车是老师给我们的福利);今天才去,多少有些后悔。

是MSRA主办的,四年一届,今年找了华师当搭档了。不过这个workshop没有任何门槛,报个名都可以进;所以我这种沽名钓誉的人就屁颠屁颠的跑去了。

请到了1980年图灵奖得主Tony Hoare来,微软真有心!总是在书中看到霍尔逻辑,在网页上看到霍尔的头像,今天终于见到本尊了;这种欣喜之情就和一个虔诚的佛教徒看到观音显圣一样!CS真是门年轻的学科,用到的理论都还这么新,大神一般的人物竟然还有这么多,而且层出不穷。不过听学长说Hoare讲课经常跑题,动不动就说“Let‘s go back to the point”;唉,毕竟人老了嘛。我错过了昨天的演讲,今天只听到他的几句总结。不过在panel discussion蔡老师问如何做research时,他说“Do something different”;我倒觉得似曾相识(我是不是又yy了?);只是目前还做得太少,没有多少心得。不过有一种传言这些德高望重的人多半是被逼着参加某某活动来撑场面的,谁又能指望他们在这种workshop上有新的idea呢?Hoare现在是微软剑桥研究院的,难道说……?看来我想多了。不过话说回来,即使没有什么实质的帮助,但鉴于这只是一个workshop,并且在场人当中不乏我这种业外人士;有一个重量级的人物在,并且还说了些,对我们总是有鼓舞的作用的。华师出力也不少,软件学院院长何积丰教授是中科院院士;后来才知道他和Hoare有过不少合作成果——这大概才是这次workshop在华师的最重要原因吧。

听讲座时我想起巴别塔这个词;尽管演讲者用的都是英语,但是还是可以凭各个人的口音(包括英国、美国的差异)大体推断出其国籍。而在用到各种术语时,经常存在两种概念几乎表达同种意思的时候,可双方都坚持用自己的说法;也有不少两种概念都用同一个说法表达的情况,谁都以为对方说的是自己的意思。这或许是上帝为了误导我们故意混乱我们的,可谁又能保证如果不存在这么多混乱这个领域可以取得现有的发展呢?语言或表述的不同的确给人与人之间带来了隔阂,那workshop大家都聚在一起是不是正是为了弥补交流的不便导致的误解呢?再想想,各种编程语言的存在是不是也给coder之间的交流带来了麻烦呢?如果没有这些语言的分歧,咱码农的世界又会怎样?估计早就没落了吧!!!flexible、efficient往往不可兼得啊。

另外我现在觉得Verified Software并不是最接近程序本质的东西,至少说从目前的研究结果来看是这样的;尽管检测程序的正确性是软件非常重要的部分,但现实的软件如此复杂以致我们根本没有办法有一套全面的验证方法来解决问题,大部分结果还都只是停留在toy一样的层次上。反之,这样一个原本应当非常形式化的内容,到头来却用到了非常多的工程上的方法。另一个让我稍有不可思议的是,这个领域的researcher们都尽可能回避函数式编程;程序验证这块在最符合图灵模型的命令式语言上还没有搞定,在函数式上的确更大打折扣了。可是,函数式语言是搞程序语言理论不可绕过的啊。

另一个感触,学术界的研讨果然太空洞了!看不见,摸不着;花非花,雾非雾,夜半来,天明去;总有种“幽暗昏惑而无物以相之”之感。这个感觉是否正确目前我还没法断言,但我感觉至少和老秦描述的他参加的几次开发者大会很不同。提问时有人指出在现实公司中没听说过真正使用到程序验证方法的(尽管事实上可以在小范围内有),这种类似砸场子的干活倒也引起了演讲者们的窘迫!到底有没有用,只能留给后人说去了;不过我有种不祥的预感(但由于我现在的立身出世,我希望我的感觉大错特错)。

在这个workshop能坚持一天的最猥琐的一个理由是这里有免费餐券,尤其是晚上的自助餐。貌似我现在已经有些习惯了这种蹭饭蹭住的生活了,终于可以揣度到贪官污吏们的心理了,hooray!不过还是感觉有些对不起微软,给我们提供了这样的优待,我却从来没说过她什么好话过,吃人家嘴软了?不过我承认绝不是IT评论中的那样吃干饭的,微软的研究院的确很牛逼,微软对软件工程功不可没(按道理我没资格评论这些>_<)。

感觉workshop上演讲者主要还是将自己的团队近期的成果(说白一点就是conference上已中的或待中的paper);如果本人不做演讲,参加workshop之前最好把感兴趣的文章多看几遍然后不懂的地方问演讲者。如果可以预测workshop中自己发言的机会很少,那还是离它远点好;把这当科普讲堂可走错地方了。

Nonsense Comments(2) Sat, 25 Aug 2012 00:54:44 +0800

编译原理学习笔记03

在字符粒度上,语法(syntax)就是词法结构(lexical structure);用正则表达式可以搞定对词法的处理。

BNF是CFG的一种表示方法,有这样的形式:

symbol ::= __expression__

其中symbol(三角括号不是必须的)是nonterminal;__expression__是一个包含symbol的表达式,仅可以由“|”连接;尽在BNF的右边出现的symbol是terminal。即只要在左边出现过一次,任何一个symbol就失去了成为terminal的资格。反过来看,现实世界其实只有terminal出现,任何句子、词语最终都是terminal组成的;nonterminal都只是便于理解加的中间层。

ABNF仅在BNF上加了注释信息,换汤不换药:

rule ::= definition ; comment CR LF

EBNF是基于BNF的一种扩展,按照wiki的定义有这些记号:

 

 

 

 

 

 

 

 

 

但是更多情况下涉及到的是下面的符号:

  • (token)       打包成整体
  • token?       $\le 1$个token
  • token*        kleene start,$\ge 0$个token
  • token+       kleene cross,$\ge 1$个token
  • .                 匹配任意一个token
  • ~token       没有token(即“非”)
  • a..z            a到z间的所有字符

具体是什么好像没有绝对的说法,只是为了便于表达;ANTLR用的是后面的说法。

 

BNF和EBNF可以相互转化,既可以用于lexer规则也可用于parser规则(这也可以从CFG比regex牛逼看出,而regex完全可以搞定词法)。

lexer规则(BNF左边)要么是literal要么是是其他规则的引用;parser规则可以引用词法规则、语法规则,也可以包含literal。比如下面这个例子:

decl : 'int' ID '=' INT ';' // E.g., "int x = 3;"
       | 'int' ID ';'          // E.g., "int x;"
       ;
ID   : ('a'..'z' | 'A'..'Z')+;
INT  : '0'..'9'+;

Programming Comments(0) Wed, 22 Aug 2012 21:18:43 +0800

一些胡思乱想

好久不扯了,原本想写点笔记类的,可被今天日子的重要性给打断了。今天这日子说普通再不过,可偏偏成了ICSE国内submit的最后一天了。开始不了解,直到琦哥说今天晚上就解放了,才知道他这些天都在忙paper,赵老师这些天都在不停地帮他改,晚上就要交了。不久看到程哥的微博,原来今天对于相关领域的researcher们来说真的大事啊。实验室里大部分人都应该知道这事,应该也不止一个人投了,我却连什么时候投稿都不知道。秦续业居然说我八卦,我的消息灰常闭塞好不好>_<

老实说原本不喜欢工程这个说法,在我本科的世界观里科学才是王道。读研选择大方向时避开了太底层的计算机体系结构又忽略掉偏应用的计算机应用技术而选择了计算机软件理论与应用。可到后来,才发现软件理论的很大一块是和软件工程相关的。比如我的师兄师姐们(好吧,师姐只有一个)投paper时总会考虑是投pl还是se,我自觉这很对得起stap中的t和p了(不过话说回来,我们毕竟不是搞纯理论的,尽管也涉及到理论计算机中的automata,cfg等概念,但并不需要特别本质的数理逻辑)。我以前一直犯了一个错误,在没有清晰的认识之前将科学与技术隔离得太远了——尽管我现在还是没有清晰认识,但我现在至少不会这么快下结论了。

我以前也完全不看好国内的学术界而非常崇尚工业界,现在这个观念淡泊了些。在知乎上看到有人问为什么非科班出身的人搞计算机行业比较厉害;看到这个问题我觉得幼稚了。在我遇到的科班出身的cser中,牛逼的人实在太多;像我这种半路出家的人,过招不过一下立即倒下。有不少人以为学术界的人比较菜,这当然是有原因的。一个原因大概和满瓶不动半瓶摇这个众人皆知的俗语相关吧。我认识好些牛逼的人之所以在网上没有那么高的名声只是因为他们觉得没有时间写博客什么的;他们或许有些看似不够高明的娱乐项目,但在现实中他们的人脉比很多人好,他们的作为比很多人都高。在现实中我了解到一些去cmu、uiuc的人、不少发顶级会议paper有重大研究成果的人,但是在网络中我看不到他们的身影。不过当真正看到他们在网上的动静时,很多情况下会发现他们的口味比工业界的重得多。比如前些天nature质疑叶诗文,就引起了不少scientists的评论。另一个原因我想是因为学术界的人的coding没有工业界人的多吧。因为学术界的人写代码之前需要顾忌code的意义:是否具有开创性,成功把握是否很高等;而在此之前,需要的是了解研究方向的理论基础,需要读大量的文献书籍。工业界中不少技术都是现有的,而程序员的工作大部分也是可以被复制的。让我感受最深的莫过于上算法课关于AKS算法作业了,听说上一级同学做的是实现AKS算法,而我们做的是对算法本身写一篇review。开始我还很惊讶为何学长学姐们完成得很好,而我们却很差。后来想想这其实理所当然:这和推导出$\pi$的公式与用公式求出其数值解不是一样的道理吗?我想还有一个原因是学术界的门槛比较高,想有所作为的话需要在一个特定的领域钻研很久;由此导致了狭隘的知识结构。按照这个说法,那些涉猎极其广泛的人其实很多是万金油罢了。另外,学术界中很多人做的都不是和end user打交道的,一般人难以理解;很多太过超前以致于很长一段时间内都没法被人所知。当然我一直承认不少计算机相关专业的学术界人水平真的很次,有些根本没有coding的观念,没有作为程序员应有的基本素质;这些人在一所高校占的比例足可以反应这所学校的垃圾水平。所以我觉得学术界最容易产生两种极端,而工业界很大程度上是填补中间的空洞的;如果按照保罗•格雷厄姆的说法,我觉得工业界更适合(培养)geek,学术界更适合(孕育)scientist。真正的牛逼公司正是寻找了理论与实践的最佳结合点,来引导行业的发展。

回归正题。这个原本就不存在的暑假快结束了,我这些天也经历了不少;而再过几天我读研就快整一年了。今天突然发现,这一年以来我的作息时间一直处于紊乱状态,偶尔的几天有规律的生活也没坚持下来。前两天陆续看到几篇关于程序员不会安排时间的文章,绰中了我的苦处。早睡早起方能养身,我的确到了需要用google calendar之类工具来计划我的时间安排了。

这几天总有个念头:我真的光明正大地折腾了一年的计算机了。但是这个念头给我带来的并不是那样的惊喜,原因究竟是什么我却不理解了——大概我心里并不甘愿做一辈子的码农吧?不管怎么说,我得好好为我以后做打算。

为自己的下一年定一个计划:

  • 投一篇ICSE/PLDI之类的paper,今年年底至少有初稿(加油!)。
  • 往我的github等repository上放10-20个有研究意义或实用价值的代码。
  • 每周至少写一篇有关Programming的文章。

死皮赖脸地写下来,这次必须动真格。

Nonsense Comments(2) Sun, 19 Aug 2012 01:05:46 +0800

七月的一些感想

这一个月来,对我一个从没见过多少世面的人来说发生了很多事情,尽管这些事对我摆脱窘境并没有实质上帮助;从这个月开始真正闲下来了,我产生了不少新的感悟,尽管这些胡思乱想我到现在为止都没法确信对我有利与否。

---------------------------------------------------

先是6号到10号当了夏令营志愿者。和那些大三的在一起的几天里,我感觉到他们都还挺单纯,见识都不够;看到大部分人的选择导师的原因不禁想笑。不过我想想我大三结束时的观念似乎还幼稚些。当时还在和家里人争辩是保研还是考研转计算机的事;对计算机的认识还只是“计算”和“机”的组合;还只是天真地认为有数学的基础搞起软件来自然得心应手;还只是固执地认为学好C++,走遍天下都不怕;还曾一度以为OS不难并简单地认为这是我感兴趣的方向;还只是以为理科和工科的思维方式很相似(现在我才知道这两者的区别几乎就是C和C++的区别);还天真地以为只有软件学院才是正统的计算机专业(当然我后来因祸得福,或许是傻人之福吧)……当然参加夏令营的学弟学妹们不会有我这样的异想天开,但是我怀疑他们很容易走上工科生会有的另一种极端。

当志愿者的几天里我总在想:如果我当时高考志愿选择了他们所在的学校,并且是软件学院或计算机系,现在的我至少可以不这么窘迫。想想高中时候的见识真的是太短浅,居然为了离家近并且误对南京死忠而放弃了更好的机会。但是又自然想到,如果当时我做出了现在看来最优化的选择,是否真会比现在好呢?概率上来说可能性很大,但现实的模型远没有想象中的简单。至少有些人,有些事是不会有了,正如《蝴蝶效应》中的那样;或处在另一个环境中我也许和高中一样对自己极端自暴自弃;或许我可能很早就有了现在的意识、但总摆脱不了三轮车追小轿车的阴影也未可知;或许我在不同的学校里会出类拔萃,在大四新的选择时可能比现在好很多但也可能面临更痛苦的抉择……其实我更怀疑的是这些可能性会交织在一起——毕竟我现在也没法确信我现在处于究竟什么状态,只是自我感觉用屌丝形容最为恰切。

参加夏令营的学弟学妹们大多比我性格外向,大部分人的口才比我好得多,且不得不承认他们比我见多识广些;这可能和理科、工科学生的思想有差异,但是我更倾向于认为这和出身关系更为密切。教育门槛的降低给人们的一种错觉就是人与人之间的差异可以明显地变小;然而事实上变化的部分远远小于一般人所想像的,至少远不是我的父母以及我所想像的。从小我被总被灌输穷人的孩子早当家这样的说法,总以为乡镇里的人比城市里的人更容易有“出息”。然而我现在才知道在统计角度来讲真实情况和我以前的一厢情愿正好相反。事实是,城市里的孩子比其他人出路一般要好;而好的学校里成长于城市的学生明显要比乡镇里来的多——于是这形成了一种隐形的等级,大多数人都心知肚明但只是不说罢了。我以前一直以为这是个别现象,也曾经认为这不公平;现在才意识到自己无知:公平是相对的,很多事需要透过现象看清本质。乡镇出身的孩子的父辈们很多文化水平不高,有些目光短浅;而周围的父辈们都是这样的,他们的孩子所受的教育自然不比城市里的了。我从来没有瞧不起这些父辈们的想法,也不能公正评价城市人和乡镇人的生活方式孰优孰劣。然而当我们要接受更高等的更好的教育时、要接受更好的物质生活时我们需要在城市里并尽力融入其中,那我就不得不承认在这样的价值观驱动下人的立身处世其实是很重要的,尤其是早年所受的教育。比如两个本来就期望过着城市生活的人,来自城市的当然要比来自其他地方的人感觉自然许多了;而如果他们都想过着田园生活,自然来自农村的要习惯得多。但事实上我们大部分会选择前者;在这样的劣势之下,我们只好更加努力,以换取将来的子女辈们好的出身;然而今天很残酷,明天更残酷,后天很美好,大部分死在了明天晚上。即使能坚持下来,很多情况下仍然没有办法去超越从小接受良好教育的孩子;因为他们可以比其他人少考虑很多而更加专注、更少怀疑——尽管这比其他人少了些阅历和思考,但是谁又能说这些经历一定利大于弊呢?没伞的孩子只能快跑,有伞的孩子何尝不能快跑?残酷,但是这是事实;想改变的话,别无他法。

​---------------------------------------------------

12号因为实验室的项目去北京,而我则像是刘姥姥进大观园一样怀着膜拜的心到了帝都。我只因为出生和求学而待过江苏和上海;每念及此,都感到失落。我曾经也不自觉地把这和出身联系起来了,但是每次想到锋哥我都觉得我的想法太不靠谱。锋哥出身并不比我好,但高中就去过北京参加北大自主招生了,又因为竞赛到了其他好些地方;本科期间还当了少年班的班长,他们同学聚会他去的地方想必比我多很多;而如今到了全美排名第一的医学部,而我还处在水深火热中,阅历和我自然不可同日而语。其实本科虽然不算好但是还是有很多机会的,只是我没有争取罢了——大部分情况下是对自己没有信心吧。考研面试的前期我的最大的感触就是我的阅历太浅,很多展示自己的机会都错过了;我总以为参与项目或活动如果失败对我会有很大的负面影响,可是却不知道不参与才是真正最大的失败。在北京见到了两个四年不见的同学,他乡遇故知,感慨很多大部分却说不出来。有一点似乎我们都达成了共识:以前太肤浅了。三个人明显没有了高中时的骄傲,究竟是好事还是坏事?总想起小时候吹的牛逼,现在感觉实现起来这么困难。不过我总算有点孔子登泰山而小天下的感觉了;希望虽然渺茫,但是不是我所想像的那么小,是吧。

​---------------------------------------------------

在这个月里,我还做了一件看似微不足道但对我意义较大的事:我取消关注了微博上的大部分技术牛人和其他公众人物,而保留下了可以和我交流的人。微博并不是一个很好的交流平台,而新浪的意图是想建立一个等级森严的环境。我毫不怀疑微博给国人的心智思想的发展有很大的帮助,但是我对大部分话题已经不感兴趣了。以前我总以为微博使得个体和他/她心目中的偶像拉近了很多,但事实上想了解并理解一个人仅从微博无异于盲人摸象;偶像的回复有时候并不是真心的。140字从来都没法阐述完整的思想,最多只是断章取义或碰巧心有灵犀;而有些话居然还是粉饰了的;字数限制决定了它是人与人之间的私下交流的工具而不是广播的好方式。然而官方却坚持名人堂的做法,转发和评论的机制始终难以建立对等的交流平台;不得不说这符合中国国情,不过并非对每个人都适合。基于类似但稍有不同的理由,我取消关注了豆瓣上一些人(尽管豆瓣的sns气息要弱很多)。以前我以为只要控制好所关注的人,豆瓣文艺只是传说;然而我现在知道文艺的大环境下谁都不能保证不受渐染。不过取消关注一些人的最根本原因是我要读的书列已经让我觉得或许怎么也没办法读完;而我现在所需要做的是“专”而不是“泛”(比如我现在就不会花那么多心思再去学去用haskell);豆瓣上的有些书评和影评很多有文艺之嫌,若非自己了解的人的推荐极有可能受表象蒙骗。我加大了博客的订阅数量(当然这终非长久之计,最终所需要的是根据自己的学识优化我的订阅内容);我还增多了和博主的交流(尽管大部分是请教)。只有长篇才可以完整地看透一个人的技术水平和思想见识,也只有更为正式的文字才需要融入更多的思考。另一方面我开始使用twitter,主要用于记录我平时的一些不成系统的胡思乱想,并肆无忌惮地和人交流(微博和twitter的不同倒有些像指令式和函数式语言的差异了^_^)。

​---------------------------------------------------

接下来的日子没课了,可不能闲着。大四时的一个信念是考上研离步入正式工作岗位至少有两年半的死缓;现在看来宏观上讲基本还对。原本以为可以通过纯学术的研究提高自己的水平而实习只作为辅助可有可无,现在看来这其实不够现实——当时只是一个理科生的思维在作怪罢了。科学和工程技术是息息相关的,实践和理论往往需要结合得很好。数学真的算不上科学;计算机科学与技术做多只有1/4的科学成份,软件工程却几乎是技术了。这一年来,给我最大的感触还是实践太少。不过真正让我有找实习的心的还是家境的原因和琦哥的提醒。现在想想我还是很幸运的,如果当时考研不成功的话,或许我就再也没有机会东山再起了;现在虽然窘迫,但是对我来说都还可以承受。上个月中旬投了简历到琦哥的部门,二十八号他的同事电面我了;情况很糟糕,非常囧;而琦哥当时就在同事旁边,后来听他说起我都感觉抬不起头。周围实习过的人很多,同室的老秦是导师推荐去的,王正也找到了,王俊也接有项目并且paper有了着落;而琦哥大一开始就可以自给自足了,现在已经有不少结余,paper也要发了;而我认识的李垚大牛大三结束跑到微软实习去了;而爽爷和我的另一个高中同学到了阿里巴巴了;实验室的其他几个哥们也都有可供补给的私活;似乎只有我成了啃老的闲人。另一方面,我的研究却迟迟进行不下去,真是心如刀绞。

这个月变得对bbs的parttime特别热衷,总是有种不管三七二十一投简历的冲动。然而,招聘启事的内容总让我比较心寒;和专业相关的虽多,但是我懂的却很少。尽管如此,也无可奈何;打肿脸充胖子在所难免,毕竟据《疯狂的程序员》所载IT行业的码农前辈们就是这么过来的。有不少是短期的兼职项目,联系上一个了解情况后才知道不懂C#.NET的我根本没法胜任;还有些当枪手的任务,虽觉无耻但也试过,最终还是放弃了。有过两次创业公司面试的机会,之所以有机会纯粹是因为研一上学期软件工程课接触过android平台,让我情何以堪。

一个情况还不算太差,只是问了些java se的基本知识,android的倒问得不多;面试的人是电院的前辈,很友好。另一个公司是这位学长推荐的,面试我的人事实上是两个人,按照我的猜想应该是一个学弟和一个学长!我首先被学弟揪住我的简历问得昏天黑地,从STL,MFC,java容器到数学建模;后来学长又问了adb、openCV、.NET、jQuery、DB等我完全摸不着边的东西。学长最后的意思是原本误以为我对android熟悉但发现我的火候还不够,Windows下的开发我又不了解;不过他还是给足了我面子,待我很亲切。在明白我不能胜任他们的工作之后,我也自报家底,尽吐苦水。

在被第二家公司面试的前一晚(前天)和另一家公司联络上了,不过还没给面试的机会。和我QQ交流的大哥(应该是男性吧)待人非常诚恳,我感觉很靠谱;不过他们的要求是面试之前先完成一个基于spring MVC的Web应用,而我之前从来没有过这方面的任何经验。大哥很好,没有给我限定期限。但是在我有了第二次面试经历并且想那位学长诉苦之后隐隐感觉我们实验室所做的的确太不适合创业公司了(翔哥除外,他本身就是多面手);所以对这个考验自然就没多少信心和勇气,中午狠狠地睡了一觉。

下午突然接到一个电话,是英特尔打过来的;原来是我20号那天投过的一个测试与质量保障部门。刚睡醒的我感觉有些突然,于是请求等待半个小时。我感觉这次又要挂了,老秦在旁边给我打气——“没事儿,遇到不懂的偷偷上网查,我也可以用耳语帮你”。好吧,在经历了几次被其他部门默拒之后,我也淡定了;破罐子破摔,该怎样就怎样吧,都是个人造化。是两个人一起面试我的,主要是一位女士;她没有问我很多技术上的问题,只提到了Python的几个小知识点,然后是测试的一些基本概念,我如实的把我所知道的以及老师、师兄们和常姐讲给我听的都给讲了一通。后来朱女士看到我本科是数学专业,居然问我泛函分析、微分几何的东西来了(后来听她说才知道她也是数学系出身);原本已经快忘光了的我只好使劲在脑海中反复回想。另一位先生开始问了我死锁的条件我只答上了两个,其他还有关于Python中tuple和list的问题我也答错了一些。问的过程中我已经抱着必死的心了,没想到最后朱女士居然说有意招我,并问我有没有什么问题。峰回路转,柳暗花明;真觉得不可思议——大概是我的几个数学问题回答得还不错,再加上我们实验室的确和测试有些渊源,而他们的确很缺人吧。两位面试官对在整个过程中都很和气,朱女士后来还发了一封邮件给我,真的打心眼里感激;其实上次琦哥的那位同事大哥也蛮和气的,只是我实在回答得很窘迫而感觉气场完全被压下去了。

不过他们最后需要实习生所属的导师同意。这件事却成了我这次能否成功实习的关键。陈老师在听我讲述了我的情况之后同意了;但赵老师不赞成这么早的实习,他更希望可以花更多时间用于实验室的研究方向。我能明白老师的苦心,因为我总感觉我的确有毕不了业的风险,而实验室的要求又相对较高,出paper不容易啊。之后老师们和我对此事又商量了好久,最终同意我三个月的实习时间。我把这个情况回复给朱女士,希望她能够在下周一上班时给我肯定的回复。她们可能不会满意这样的结果,谁不希望招收长期的实习生呢?但是不管接下去情况怎样,我找实习的事都会就此搁下了。我不会责怪别人,而只会在接下来的死缓期里强化自己的专业素养;这个时期对于我今后来说至关重要,而如果能有所突破并有新的不可思议的机遇那就更值得了。不过我还是捣鼓了一天多的基于spring那个留言板系统;尽管有周围同学的帮忙,但也不想总麻烦别人;进度非常慢,tomcat、jsp,ioc,mysql等都是从零开始。今后肯定还是需要不少这种没有系统的目标导向型的即时学习,但是对我来说真的还是太勉为其难。晚上我回绝了那位令人尊敬的大哥;他说了些鼓励的话,我感觉我又一次有负于人了。

*************************************

今天英特尔那边有了答复,三个月太短,拒。同时也明白了他们之前接受我大部分是因为我可能有很长的实习时间。没办法,看来我以后要做事要纯粹些了。

*************************************

​---------------------------------------------------

身如不系之舟,以前也有过这样的感慨,如今的感觉更深了。总觉得现在的处境很令我无可奈何,有太多的事是我无法决定的;但能有什么办法呢?只能说:没有伞的孩子,快跑。

Nonsense Comments(7) Sun, 29 Jul 2012 01:50:50 +0800

quicksort探究1

龙书的P431中有一个quicksort的不含嵌套函数及高阶函数的例子,我实现的时候居然错了,真的太菜了。虽然整体的思想都是让问题退化为解决枢轴两边的快排问题,但是在处理细节上是不同的。虽然基础,但是好记性不如烂笔头,还是硬着头皮写下吧>_<

方法一

public class Qs {
	private int[] numbers;
	private int number;

	public void sort(int[] values) {
		if (values == null || values.length < 2) {
			return;
		}
		this.numbers = values;
		number = values.length;
		quicksort(0, number - 1);
	}

	int partition(int low, int high) {
		int pivotKey = numbers[low];
		while (low <= high) {
			while (numbers[low] < pivotKey) {
				low++;
			}
			while (numbers[high] > pivotKey) {
				high--;
			}
			if (low <= high) {
				exchange(low, high);
				low++;
				high--;
			}
		}
		return low;
	}

	private void quicksort(int low, int high) {
		int i = partition(low, high);
		if (low < i - 1) {
			quicksort(low, i - 1);
		}
		if (high > i) {
			quicksort(i, high);
		}
	}

	private void exchange(int i, int j) {
		int temp = numbers[i];
		numbers[i] = numbers[j];
		numbers[j] = temp;
	}

	public static void main(String[] args) {
		int[] arr = { -4, 4, 3, -1, 2, 1, -3, -2, 0 };
		Qs qs = new Qs();
		qs.sort(arr);
		for (int ele : arr)
			System.out.print(ele + " ");
	}
}

方法二(修改方法一中的partition和quicksort)

int partition(int low, int high) {
		int pivotKey = numbers[low];
		while (low < high) {
			while (low < high && numbers[high] >= pivotKey)
				high--;
			exchange(low, high);
			while (low < high && numbers[low] <= pivotKey)
				low++;
			exchange(low, high);
		}
		return low;
	}

	private void quicksort(int low, int high) {
		if (low < high) {
			int pivotKey = partition(low, high);
			quicksort(low, pivotKey - 1);
			quicksort(pivotKey + 1, high);
		}
	}

注意细节即可,这里就不演示了。想了解一下细节的话可以加断点细细分析;或者加些aspect的信息来看一下。下面是直接用aspectj插入的一些信息:

public aspect QsAspectj {
	
	private int callDepth = -1;
	
	pointcut MethodInfo(int low,int high):call (* *(..))&&this(Qs)&&args(low,high);
	before(int low,int high):MethodInfo(low,high){
		callDepth++;
		System.out.print(callDepth);
		for(int i = 0; i< callDepth;i++)
			System.out.print("   ");
		System.out.println(thisJoinPointStaticPart.getSignature().getName()+"("+low+", "+high+")");
	}
	after(int low,int high):MethodInfo(low,high){
		System.out.print(callDepth);
		for(int i = 0; i< callDepth;i++)
			System.out.print("   ");
		System.out.println(thisJoinPointStaticPart.getSignature().getName()+"("+low+", "+high+")");
		callDepth--;
	}
	
	pointcut sortInfo():call(public void sort(int[]))&&within(Qs);
	Object around():sortInfo(){
		long begin = System.nanoTime();
		Object result = proceed();
		long end = System.nanoTime();
		System.out.println("total time: "+(end-begin));
		return result;
	}
	before():sortInfo(){
		System.out.println("*** "+thisJoinPointStaticPart.getSignature().getName()+" ***");
	}
	after():sortInfo(){
		System.out.println("*** "+thisJoinPointStaticPart.getSignature().getName()+" ***");
	}
}
为了无聊起见,顺便插一段scala的实现,剽窃自这里
class Quicksort {
  def sort(a: Array[Int]): Array[Int] =
    if (a.length < 2) a
    else {
      val pivot = a(a.length / 2)
      sort(a filter (pivot >)) ++ (a filter (pivot ==)) ++
        sort(a filter (pivot <))
    }  
}

object Quicksort extends Application {
  val qs = new Quicksort
  val a = Array(-4, 4, 3, -1, 2, 1, -3, -2, 0)
//  val start = System.nanoTime()
  val sorted = qs.sort(a)
//  val end = System.nanoTime()
//  println("total time: " + (end - start))
  sorted.foreach(n => (print(n), print(" ")))
}

貌似这样的做法不怎么高效(不妨看看运行时间),但鉴于我的scala还只勉强达到入门级,如何改进还得以后再说。

Programming Comments(3) Tue, 17 Jul 2012 21:57:43 +0800