主题:[讨论]第39次编程比赛结果
ccpp [专家分:9360] 发布于 2006-08-27 14:51:00
第一题未通过测试的朋友:
liyanguestc_1f:
没有按要求编写函数:若存在这样的i(m个),函数Majority返回m,否则函数返回0。而你返回的是这个自然数 i。
tenm_7f:
方法比较直接,而且没有按要求编写函数:没有完整的计算可能存在的超过半数i的个数
batmanlf_10f:
=>Wrong,right is 6,but you get 0
array:x[] = { 2, 2, 1, 1, 2, 2, 2, 1, 2, 1,};
wlsss_15f:
=>Wrong,right is 6,but you get 4
array:x[] = { 2, 2, 1, 1, 2, 2, 2, 1, 2, 1,};
joekings_f17:
你和 1楼的liyanguestc一样没有按要求编写函数。你们算法大体上也是一致的,
排序后,你查找的方法有问题,参见完整代码。
ghbxx2004_f20:
没有按要求编写函数:题目已知 m > n/2,
而你的代码是 :if(m >= (n/2) ){return m;}
bloodybg_f21:(修改后,对你的程序进行了效率测试)
使用全局变量arrayNum时,
int Majority(int vote[], int n)
{
//arrayNum = 0;//在调用函数Majority时arrayNum没有赋值为0
int *a, *b;
...
//结果造成你的函数不能循环使用,
//原因是,在第二次调用函数Majority时,arrayNum的值不是0,而继续保存上一次的遗留值。
gohan_f28:
=>Wrong,right is 6,but you get 0
array:x[] = { 2, 2, 1, 1, 2, 2, 2, 1, 2, 1,};
hwjian_f31:
=>Wrong,right is 6,but you get 10
array:x[] = { 2, 2, 1, 1, 2, 2, 2, 1, 2, 1,};
天边蓝_f32:
你和 1楼的liyanguestc一样没有按要求编写函数。你们算法大体上也是一致的,
排序后,你查找的方法有点繁琐,参见完整代码。
forjane_f42:
=>Wrong,right is 6,but you get 0
array:x[] = { 2, 2, 1, 1, 2, 2, 2, 1, 2, 1,};
wksuper_f47:
没有按要求编写函数:没有计算可能存在的超过半数i的个数。
yelv_f49:
方法比较直接,而且没有按要求编写函数:没有没有完整的计算可能存在的超过半数i的个数。
大部分未通过测试的朋友,主要原因是没有按要求编写函数接口,或者写代码时过于疏忽,
因为上面的朋友使用的都是同一种算法:先排序,后查找并计数。
有完整的代码供大家参考,如下:(n=1千万时,耗时781 ms)
int Compare(const void*x, const void *y){
return *(int*)x - *(int*)y;
}
int Majority (int vote[], int n)
{
int i,j,half = n/2;
int count = half+1;
qsort(vote, n, sizeof(int), Compare);//排序
//sort(vote,vote+n);
for(i = 0; i < int(n/2.0+0.5); i++){//平台式查找
if(vote[i] == vote[i + half]){
for(j = i + half + 1; j < n; j++){
if(vote[j] == vote[i])
++count;//开始记数
else
break;
}
return count;//计算完毕,结束函数
}
}
return 0;
}
效率测试:
当数组的大小为2万时,一些朋友的程序开始见慢,
wlsss_4f:time cost is :3375 ms
hyl084_f25:time cost is :5594 ms
qingfengjianke_f46:time cost is :1640 ms
jihao111_f53:time cost is :3329 ms
而其他朋友的程序都能控制在 10ms(左右)以下。
当数组的大小为1千万时
jackin0627_3f: 938 ms
01835cwj_6f: 2766 ms
rickone_f18: 313 ms
bloodybg_f21: 688 ms
孤独的猫_f22: 531 ms
天国龙_f23: 516 ms
jxstudying_f24:1141 ms
xyhx_f26: 860 ms
火海时代_f27: 1375 ms
SonicLing_f30: 8328 ms
neverPE_35: 0 ms
yunzhou008_f37:5000 ms
amen_f41: 4078 ms
wshong_f44: 1500 ms
侍鱼_f48: 515 ms
liangbch: 172 ms
BigCarrot: 232 ms
[color=008000]当数组的大小为1亿(机器状态最好时)时
neverPE_35: 0 ms //为什么总是0,是不是编译器有问题!
liangbch: 1703 ms
BigCarrot: 2329 ms
题目标准算法: 830 ms[/color]
我宣布次数比赛的冠军是 [color=800000]neverPE 兄[/color],请neverPE 准备第40次编程比赛。
[color=000080]赠送题回复得人不多,且都使用了相似得算法,题目的标准算法也和大家的几乎一样。[/color]
P.S.测了一天了,几乎要崩溃了!如果测试结果有令大家不满意的地方,请多多见谅!
回复列表 (共29个回复)
11 楼
BigCarrot [专家分:10] 发布于 2006-08-26 22:44:00
一般情形下来说确实是标准答案最高效,下面我有几个问题
1 为什么neverPE的时间是0? ccpp有没有研究过ccpp的算法?
从纯算法正确性的角度来说,我觉得neverPE的实现是错的
从能否通过测试的角度来说,neverPE的实现非常漂亮,已经非常接近于无懈可击了
他的方法太投机了, 实现了一个正确性为一个非常高的概率的快速算法
2 关于测试数据
int n = 100000000,step = 10;
int *vote = new int[n];//分配空间
for(int i = 0; i < n; i++){ //生成测试数据
vote[i] = rand() % step + 1;
}
这个数据太特殊了,不具有一般性吧
两个问题, 第一是不同的数组元素个数太少了吧,总共才10个,
第二是数组元素的分布有问题,集中在1..10,
原题中数组元素是自然数,而函数原型中给出的是int型
正是这种特殊性才使liangbch的程序有比较快的速度
建议你可以试试下面两组数据
{1,2,3,...,n}
{1,2,3,...n/2-1, n/2,n/2, ...}
除了标准答案,我得程序和neverPE的程序,其他代码的执行时间都会有翻天复地的变化
3. ccpp是否研究过rickone的算法?
理论上在你给出的这种测试数据的情形下, hash几乎不会产生冲突,因此他的复杂度应该为 n , 而标准算法算法复杂度为2n,我得也是2n,测试结果,在1千万时hash并不非常快,1亿时也见不着影子.
我得猜测,ccpp测试时是在debug模式下作出的,那个hash的实现中有多个函数调用存在,debug模式下函数调用的额外开销导致了实际结果并不好,如果能在release模式下并且inline掉,就不会有这些额外开销了
同样我得程序运行时间也证明了这一点,我得时间复杂度为2n + 64k*2, 标准答案为2n, 那个尾巴64k*2非常小根本不可能反映到执行时间上,但实际执行结果却是接近3倍的时间差距,合理的解释还是在debug模式下,更加紧凑,简洁(当然也更加漂亮)的代码会快不少
我在提交程序的帖子中0x6000000(比1亿还大一点点)时执行时间4-5s是在debug模式下,我刚刚跑了一下release模式2-3秒,我得机器是P3M 1.2G, ccpp的机器应该比我好不少吧.
最后对测试方法的建议,希望采用下面两种方案之一
一是出题的同时,给出测试数据或测试数据生成代码
二是给定机器,环境,配置,编译参数,执行时间,在结帖之后,除了测试出题人的数据之外,还允许网友们提交测试数据,类似于topcoder的challenge阶段.
12 楼
01835cwj [专家分:1900] 发布于 2006-08-26 23:00:00
[quote]gohan_f28:
=>Wrong,right is 6,but you get 0
array:x[] = { 2, 2, 1, 1, 2, 2, 2, 1, 2, 1,};
不是就是输出0吗?只有2个自然数嘛。ft,难道没读懂题目??[/quote]
你没读懂题目啦。浪费了ccpp兄的心血啊。
13 楼
neverPE [专家分:1620] 发布于 2006-08-26 23:25:00
看来BigCarrot花了不少时间来研究这几个程序。我也认为测试数据不强,但毕竟一个人要测试几十个程序,而且这么短时间出结果也不容易。
我记得第36次出结果后,liangbch作为参赛者又对所有程序进行了分析和进一步测试,甚至还有改进。(http://www.programfan.com/club/showbbs.asp?id=185736 第1~3页) 既然BigCarrot兄如此有热情,何不在ccpp的基础上再进行更严格的测试呢?用针对性的数据指出各个算法的弱点。
ps:我并不认为的我算法投机,概率算法也是算法的一个重要分支。6个9以上或者更高的正确率足够保证它的实用性。
14 楼
SonicLing [专家分:6260] 发布于 2006-08-26 23:57:00
neverPE的算法的确很投机,他的结果正确性只能用百分比来形容。
不过对大批量数据进行定性处理,使用投机算法来加速也不是不可以,密码学中生成巨型素数也是使用投机判别法,只要保证9是素数的可能性达到90~97%以上即可,算法简单高效。
15 楼
BigCarrot [专家分:10] 发布于 2006-08-27 00:20:00
更好的test case我已经给出了, 而且预测了结果. 如果对算法复杂性有所了解,都会认可这个结果. 如果还有怀疑的话, 直接跑那两个case就可以了.
如果要attack你的程序,有两种方法,一是改rand()函数,二是改time()函数, 我自己都怀疑这样是否合适 :(
这样就导致你得不到随机序列, 剩下的事情就简单了
你的方法一个比较正式的名字叫做Monte Carlo method, 这是一个非常重要的方法.
问题是用在哪里要看所处的环境.
比如一个数学证明题, 你用电脑模拟了100000次得到一个结果,就能说明这个命题被证明了吗? 也许还有10^100在等着你呢.
现实一点的例子,编译器优化算法中很多都是NP问题,但是假设你发现了一个快速算法,能够针对99.9999999%(10个9)的起作用,唯一的遗憾是剩下的0.000000001%情况下会导致错误的结果,这个快速算法能用吗?
另外一些情形,比如网络流量控制, 生物种群的变化等等,这些才是Monte Carlo的用武之地.一般只有当问题的本质是基于统计的,Monte Carlo才比较适用.
很显然这个题目本身不是基于统计的,你的算法对于这个题目是错误的.
问题在于测试过程是一种统计的过程,因为我们不可能把所有的数据,所有的time,和所有的rand实现都拿来测一下,所以你的方法能够在测试这样一个基于统计的方法中表现非常好.
16 楼
euc [专家分:4310] 发布于 2006-08-27 09:33:00
这两种方法真好!!因为neverpe的方法只抽511个数,所以不管n多大都是0ms.学到了~ 呵呵
17 楼
wshong [专家分:1880] 发布于 2006-08-27 10:05:00
[quote]gohan_f28:
=>Wrong,right is 6,but you get 0
array:x[] = { 2, 2, 1, 1, 2, 2, 2, 1, 2, 1,};
不是就是输出0吗?只有2个自然数嘛。ft,难道没读懂题目??[/quote]
因为2个数超过总数的半数,所以是6
18 楼
ccpp [专家分:9360] 发布于 2006-08-27 11:00:00
[quote]
最后对测试方法的建议,希望采用下面两种方案之一
一是出题的同时,给出测试数据或测试数据生成代码
二是给定机器,环境,配置,编译参数,执行时间,在结帖之后,除了测试出题人的数据之外,还允许网友们提交测试数据,类似于topcoder的challenge阶段.
[/quote]
很好的建议,可供以后的冠军参考...
本来想仔细看看每个人的程序,可是后来脑子已经不好使了...
neverpe 兄 原来使用了概率算法,这回我又长见识了...
p.s.马上就开学了,就要从业余人士变成专业的了...
在这里遇到了很多达人,长了很多见识,以后还要继续向大家学习...
19 楼
liangbch [专家分:1270] 发布于 2006-08-27 11:34:00
neverPE 确实厉害,我要好好读读你的程序.你上次写的程序前几天读完,我试图改写一下,结果越改越复杂.如果从程序简洁性方面来看,可能很少有人能够超过neverPE.我有时间的话,我想就上一次程序,写一个非递归程序.
20 楼
liangbch [专家分:1270] 发布于 2006-08-27 11:46:00
我也觉得应该增加几种testcase,这样才能全面评价各个程序的性能。比如我的程序,实际上用了三种算法,当数组较小时,采用qsort排序加顺序统计的算法,当数组中元素的最大值小于数组元素个数时,采用的是一直接计数的方法。当数组中的元素最大值很大时,采用的是一种非常复杂的算法。而且这个算法对结果等于0和结果不等于0的运行时间也不一样。
我来回复