Home > Uncategorized > CNCERT 比赛三天记

CNCERT 比赛三天记

比赛的三天是本周的周一至周三,日期是2010年8月9号至11号。那三天是我为搞比赛最忙的三天,每天晚睡早期,几近虚脱。最开始跟 @yakergong 同学商量做比赛,然后yaker 叫上了他中科院同学黑虾(我不记得他名字了,也没见过面,暂且这么叫吧)。yaker 在中科院上学,在HUST的时候聊过几句,没深交,大概我跟他性格都有点问题。当时是在校内和twitter上看到cncert比赛相关信息的分享,cncert是第一次办这个比赛吧,也不高调,我估计没多少人参加,于是抱着抢钱的想法报名了。随后是找人一起参赛。得知yaker 读过字符串匹配相关的理论书籍之后,邀请他一起比赛。yaker 欣然同意。

赛前也就面聊过几次。平时我们都比较忙,前期的准备都是黑虾 同学做的。比赛题目是这样的:给你一堆正则表达式(决赛有2000条),以及一大块数据(资格赛是1G的数据文件,决赛8G),对于每一条正则,把它在数 据块中每一次匹配打印出来。每一次匹配打印一行,格式为:匹配位置的文件偏移地址_匹配文本的长度_正则的ID。因为我之前做ACM比赛时,写过基于 Trie(字典树)的DFA,可以高效地做字符串匹配。于是我认为处理这个问题,最快的方式,也是做正则表达式合并。比如有规则r1 – rn,那么把字符串做成 (r1)|(r2)|…|(r3) 这种方式,做一次匹配就OK了。资格赛只要求提交数据。我用python写了一份,yaker 那边用pcre 做了一份,都是最简单的每个的正则做一次扫描,基本上跟举办方发过来的demo没多少差别。后来我把我的数据发过去,让yaker 比较下。yaker 说数据没问题,然后提交了。一段时间之后,我收到了决赛通知。

决赛当时通知的只有9号、10号两天。我一直认为,参赛队伍不会太多。因为举办方给我们发了测试用的ssh账号,我们的用户名是user5。我预计参赛队伍只有10来个队伍。这更坚定了我参赛的决心。

决赛的一周前,跟yaker 碰了面,讨论算法。那时候我们基本达成了一致,就是合并规则,做一次数据扫描。但上周日,yaker 告诉我这种方式有问题。当时在女朋友家,吃过晚饭之后才去中科院。那时候貌似发现了几个问题。
    1. 如果规则里面有括号,如何处理? – 这个问题,实际上把每个表达式的左括号在所有左括号中编号找出来就可以。因为pcre_exec 返回的捕获项目,是以左括号编号的。
    2. 如果两个规则,匹配的数据块有重叠,怎么办?同一个规则,匹配数据块有重复,怎么办?- 这个问题,主要是看规则怎么要求的。后来仔细看了规则,发现是这样的,对于同一个规则,匹配数据块不能重复。不同规则则不做要求。

晚上回去才开始coding C代码。那天yaker 硬盘出了问题,之前写的代码读不出来。我要求yaker 重写。我也被逼开始着手写。写完了之后发现一个问题:合并表达式的做法超级慢。另外发现一个问题,pcre_exec 函数并不是一次把数据匹配完,而是在第一次发现匹配后返回,另外还能带回捕获的信息。我是自己那小数据测试发现这个问题的;发现之后我们都傻逼了。部分原 因是给的demo代码写得烂;不过我们自身也有问题,到决赛前一天晚上,才发现这么一回事。之后比赛完了,我一直在反思:以后自己决心做一件事情的话,绝不能太依赖别人。8号那天晚上改C代码,基本上是被逼的。因为我不想放弃拿到那笔奖金的机会。

第一天
yaker实 验室开会,去不了。第二天早晨我醒来9点多了。那天周一。本来已经跟老板请好假了。但是我估计这时候去太晚了,所以干脆不去。我尝试着跟举办方打电话能否 下午过去。那边人说得请示领导。几分钟之后,那边来电话,说可以换明天上午。当时挺高兴,因为争取了24小时的时间。9号那天在公司基本上在做自己的比 赛。基本上放弃了合并规则的方式,并做了参数调优。所谓参数调优,不过是把pcre_exec 函数,以不捕获的模式运行。这种方式要快一些,当时算的是80%吧。那天还是非常想用非捕获的模式,运行合并后的正则表达式;然后hack pcre代码,返回匹配结束的时候,正则执行的位置。不过这东西不可能一个晚上写完了。

