说一说Wanting的历史~~~

注:长文,4000+,没有兴趣的还是不要看了~~~
 
Wanting的研究已经正式告一段落两个月左右了,现在讲一下情况。因为太古老了,我现在都要借助笔记本来说了~~~
大概是2005年三四月的样子吧,那时候我们刚刚高一下学期。有一个晚上我回到宿舍以后没事可干就站在寝室外边发呆。那时候周伟俊(以下简称Sec俊)跟我还不算很熟,也就是同一个宿舍。然后他就突然走过来问我关于烷烃异构体枚举的问题,问我有没有什么好主意。我现在还搞不明白为什么他那时要找我,因为无论在数学还是程序方面我在我们班都远远不是最好的,可能是我各方面比较平均,Sec俊不用翻译术语的缘故吧。然后我就回去想,想了几个主意,第二天就跟他详谈了一下。烷烃异构体相信大家高中都学过,不记得的就去Google一下吧~~~
那时候Sec俊的方法很原始,就是蒙特卡罗法,通过对查表得出的数据再乘上一个倍数,生成这么多的符合条件的树之后再来比较它们有没有重复,重复的就删去,最终就得到了一些不重复的异构体。可想而知,这种方法不仅结果容易错误,还很麻烦。我们都觉得要避免这种方法。
我的提议是:先生成含有n个碳原子的烷烃异构体,再通过“粘上”一个原子的方法来生成含有n+1个碳原子的烷烃异构体。这就是类似于数学归纳法的方法,比蒙特卡罗法效率要高一些,而且不会出错。经过商议以后,我们都觉得这种方法很不错。但是,使用这个方法有几个难关。第一是想到一种表示烷烃异构体的方法,第二是想到一种最快判别两个烷烃异构体是否同构的方法。很容易看出来这两个问题其实是相关的。我们讨论得出的结果就是:关键是找出图里边一个唯一的标志,这样就可以通过这种方法唯一地表示一个烷烃异构体了。
后来我在一个有点不正常的场合想到了解决的方法。那是一节体育课下课以后,我们去做课间操。因为Sec俊在刚刚的体育课上被冷落(包括我在内),所以我觉得有点对不起,所以就在一边埋头想东西,突然就想出来了一种找出图里边唯一的一个点的方法。后来我跟Sec俊讨论了一下,发现很可行,于是就用这个方法写了一个程序,当然那时候还是用邻接表来表示烷烃异构体的,结果效果不错。后来想啊想,又想出来了一个用字符串直接表达的方法,那时候我们还没发现这个表达法的精妙之处。
那时候我刚刚接触分布式计算,对这个很感兴趣。再加上烷烃异构体的枚举所需的运算量是很大的,所以我想:能不能利用分布式计算来枚举烷烃异构体呢?那时候我对分布式计算了解得并不多,所以想了几个现在看起来很拙劣的方法。然后我们两个商量了一下,决定去找黄秉刚老师问问我们的这些个东西他会觉得怎么样。
那天,根据我们的笔记本来说是2005年5月13日。在他的建议下,我们非正式地立了一个项目,然后我拿了一个笔记本出来作为研究的记录。这个笔记本后面沦为涂鸦、互相郁闷和草稿纸这件事,暂且就按下不表。在非正式地立了项目以后,我们就拿出更多的时间来研究了。
后来进展顺利,因为笔记本没有记录日期所以就算了。首先是发现一个图如果有两种可能的字符串表达的话,那么这两个字符串就会有内在的联系。发现了这个,就相当于我们以后可以直接比较字符串来知道对应的图是否同构。后来是知道了如何绕过图直接在字符串的形式上添加结点,这就使我们摆脱了麻烦的邻接表。经过这些进展,我们的程序速度快多了,但是我们还没有满足。这两个阶段的程序代号分别为WTGraph。
后来,我又想到了一个方法,就是把烷烃异构体分类,分成几大类粘贴结点的时候不会重叠的类,大大加快了速度。这是因为每生成一个字符串都要判断是否重复,就要跟前面的比较,这是很费时间的。要比较的东西少了,自然速度也快多了。后来Sec俊和我就写了那么一个程序,代号是WTStr。经过艰苦卓绝的调试以后,程序正常运行,结果正确,我们那是极其高兴。
看了运算的结果以后,我发现很多字符串它们有很多相同的部分。我想:能不能好像堆积木那样把那些重复的东西拼在一起组成整个烷烃字符串呢?后来我们经过推敲,觉得可行,于是Sec俊就写了一个程序。调试成功后发现这个程序的用时比以往少了很多。后来我又做了一些证明,证明这种方法的用时的递增程度是几乎最佳的,最多就跟最好的程序差一个常数。后来的事实证明的确如此。这个程序的代号是WTPart。那时我们用数据库来储存目录。我一直觉得这样子肯定很慢,想劝说Sec俊重新编一个直接在内存里边存储的程序,但是他说他尝试过这样子做但是好像不成功,写出来很慢,于是我就打算有空的时候自己来写,没想到一拖就是一年。
当然,这个东西写好了以后,我们并不是闲着没事干的。我们要开始接下来一项更为浩大的工程:写论文。为什么说写论文是一项浩大的工程呢?因为那时候我和Sec俊都没有写过什么像样的论文,完全不知道论文是怎么样写的。为了写论文,我还专门在网上下载了几篇学术论文来看,看完以后就硬着头皮也写成了一篇。可想而知,这篇东西看起来不像论文,倒像是科普文章。然后黄秉刚老师在看到这篇东西的时候提出了很多很多的意见,比如说哪个部分该放在哪里,详略问题和一些字词的问题等等。反正我们是一窍不通,就按照老师的要求改啊改,越改越觉得不通顺:怎么有点像王婆卖瓜啊。黄同志说:这就是现在创新大赛的规律云云(原话不记得,反正这是我领会出来的意思)。我们两个心里都觉得不爽。后来有一个什么创新项目与专家交流会,那时候我们拿台电脑拿个笔记本就去了。那时候还有很多别的项目,反正我们有两个人而我们要对那些专家讲的东西很简单,于是我就去看别人的东西,让Sec俊留守。看了几个项目之后我就知道为什么黄同志会这样说了。那些项目都是应用性的,当然要多多“卖瓜”。但是有一些比较有趣的东西是(这时后来听别人说的),有一个项目有关计算机的,需要编程,然后有人问那个搞项目的用什么语言写,他说是C++,但内行人一看他的代码截图就知道是C#,这种项目我都不知道说什么好了。这样的项目当然要依靠论文里边玩弄辞藻(说白了就是搞虚的)来吸引注意力了。那我们也迫不得已要随大流了。那些日子改论文真是辛苦啊,要拼命写虚的进去。
不过在改论文的途中,我们并不是别的什么都没有做的。我们那时候走了一个很大的弯路:尝试把算法改造成分布式计算。后来对算法的真正详细分析表明,这个算法只适合做一般的并行算法,对于分布式计算来说它需要的储存空间太大了,收集结果的服务器不可能拥有这种带宽。这也是一个例子:有时候研究一样东西的人可能并不完全了解这个东西,即使这个东西是他发明的。老实说,这个算法的潜力是我在后面才慢慢体会出来的。除了分布式计算这个尝试以外,我们还写了几个将字符串变成图形和国际命名法命名的程序,这都是为了看论文的人和我们解释方便的。
12.6,对我们来说是黑暗的降临,伴随而来的是噩梦般的工作。其实不是工作多和辛苦的问题,而是要违背自己意愿写很多很多的东西。我们是很愿意干重活的,比如说我们想算法和写程序的时候其实干了更多的活,但我们乐在其中所以不觉得辛苦。这回这样子让我们觉得很不爽。尽管我们做了这么多的委曲求全,那些所谓“专家教授”看完我们的论文以后第一个问题不是问我们这个算法具体实现如何如何,却是一个在我看来很有点弱智的问题:“你们这个研究有什么意义或者应用价值?”我们两个当场差点昏倒,这竟然是我们这个国家里边处于研究一线的人物能问出来的一个问题!那只能说明他们根本想的不是科学,科学研究的好坏不是用应用价值来衡量的,而是用独创性来衡量的。这种人我只能说他们太聪明了,不适合做科学研究(看不明白的翻翻刘慈欣《三体》的第一集),商人或者政客比较适合他们。这以后也间接导致了我去法国的决定。我不知道法国怎么样,但我知道中国(看不明白的再去翻翻《三体》讲伊文斯的一段)。好了不说太多了,那段东西我记得这个Space里边有记录,看的时候注意从字缝里看出字来。
后来改啊改,改得昏天黑地,勉强送到了市里边比赛。在这里边还有一件令我们很不爽的事情,就是学校为了增加项目能进入更高一级的机会(这样学校就更有机会变得“光荣”了),让我们签了一份协议书,说如果要学校的策略要求项目变为个人项目的话,Sec俊就要放弃权利。这个令我们很不爽,因为这毕竟是两个人的项目,这样做是绝对不妥当的。我对这个发的一点议论可以在这Space上找到,最近的。
其实当我看了那些专家教授们的表现之后我就对创新大赛没什么信心了,所以后来一个多月后黄秉刚老师来找我们说这个不行,我们很平静地接受了。正所谓希望越大,失望越大。倒不如不抱任何希望的好。
几个月之后,大概是高考的一段,很不幸,上面的格言得到了正面的证明。关于这一段我已经在Space上面写过一些,参见《事实·缘起》和《无梦再期望》。那段时间我比较消沉,好在较为不消沉的Sec俊把我拉了出来,merci!
经过那么一次打击以后(其实回想起来也算不上什么打击),我又去想别的东西了,比如说3x+1,还取得了一些可喜的东西。但是在我心目中,这个项目还有一个地方没有完成,就是基于内存的程序。后来9月末十月初的时候我就把它搞定了,那时候也是很高兴,因为项目终于完完全全搞定了。于是我就叫上Sec俊和黄同志来看上帝~~~看了新的程序以后Sec俊很高兴,然后他就去查烷烃异构体的枚举的论文,因为我们是没有怎么认真看过网上的论文的,结果发现1991年的时候有人用类似的方法已经做过一个枚举烷烃异构体的程序了。他的方法更胜一筹,因为他用了一个数学定理,利用了我们没有利用的树图的性质,当然会做得比我们好。不过我也没怎么灰心,因为就两个相对来说很忙的中学生来说,做出来这样的成绩已经是不错的了。黄同志则对我做的3x+1优化比较感兴趣,不过那是题外话了。Sec俊还找了一个几百页的英文pdf,都是关于化学分子枚举的。我到外面把整本书打印了出来,看了以后觉得学到了不少的东西。
本来项目已经完成了,这些东西也应该告一段落了,但是前几天(!!)黄同志又QQ我说有一次机会去不去。关于这个也可以在最近的文章里边找找。反正前几个晚上在学校已经把所有东西都搞定了,我也不抱有任何希望。不抱希望就不会失望了,哈哈~~~
回想起这段历程,有有趣的事,有失落的事。曾经,我跟Sec俊在网络中心写完程序已经很晚了,在饭堂两个人以5分钟的高速度吃完一顿饭,我吃饭的速度也是那时候练出来的;曾经,我们填mt的申报表的时候民科豪在旁边瞎出主意,最绝的是我们接受了他的建议;曾经,我们拿着论文去拜托Kelly看,Kelly花大力气看完却不怎么明白,但是他还是尽力给了几个有用的建议;曾经,我拿着论文去给老李看,老李几乎不看时我的郁闷神情是可想而知的;曾经,我们在想算法的时候忘我地大声讨论遭到了众人的谴责;曾经,我们在本子上一边互相郁闷一边讨论;曾经,我们在开完所谓专家大会之后在宿舍外边大声笑骂那些混账的专家;曾经,因为调试成功而欢呼雀跃,因为遇到难题而苦思冥想;曾经,我们两个在寝室外边因为失落而叹气;曾经,我们跟黄秉刚老师讨论来讨论去;曾经,余超把论文抢去看,看了半天看出了道道来,还给我们几个建议,可惜都不是新的……一切一切,太多太多了。可惜一切都已经成为了曾经。不过我还是感谢这个项目,因为它使我成熟了起来,也使我交到了很多朋友。
向下一个目标进发!!
Advertisements

2 thoughts on “说一说Wanting的历史~~~

  1. 说实话,我很感动。文杰的文字尽管从来不用华丽的词藻和深沉的主题(应该说是不会用和没有),但正是其内涵,使得很多人都有似曾相识的感觉。尤其使我惊异的是wanting中原来有这么多奇思妙想……我觉得如果某某大赛可以用这篇文章来做论文的那该多好……外,3x+1你在说角谷猜想吗?

  2. @Dark Mader
    的确是角谷猜想~~~之前对别人的一个关于这个的分布式计算程序作了一点优化~~~
    详见www.equn.com/3x+1, 还有我记得我这个Space上面也有写过关于这个的事的~~~

发表评论

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / 更改 )

Twitter picture

You are commenting using your Twitter account. Log Out / 更改 )

Facebook photo

You are commenting using your Facebook account. Log Out / 更改 )

Google+ photo

You are commenting using your Google+ account. Log Out / 更改 )

Connecting to %s