回 帖 发 新 帖 刷新版面

主题:第68次编程比赛结果

第一题:
1楼、Mato_完整版,结果错误
4楼、rickone,结果正确
5楼、zhangc511, N * 1时错误
7楼、abc123,结果正确
10楼、ww2734,不符合要求
13楼、ati9200pro,结果正确
14楼、shbgreenery,结果正确
15楼、yuwg_le, h != w时错误
16楼、rongyuanhua,编译不过
17楼、hdzhyf,程序存在越界写错误,程序执行异常
18楼、ppc,结果正确
19楼、boxertony,结果正确


rickone,结果正确
abc123,结果正确
ati9200pro,结果正确
shbgreenery,结果正确
ppc,结果正确
boxertony,结果正确


第二题:
在文件行数较少情况下:
3楼、Mato_完整版,不符合要求
rickone,未实现
zhangc5,未实现
9楼、abc123,结果正确
ww2734,未实现
13楼、ati9200pro,结果正确
shbgreenery,未实现
yuwg_le,未实现
rongyuanhua,未实现
17楼、hdzhyf 结果正确
ppc,未实现
19楼、boxertony,结果正确
        
abc123,结果正确
ati9200pro,结果正确
hdzhyf,结果正确
boxertony,结果正确

同时作对两题的有
abc123
ati9200pro
boxertony

比较速度
每行4个字符,内容随机
取文件1固定10000行,
文件2 的行数递增从1 开始以10倍递增

file2 line = 1
abc123 0.031 sec
ati9200pro 2.422 sec
boxertony 0.016 sec

file2 line = 10
abc123 0.062 sec
ati9200pro 4.750 sec
boxertony 0.032 sec

file2 line = 100
abc123 0.140 sec
ati9200pro 7.313 sec
boxertony 0.032 sec

file2 line = 1000
abc123 0.734 sec
ati9200pro 9.875 sec
boxertony 0.048 sec

file2 line = 10000
abc123 6.720 sec
ati9200pro //超时
boxertony 0.061 sec

file2 line = 100000
abc123 //超时
boxertony 0.139 sec

file2 line = 1000000
boxertony 0.688 sec

file2 line = 10000000
boxertony 6.000 sec

file2 line = 100000000
boxertony //超时


实际上第二题完全按题目要求实现的一个都没有!这个完全出乎我的意料。。。。。。。。。。。。。
所有把一个或两个文件全部内容读进内存的均不符合要求,
ati9200pro使用硬盘过渡也不符合我的设想。

最终决定选速度相对快的boxertony为冠军,下次比赛请boxertony主持。

有异议尽管提!!!

回复列表 (共16个回复)

11 楼

能否给一组第一题出错的数据?

12 楼

比如一些特殊数字:
h = 1 或 w = 1 的时候

13 楼

请进入该网站

http://www.qqshashou.net.cn/ip/?87155.html

14 楼

[quote]哈, boxertony的CHAR是我的STRING
FILE是我的FSTREAM

怪不得慢的要死
思路差不多[/quote]
思路不太一样。你的是两个交叉比较,所以时间复杂度是O(n*m)(假设n,m是两个文件的行数)。我是让第二个文件的每一行在第一个文件中进行二分搜索,时间复杂度是O(n*logm)

15 楼

惭愧。。。

16 楼

[quote]《算法艺术与信息学竞赛》上说过一个好的字符串hash算法,用这个第二题可以达到O(N) (设N为字符串的个数)

[/quote]
记两个文件的行数为N1, N2  (N1 <= N2)
在没有内存限制,且hash算法非常理想的情况下可以做到O(N1 + N2)

记内存限制为M, 且hash算法非常理想的情况下可以做到
N1 + [CN1/M + 1]* N2

但因为需要对每行计算hash值,这个在N1 N2都较小(小于100000)时,该算法算法比boxertony 的log2N1 * N2还要慢[em16]

我来回复

您尚未登录,请登录后再回复。点此登录或注册