推荐阅读的两篇文章
semaphore and mutex
Jun
7
写了一点代码来判断astar公开的代码中任意两段代码的相似性。
最关键的是求字符串的编辑距离，O(N^2)，很慢。
于是跑了6个小时，还是2台机器、多个进程同时运行。
但是那个囧到我的astarAnticheat则很快就cha到了我的代码。
问了他怎么回事，然后发现自己做了很挫很挫的事情（详见聊天记录，后附）。
附上用来判相似的代码：
下载文件 (已下载 次)
聊天记录如下：
转载请注明出自 ，如是转载文则注明原出处，谢谢:)
RSS订阅地址: https://www.felix021.com/blog/feed.php 。
最关键的是求字符串的编辑距离，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
嗯，我也是考虑这个，但是还傻乎乎地保留关键字。。。果然挫了
细想一下发现其实没有必要
今天真是太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 。
是O(N*L*log(L))，我大概是以前看错了=.= 而且好像不是这个地方用的，汗。
其实你还应该考虑改定义顺序什么的……
二试信息组众学乖了花了半个小时改风格……
我认为你应该先选择特征性错误输入对所有程序进行测评，然后针对输出相同的/发生相同崩溃的，进行判断，这样可以很好的减少查的东西。
此外，我觉得可以根据程序特征，比如一些特别的运算符、标准库函数还有递归等的出现顺序作为一个函数的特征，然后对特征进行对比。通常改风格不会对函数内部做大的操作，最多就是提取小的函数。鉴于可能有函数的提取和合并，我建议之间将仅出现一次的函数先扩展了，所有短的函数也直接扩展了，这样准确率又再次提高……
还有一种方法，就是运行时调试，就是编译完跑一个数据，然后比对内存中存储的数据相似性什么的……
还可以通过比较奇特的数据比较运行时间什么的……本质不同的代码通常常数会有相当的差异……
可以选用一些快而有效的方法先筛什么的……
说一句……多线程要在超线程或多核的处理器上才比较有意义……否则只会更慢……
推荐弄一个linux精简核心不加其他东西然后拿来跑，这样效率估计会好不少……
以上是建议……
另外啊……LCS怎么优化到O(n)啊？？？
现在的CPU基本都是多核的。。不然我才不会开多个线程跑。
http://www.byvoid.com/blog/lcs-suffix-array/
是O(N*L*log(L))，我大概是以前看错了=.= 而且好像不是这个地方用的，汗。