刚刚参加的百度执行资格赛第一场很遗憾的未能提交。

最后5分钟发现bug，然后找出来改好的时候，已经过去2分钟了，于是我很遗憾的失去资格。

原因很简单，我用的set<const char*>来记录水果名（题目见百度官方网站，第一场第一题），我以前好像看过const char*是默认支持的元素类型，就没有重新定义比较算子，结果我错了，如果不定义比较算子，set就会按照char*在内存中的地址来排序，结果就是我的集合无法进行交，并操作，因为同样的文本的下标不同。

我太疏忽了，一开始我仿照sgi文档的写法，都是重定义比较算子的，后来嫌麻烦就省掉了，结果就不行了。我对stl掌握不熟，被模糊映像刷了一道。多2分钟，这20分我就能拿到了。而这次比赛，刚开始浪费了5分钟，没登录，中途出去把东西递给别人，花了大概5分钟。

觉得很遗憾，但是又无可奈何。明天如果有时间再去做第二场。

今天中午赶回来参加了第二场比赛。

第一题很简单，不过还是做了很久，40分钟左右之后提交。

然后做第四题，花了很久在处理字符串上面，用了set来保存站点，url，和查询信息。最后拿出来金老师的数据结构书开始抄KMP算法，无奈很遗憾的时候，抄完已经比赛停止了。啊，胸中无限憋屈！最无奈的事情就是程序做出来了但是没有数据测试是否正确，仅在那种小规模下的跑跑根本没有成就感，输入数据还没有代码十分之一长呢。

不过，看来我的确还不够强啊，估计肯定有人能够在2小时内完成2题的吧。这就是编码能力的差距啊。我还需要练习。

ps：很大时间花在字符串处理上了，如果会用string类就好了，如果string.find是kmp查找就更好了。

今天中午收到了Tshirt和证书，哈哈，还是很开心的。虽然花的时间不很多，也就10几天的样子，收获还是挺大的。

总结一下，参加imagine cup总共收获xp正版序列号一个，vista business正版序列号一个，Tshirt一件，微软的证书一张，哈哈

微软如果早点说有Tshirt和有正版序列号的话，我当初宣传也好做一点。

这次imagine cup第二轮实在是没时间参加了，几个作业压下来，自杀的想法都可以理解了。下周又要开始接口硬件实验了，头痛。。

明年的imagine cup还是可以好好准备一下的，大四可能会有不少时间。

昨天把八数码问题用转到C#上再实现了一遍。总的感想是，有的地方没有C++方便，大部分时候还是用起来很爽的。

C#的模板和C++的stl比起来，要少的多，所以刚开始究竟选什么模板想了很久，也去网上搜索了不少，总的感觉是讲的不清不楚的，msdn上也是这样。C++里面我是用set来做openlist的，C#里面好像要用SortedDirectory or SortedList， 这两个模板函数基本上一样，而且都是key/value类型，最后我用的时候才发现，sortedlist在频繁插入的时候效率要低的多，至少耗时超过sorteddirector5倍，我等了很久，等不下去了。(当然，这是在程序写错了，忘记排序情况下，导致复杂度超大的关系）

在重载比较算子的时候，遇到了很大的麻烦，找了很久才找到示例程序。想想SGI的文档，真的很温馨啊。C++的stl真的是用了都知道好啊。不过C#最后不需要释放内存，省了不少工夫。

最后程序写好了看，C#的耗时和C++比并没有明显的滞后，可能复杂度还不够高吧。不过C#程序装载的时间的那段延迟很明显。

写好以后，我上网找了个DotTrace，据说是。net平台的gprof一样的东西，可以分析profile。用了之后发现果然是个狂好用的东东，比gprof好用的多了。而且功能做的相当的人性化，点击函数名还能出现代码，神了。看看分析报告，有一半以上的时间都在读文件上，这我就没办法了，不知道。net怎么做的，读文件花了这么长时间。streamWriter效率很值得担忧啊。其他部分耗时都很少，几乎可以不用考虑优化了，不值得。