第二天
yaker继续去不 了,又我只好一个人去。9号给手机设置了闹铃。所以10号得以醒来。我直接带个手机出门上地铁。到了健德门站下车,凭着之前一天看google map 的感觉走。结果后来开google map 搜,发现走反了方向。然后打的去的。打的我都不知道具体位置,让司机慢点开,居然让我看到了。在收发室办一个房客的牌子。查的很严格,首先是被访人电话确 认,然后报自己的手机号码、工作单位。收发室那会儿刚好碰到几个一起参赛的。一个是大连理工大学的女研究生;另外3人,是华南理工大学的,他们还背了一台 式机。看到这台式机,我想到某年ACM/ICPC 全球决赛,朝鲜队也背着台式机让人笑话了。。。我们在一楼,给负责人打电话,过一会儿来人了,于是一起上楼。

上楼才发现上午参赛队伍只有 我们3家。瞄了眼比赛的报到表,大部分是学校参赛,北航,中科院,以及外省的;也有已经有工作单位的过来参赛。华南理工大学有个老师带队,那老师进场之后 开始向比赛的负责人介绍他们的作品:GPU做正则匹配。台式机居然也是Ubuntu Desktop。我和大连理工研究生mm比较安静了。

那 天上午我挺紧张。首先是发现我们队一直在用的代码是旧的,后来举办方发了一个新的代码框架,不仅仅是数据读入共享内存,规则也预先读入共享内存。新的框架 去了一些无用代码。我就把匹配函数放在新框架中。狂改了1个小时,终于编译通过,测试小数据也没问题。于是让负责技术的老师运行。结果,一运行真实数据就 出问题了:没有结果输出。于是打印调试信息查问题。发现,8G的文件长度,一个int类型已经存不下了,得用8字节整形。改代码,再跑,还是没结果。求助 负责老师。老师说,pcre 只能处理4字节的整形。那我只好修改上层调用。当时没怎么想,就把测试数据分块了,分了8个1G的。最后终于可以跑出数据。但相当慢。中午在楼下吃饭回来 之后,下午的参赛队伍陆续来了。因为测试机器只有4台,我的程序只好掐掉。负责老师也说了,如果是pcre库,单核心得跑上10多个小时的。跑了两个小 时,似乎才跑完2G的数据不到,正确报出了 4k 多的结果,但是错误结果报了1w多。按规则算分的话,分数就是负数了。这令我郁闷的不行,挺绝望,比赛之前也没想到会遇到这么多操蛋的事情。

大 连理工大学那队,也是一个人来参赛。她早晨来了之后,宾馆没订好,直接来参赛了。她们队是自己手写的正则匹配方法,没有用到现成的库 — 我觉得这事很不靠谱。她上午跑出来的结果是乱的,貌似也是因为测试数据的大小超出4字节整形的缘故。没调好,估计挺咪涨。她问比赛负责人LJ下午能否继续 调,LJ问她什么时候回去。她说后天。LJ告诉她说,那你明天上午再过来吧。

还有华南理工大学的。带队老师一会儿给LJ及其它领导介绍 GPU,一
儿监督两学生调程序。因为决赛通知里说了,最多每队只能两人到现场参赛;我觉得他们违反了规则。到了下午,别的队都来了,他们继续在台式机上 调。这令我很不爽。我心想,你们最开始坏的规则,早知道我也学着点。

下午我跟研究生mm一起下楼了,打算陪她去订好酒店就回去。结果去了 发现,酒店还是得她自己掏钱,报销是比赛结束后,交发票,然后打钱给你的。押金得900。她身上没那么多钱。她给比赛举办方打电话问能不能先举办方把钱交 了,电话那边给扯了一堆屁话,说什么怎么那么贵,问问能不能便宜点之类的,然后就挂了。我跟她说,我先借你钱吧。于是借了她1000。跟她一起上楼了。我 把电脑借她调程序了。

跟她交流中,我得知她在匹配过程中用了8个进程。8核就可以用满了。我想着,如果我们的代码加一个多核优化,以及对 于没有正则规则的表达式,聚合起来用DFA,那应该相当快的。我首先跟yaker 打电话,告诉他现在的情况以及自己的想法,问他还想不想搞。他答应了。我说数据还在现场,没数据没法知道我们现在错哪儿了。于是我马上跟LJ打电话,表示 希望争取下明天参赛的机会。LJ同意。当时我鼠标恰好也没带回来,我直接去那边拿了。过去的时候,又一次扣证件,并给LJ打电话说过来拿鼠标。LJ想我明 天再来拿,我说不行。他只好放我进来。但这会儿LJ在开会,只有那个技术负责人在比赛现场。我跟他说明了情况并把自己的数据拷了出来。出门的时候,由于没 有LJ的签字,在收发室等了好久;直到他一个电话过来,给值班人员说,先放我走,明天两份一起签字。

会宾馆之后累得不行,把数据发给 yaker 之后,就想睡觉。厕所有个浴缸。于是我跟研究生mm说了一声,进去泡了。泡得很舒服。这似乎还是我人生第一次用浴缸。以前没记得在哪用过;除非小时候的大 洗澡盘也算。出来之后都没力气把身体擦干净,直接穿个内裤上床睡觉了。不知睡了多久,研究生mm也洗去了。那时候就开始写字典树。她出浴之后还没写完。我 挺想在这里写一个通宵的。吃完了完饭之后,她说她想休息了。让我回去。我说我就在这里过一晚上呗。回去明天还得过来,麻烦。她说不方便,我说那好吧,我闪 了。

