Jun 7

今天很有收获 不指定

felix021 @ 2009-6-7 00:45 [IT » 其他] 评论(2) , 引用(0) , 阅读(5513) | Via 本站原创 | |
写了一点代码来判断astar公开的代码中任意两段代码的相似性。
最关键的是求字符串的编辑距离,O(N^2),很慢。
于是跑了6个小时,还是2台机器、多个进程同时运行。
但是那个囧到我的astarAnticheat则很快就cha到了我的代码。
问了他怎么回事,然后发现自己做了很挫很挫的事情(详见聊天记录,后附)。

附上用来判相似的代码:
下载文件 (已下载 次)


聊天记录如下:
引用
Felix021 00:26:04
今天真是太happy了~

astarAnticheat 00:26:17
挺有意思的

Felix021 00:26:20
第一次跑这么久的程序啊~
你是咋找的相似呢?
很好奇

astarAnticheat 00:27:06
其实是lcs

Felix021 00:27:10
………………………………
我败给你了

astarAnticheat 00:27:21
取一些标点,然后lcs

Felix021 00:27:26

分段
lcs

astarAnticheat 00:27:29
。。。你的技术含量更高

Felix021 00:27:35
我的效率太低
lcs可以优化到O(n)啊
O( n )
edit distance O ( n^2 ),太慢了

astarAnticheat 00:28:55
我只会搞个平方了

算法基础差。。。

Felix021 00:29:15
- -|| 那你跑了多久判到我的啊。。
suffix array我也不会写=.= 只是扫过去而已

astarAnticheat 00:29:52
5点多是就cha到了
但一直没发

Felix021 00:30:19
被你囧到了,哈哈

astarAnticheat 00:30:24
程序大概跑10分钟
呵呵

Felix021 00:30:45
啊?10min?你判多少人啊?

astarAnticheat 00:31:09
第一题只有312个程序
我能拿到的

Felix021 00:31:27
可是总共有48000+种组合啊
O(N^2)哪有那么容易算。。

astarAnticheat 00:31:49
300×300 × 1024×1024

Felix021 00:32:04
我的程序从开始到最后一直在算day1_1,多开了几个线程兼算其他的
day1_1还分开算了
没有1024那么简单吧

astarAnticheat 00:32:50
我的字符串比源程序短,因为只选取标点和数字,把字母都删掉了

Felix021 00:32:51
有一半的代码在3.5K以上啊

这样确实最省事。。
其实我做了很多无用功=.=
标点和数字足够了。。

astarAnticheat 00:33:40
因为考虑到变换变量名啥的,就把字母删掉了

Felix021 00:33:55
嗯,我也是考虑这个,但是还傻乎乎地保留关键字。。。果然挫了
细想一下发现其实没有必要






欢迎扫码关注:




转载请注明出自 ,如是转载文则注明原出处,谢谢:)
RSS订阅地址: https://www.felix021.com/blog/feed.php
love8909
2009-6-7 12:02
LCS用位运算优化倒是有 O(n * m / |w|)的方法,没有听说过可以优化到O(n)
felix021 回复于 2009-6-7 13:46
http://www.byvoid.com/blog/lcs-suffix-array/
是O(N*L*log(L)),我大概是以前看错了=.= 而且好像不是这个地方用的,汗。
upsuper Email Homepage
2009-6-7 11:11
……幸好没和他们一起搞……不然名誉扫地了……

其实你还应该考虑改定义顺序什么的……
二试信息组众学乖了花了半个小时改风格……

我认为你应该先选择特征性错误输入对所有程序进行测评,然后针对输出相同的/发生相同崩溃的,进行判断,这样可以很好的减少查的东西。
此外,我觉得可以根据程序特征,比如一些特别的运算符、标准库函数还有递归等的出现顺序作为一个函数的特征,然后对特征进行对比。通常改风格不会对函数内部做大的操作,最多就是提取小的函数。鉴于可能有函数的提取和合并,我建议之间将仅出现一次的函数先扩展了,所有短的函数也直接扩展了,这样准确率又再次提高……
还有一种方法,就是运行时调试,就是编译完跑一个数据,然后比对内存中存储的数据相似性什么的……
还可以通过比较奇特的数据比较运行时间什么的……本质不同的代码通常常数会有相当的差异……
可以选用一些快而有效的方法先筛什么的……

说一句……多线程要在超线程或多核的处理器上才比较有意义……否则只会更慢……
推荐弄一个linux精简核心不加其他东西然后拿来跑,这样效率估计会好不少……

以上是建议……
另外啊……LCS怎么优化到O(n)啊???
felix021 回复于 2009-6-7 13:46
程序要是那么复杂我就不写了。。。。

现在的CPU基本都是多核的。。不然我才不会开多个线程跑。

http://www.byvoid.com/blog/lcs-suffix-array/
是O(N*L*log(L)),我大概是以前看错了=.= 而且好像不是这个地方用的,汗。
分页: 1/1 第一页 1 最后页
发表评论
表情
emotemotemotemotemot
emotemotemotemotemot
emotemotemotemotemot
emotemotemotemotemot
emotemotemotemotemot
打开HTML
打开UBB
打开表情
隐藏
记住我
昵称   密码   *非必须
网址   电邮   [注册]