看看DotTrace的华丽界面吧。

看来问题不多，我就答一下。

问题：

1.如果让你用生命换一个愿望，你会许什么？

更多的生命。

2. 你觉得这个无聊吗？

玩多了就觉得无聊了 。

3. 食堂的饭什么时候才能好吃一点啊?

刚报到的时候。

4. 你觉得被别人爱比较幸福，还是偷偷的爱他（她）会更幸福些？

同时会比较幸福，但是我常常只能后者。现在成仙了，连后者都时续时断了。

5. 对我的第一印象是怎样的？要详尽哦！

胖胖的（不要生气哦），怪机灵的，小脑袋里面在想什么呢？

6. 自己最向往的地方，国内外都行

自己的家 。

7. 你会觉得有物质而没有感情的婚姻无所谓吗？

不会 。

8. 你觉得人为什么越来越虚伪?

一切的计算都是为了更好的获得利益 。

9. 你知道谁能解释富士山下的歌词么？：）

富士山下，沉寂的火山灰，能长大大的苹果，好好吃啊，好好吃！

10. 我最大的优点是什么？哈哈

有理性 。

决定不做恶了，所以不点别人了。

今天组织的实践项目宣传会相当的失败，只有一个人来听。

从周三借的教室，周四晚上打印的传单，周五中午在三个食堂发了288分传单，但是效果确是零。成本总共花了15块钱左右，还有制作传单，以及找打印效果比较好的店打印，然后分切，最后我手工把边上的空白剪掉，加起来大概3个小时，另外，还有3个人力*10分钟的分发传单，cm准备了一周的演示。传单做的还是挺漂亮的。

然而，实际的讲来，今天的确有很多因素导致来的人少。一方面，今天是周五，大家都想玩，这种学术性的活动吸引力肯定没有周五的电影大，另外，今天有太多的活动分流，还有大一新生都喜欢的电影播放。第三，我们的宣传肯定不到位，我们周五的活动，周五中午才开始宣传，也许早点宣传会更好。第四，我本不赞成这个活动，虽然我做的过程中曾经相信会有人感兴趣，在我做出传单之后，我天真地以为这样就够了。也许帖海报真的会好点。

除了上述原因，我还发现一个很重要的前兆，本来我可以考虑改时间的但是我没有。那就是上周技术部开会的时候，没有人周五有时间来做。我们的这次活动的目标受众就是像我们社团技术部的人那样的学生，我们技术部的人没有时间，那么很可能大部分我们的目标受众也没有时间，据说大一马上就考C++，有的专业还要考物理的，如果我早点注意到这点，我可以把这个活动延迟或者干脆取消，至少可以节约人力物力。时间因素绝对是很大的影响，谁会在考试前夕来参加这个活动呢！老实说，如果这个活动不是我组织的，如果我不是俱乐部的，我也不会去参加这个活动，因为下周二还要交体系结构实验，我还有yacc实验要做。

铭记这次失败！

这2天做了这个程序，做的比较曲折，本来想用stl里面的优先队列的，后来发现优先队列不允许修改值，最后只能改成排序。其实费波纳契堆最好了，但是没用起来，我以前写的那个费波纳其堆比较适合于定义了<=符号的类型，我想类型重定义的，但是指针类型重定义出现语法错误。

程序做的比较花哨，用了2个函数指针，一个用来指向评估函数，另一个用来指向空格移动的动作，这样主要循环就可以做得比较简单。另外使用了stl的vector，set两种容器。程序500多行，包含5个评估函数。我测试的数据量不大，发现最好用的是实际距离的平方。虽然这个评估函数并不可靠，但是在我的测试用例里面，找到了最优解。

昨天在bbs上看到2005年的百度之星比赛就是八数码问题，想想如果没写过这个程序，光知道算法的话，要在5个小时以内做出来还是比较困难的，数据结构以及stl方面都有很多东西要注意，比如我用了sort函数，这个函数用到了一个重载的比较算子，如果没有stl文档，我绝对做不出来的。如果不用stl，那就只有手动排序了。也算是比较辛苦的。

我的程序在vs2005下无法生成release版本，但是可以调试。最后我用gcc编译生成了release版本，运行了下看看，还是相当的快的。用这个程序去拿百度之星2005年的比赛应该是没有问题的，哈哈，可惜当时我还不会A*。

今天托业成绩出来了，竟然超过800分。很是震惊，没想到会考这个分数。因为只做过一份模拟卷，得了790，实测的感觉没有模拟卷好，但是听力比模拟多了25分，阅读和模拟一样。

太意外了，算是给我的一个小礼物吧，作为最近这么辛苦写程序的奖励！

从5.5日开始做到现在，我们的seuLex实验终于全部完成，刚刚发给老师了。

我负责的是NFA转DFA，DFA转MinDFA的部分。最后的代码，我还是比较满意的。算法上没有什么特别的，用的都是龙书上教的算法。但是实现技巧上着实花了一些功夫来降低复杂度。

首先在应用子集构造法做DFA的时候，用set表示子集，然后我简单重定义了set的比较算子，让set在排序的时候，首先比较集合的元素个数，然后再按元素逐个比较。其实这点我还是有点疑问的，我想如果用hash值来表示一个集合，肯定比较集合会更加快。具体想法是这样的，每个集合搭配一个集合的分数v = 1，然后每放进去一个元素a，求a的hash值，然后v *= hash(a)，最好按照v来排序集合。之所以没有这样做是担心会有重合的情况而且理论上我没办法证明不会有重合。

另外，在最小化DFA的时候，我重定义了set的比较算子，通过比较set被赋予的顺序id来比较分区。这样在分区里查找单个集合就是很快的了。最后，在分区构造好之后，建立了2个数组，分别表示DFA和MDFA状态之间的对应关系。通过这2个数组，以单位时间建立表格里一个单元的复杂度重建转移表。

自从前天阿松把NFA优化之后，我的DFA转化耗时就大大缩小。现在加上我的优化，程序只需要1.5秒左右就可以运行完毕，能够生成标准C的词法解析文件。

这几天用stl做lex，第一次比较大量的使用stl，发现stl并没有我心中想象的那么神。

首先要提的就是，stl的效率问题。的确stl含有很多世界上最优秀的算法，但是对于一些比较简单的结构，比如可以随机访问的线性容器，使用vector这一种最简单的容器，按我和同学们估计，估计根据是sgi的stl文档，vector随机读取是单位时间，应该和数组下标访问差不多。近今天阿松和我讨论到底用哪种比较好的时候，我们做了一个实验。8千万次随机访问vector和数组，vector耗时4秒，数组耗时1秒。我们原来估计也就是1：1.2的差距，谁都没想到竟然高达1：4。

不仅如此，如果我没看错的话，在集合的集合中查找集合，竟然没有利用最简单地先比较集合元素的方法，而是直接进行集合里逐个元素的比较。这导致我在set<set<int> >里查找一个set<int>成了意见很耗时的事情。但是，我觉得，这种情况下，先查找到元素个数相同的集合，再比较会很有效的节省平均复杂度。这并不是什么不容易想到的方法。

其次，本来我对于stl的使用是很畏惧得，觉得那种东西应该会很复杂。目前写了几百行代码的感觉就是，stl的迭代子使用起来，要写好长的类型申明的代码。第一次感到快速开发的可爱。

ps：最近写代码的时候，特别想酷一下，所以用void*和void**类型的参数，哈哈。不论什么类型，都可以通过这种方法传进来，然后可以cast成任意我想要的类型。于是，传进去的&T,传出来的类型就是T2，这里T != T2。hoho