第67次编程比赛结果 — 编程爱好者社区

主题：第67次编程比赛结果

boxertony [专家分：23030] 发布于 2008-06-25 22:49:00

测试环境：VS2008，Windows XP

7楼的程序开空间过大，18楼的程序运行时出现异常错。

1000个数据：
        scutdx2005(   1楼):      0毫秒。
     willzhanglala(   2楼):      0毫秒。
            yclz(   3楼): 结果错误。
        wxfbbsid(   5楼):      0毫秒。
    yuwgle(   6楼): 超时
       blue.lake(   9楼):      0毫秒。
          廖增祥(  10楼):      0毫秒。
           fdasf(  12楼): 结果错误。
     ckeryradish(  13楼):      0毫秒。
        路人甲08(  16楼):      0毫秒。
          hxw910(  17楼): 结果错误。
            hyfl(  19楼):      0毫秒。
            Noar(  20楼):      0毫秒。

100000个数据：
      scutdx2005(   1楼):      0毫秒。
   willzhanglala(   2楼):     47毫秒。
        wxfbbsid(   5楼):    157毫秒。
    blue.lake(   9楼):    157毫秒。
          廖增祥(  10楼):    157毫秒。
     ckeryradish(  13楼):     32毫秒。
        路人甲08(  16楼):     32毫秒。
            hyfl(  19楼):     32毫秒。
            Noar(  20楼):   1313毫秒。

1000000个数据：
      scutdx2005(   1楼):    484毫秒。
   willzhanglala(   2楼):   2453毫秒。
        wxfbbsid(   5楼):    超时
    blue.lake(   9楼):    超时
          廖增祥(  10楼):         超时
     ckeryradish(  13楼):    328毫秒。
        路人甲08(  16楼):   1656毫秒。
            hyfl(  19楼):   1687毫秒。
            Noar(  20楼):  26797毫秒。

10000000个数据：
      scutdx2005(   1楼):   5187毫秒。内存耗费136M
   willzhanglala(   2楼):  25078毫秒。
     ckeryradish(  13楼):   3687毫秒。内存耗费40M
        路人甲08(  16楼):  15234毫秒。
            hyfl(  19楼):  73875毫秒。
            Noar(  20楼):  超时

（注：上面内存耗费是指程序运行时实际耗费的内存大小）

从上面测试结果来看，13楼ckeryradish的程序速度最快，且耗费空间最少，因此本人宣布ckeryradish为本次比赛的冠军，下次比赛由ckeryradish主持。祝贺！

本帖地址： http://bbs.pfan.cn/post/279501.html

回复列表（共5个回复）

沙发

路人甲08 [专家分：20] 发布于 2008-06-26 14:11:00

第一次参加，能挺到最后，知足了。本来就有偷懒的嫌疑，几乎没有自己的东西，关键的都是vc++里面集成的stl。或许自己再修改一下会更好，不过不是很清楚stl里面的算法是什么，自己的算法未必会更好就放弃。
ckeryradish的程序粗略看了一下，没看懂，大概是具体问题分析，把问题出现的情况细分了吧。很强啊，10000000个数据才3687毫秒。

板凳

Noar [专家分：0] 发布于 2008-06-26 20:30:00

楼主能否把测试程序贴出来，主要想看看是什么样的测试数据

3 楼

boxertony [专家分：23030] 发布于 2008-06-27 00:07:00

long GetRand(long n)
{
    return (long)((double)rand()/32768*n);
}

int main()
{
    FILE    *fp;

    fp = fopen("1000000.txt", "wt");

    srand(time(NULL));
    int        n = 1000000;

    long    *arr;

    arr = new long[n];
    arr[0] = -rand()*rand();

    for(int i=1; i<n-1; ++i)
    {
        arr[i] = arr[i-1] + rand()/15;
        if(arr[i] == arr[i-1])
        {
            --i;
        }
    }

    arr[n-1] = arr[n/2];

    int        j;
    for(i=0; i<n; ++i)
    {
        j = GetRand(n);
        if(i != j)
            Swap(arr[i], arr[j]);
    }

       // 检查是否有一对以上的重复，如果有则重新生成。

    for(i=0; i<n; ++i)
        fprintf(fp, "%12d", arr[i]);

    fclose(fp);
    delete []arr;

    return 0;
}

4 楼

ckeryradish [专家分：140] 发布于 2008-06-27 22:50:00

晕如果测试的数据中存在一个绝对值很大的数的话，我的算法会立刻恶化。
而如果测试的数据中的所有元素的hash值全部相同的话，使用hash set的算法也会立刻恶化。
每种算法都有各自的劣势。

实在没想到得了个冠军....................

5 楼

Noar [专家分：0] 发布于 2008-06-27 23:38:00

谢了楼主

我来回复

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

主题：第67次编程比赛结果

回复列表（共5个回复）

我来回复

程序员工具箱 new

代码片段

本版新帖

主题：第67次编程比赛结果

回复列表 （共5个回复）

我来回复

程序员工具箱 new

代码片段

本版新帖

回复列表（共5个回复）