回 帖 发 新 帖 刷新版面

主题:[讨论]第39次编程比赛结果

第一题未通过测试的朋友:
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 楼

一般情形下来说确实是标准答案最高效,下面我有几个问题

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 楼

[quote]gohan_f28:
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;=>Wrong,right&nbsp;is&nbsp;6,but&nbsp;you&nbsp;get&nbsp;0
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;array:x[]&nbsp;=&nbsp;{&nbsp;2,&nbsp;2,&nbsp;1,&nbsp;1,&nbsp;2,&nbsp;2,&nbsp;2,&nbsp;1,&nbsp;2,&nbsp;1,};

不是就是输出0吗?只有2个自然数嘛。ft,难道没读懂题目??[/quote]

你没读懂题目啦。浪费了ccpp兄的心血啊。

13 楼

看来BigCarrot花了不少时间来研究这几个程序。我也认为测试数据不强,但毕竟一个人要测试几十个程序,而且这么短时间出结果也不容易。

我记得第36次出结果后,liangbch作为参赛者又对所有程序进行了分析和进一步测试,甚至还有改进。(http://www.programfan.com/club/showbbs.asp?id=185736 第1~3页) 既然BigCarrot兄如此有热情,何不在ccpp的基础上再进行更严格的测试呢?用针对性的数据指出各个算法的弱点。

ps:我并不认为的我算法投机,概率算法也是算法的一个重要分支。6个9以上或者更高的正确率足够保证它的实用性。

14 楼

neverPE的算法的确很投机,他的结果正确性只能用百分比来形容。

不过对大批量数据进行定性处理,使用投机算法来加速也不是不可以,密码学中生成巨型素数也是使用投机判别法,只要保证9是素数的可能性达到90~97%以上即可,算法简单高效。

15 楼

更好的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 楼

这两种方法真好!!因为neverpe的方法只抽511个数,所以不管n多大都是0ms.学到了~ 呵呵

17 楼

[quote]gohan_f28:
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;=>Wrong,right&nbsp;is&nbsp;6,but&nbsp;you&nbsp;get&nbsp;0
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;array:x[]&nbsp;=&nbsp;{&nbsp;2,&nbsp;2,&nbsp;1,&nbsp;1,&nbsp;2,&nbsp;2,&nbsp;2,&nbsp;1,&nbsp;2,&nbsp;1,};

不是就是输出0吗?只有2个自然数嘛。ft,难道没读懂题目??[/quote]
因为2个数超过总数的半数,所以是6

18 楼

[quote]
最后对测试方法的建议,希望采用下面两种方案之一
一是出题的同时,给出测试数据或测试数据生成代码
二是给定机器,环境,配置,编译参数,执行时间,在结帖之后,除了测试出题人的数据之外,还允许网友们提交测试数据,类似于topcoder的challenge阶段.
[/quote]

很好的建议,可供以后的冠军参考...

本来想仔细看看每个人的程序,可是后来脑子已经不好使了...

neverpe 兄 原来使用了概率算法,这回我又长见识了...



p.s.马上就开学了,就要从业余人士变成专业的了...
    在这里遇到了很多达人,长了很多见识,以后还要继续向大家学习...

19 楼

neverPE 确实厉害,我要好好读读你的程序.你上次写的程序前几天读完,我试图改写一下,结果越改越复杂.如果从程序简洁性方面来看,可能很少有人能够超过neverPE.我有时间的话,我想就上一次程序,写一个非递归程序.

20 楼

我也觉得应该增加几种testcase,这样才能全面评价各个程序的性能。比如我的程序,实际上用了三种算法,当数组较小时,采用qsort排序加顺序统计的算法,当数组中元素的最大值小于数组元素个数时,采用的是一直接计数的方法。当数组中的元素最大值很大时,采用的是一种非常复杂的算法。而且这个算法对结果等于0和结果不等于0的运行时间也不一样。

我来回复

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