晚上回家用手机3G网络,继续跟yaker交流,写trie上的DFA。他的多线程的任务调度,在10点半左右写完,测好了,提交。 我这边的trie DFA出了点问题。我之前以为匹配失败,直接去连根节点的。但是稍微细致地想想就发现不对。因为一次失败之后,后缀可能会参与下一次匹配。直接重新从跟部 走,会丢掉后缀的。没办法,这算法我不熟悉,然后给@ichbinghost 打电话,要代码。他没有C的,有pascal的。我让他发过来。一看比TM天书还难懂 — 这就是OI/ACM 代码风格,代码质量完全以是否能Accepted为准。我看得头疼,又打电话要论文。他给发了过来,继续看不懂。。。那论文刚说到要点就开始扯蛋,连一个 算法流程违代码都没有。当时搜google也没搜到。于是继续电话问原理。大概懂了。但是由于担心第二天精神不好,到了凌晨两点,没写完,我还是睡觉了。

第三天
第 二天来还拍了几张照片的。到了第三天,就完全没心情了。早晨在地铁上就开始画字典树的构造流程。到了现场直接开自己的笔记本敲代码。敲了有2多个小时,到 了10点半,才写完。make下 error 一堆的。error fix完了之后11点吧。这时候有点慌了,因为时间不多,而昨天yaker 的多线程仅仅测试了小数据。没办法,我把自己的代码注释掉了。开始测试yaker 的东西。结果再一次悲剧:木有结果出来。这会儿LJ过来看,说,昨天不是还有结果的么,今天怎么没了;只有1个小时的测试时间了,要不用昨天的结果吧。我 说,我相信这次一个小时出来的结果要比昨天的好。debug了一阵子,发现多线程传数据那块,把长度设为4字节int 类型了。改完了之后就让跑测试,并下楼吃饭。回来之后,我的程序已经跑完了。11分钟,8800+个正确,1个误报。这结果让我松了口气。我脸皮没有厚到 下午还要赖在这里。但研究生mm还是坚持下午做调试。后来也没怎么问结果如何了。

yaker 中午也过来了。他过来那会儿我在吃午饭。后来上去之后,我又改了代码,希望多报几个结果。很不好意思地说我把代码改怀了。于是连忙说这个结果不算,还是用 中午已经跑出来的那份吧。然后闪人了。打算跟yaker 一起回去,路上聊聊。结果进地铁手机没信号,也没碰到他。然后各自回去了。

第四天
这天不是比赛,只是又去了宾馆一趟,收钱而已。研究生mm要还我钱了。人家主动跟我说的,人还挺厚道。

最 开始一位这个比赛,yaker 他们完全可以搞定,我呢,之用去现场跑一跑就够了。而结果完全不是这样的。每一行代码我都得看都得改。虽然 yaker 在比赛前有段时间表现不太积极,但是我后来觉得,既然是以自己名义报名参赛,就应该承担所有的责任和风险,并且不能让队友失望。而且,自己去现场,就不能 太依赖别人。星期一那天去没参赛,女朋友打电话我问这件事情。我说起晚了,她把我骂了一通,说你咋这么不负责,这么轻易就把别人的付出白白浪费了。后来我 告诉她我已经争取到了第二天参赛的机会,她才消气。责任,责任。

至于pcre,比赛那几天可是争分夺秒地看文档,还非常希望能够自己去改pcre的代码。结束之后什么懒得做了。希望自己能够养成好的学习习惯。

小公司比较自由,可以有比较大的个人发挥空间。但闲散也能把一个人废掉吧。在这里,还得感谢我的老板,能在我的工作任务扎堆的情况下,给我三天时间作比赛。感谢队友@yaker 黑虾 以及 @ichbinghost 的参与和支持。

明天要去怀柔玩。我不把这些写下来,会很快忘记。用WebQQ,我开始选择性地记录。人总得往前走。人的记忆量也有限。会舍弃无用,会追求新知,这也是适应能力的一种表现。

Advertisements
Categories: Uncategorized
  1. August 14, 2010 at 6:00 am

    为G*F*W效力,迟早会被清算的

  2. August 14, 2010 at 8:02 am

    楼主把层次提得太高了,分辨是非的能力我们还是有的

  3. August 16, 2010 at 2:04 pm

    1楼,其实目前我所做的仅是为了参赛。GFW 不可能连我做的那点优化都做不到的。
    我认为,我们应该向政府正面表达我们对内容审核的不满,GFW 才有可能被推到。

    另外,这里没有审查,没人删的。

  1. No trackbacks yet.

Leave a Reply

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 / Change )

Twitter picture

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

Facebook photo

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

Google+ photo

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

Connecting to %s

%d bloggers like this: