编程C,C ++,Java,PHP,Ruby,图灵,VB
计算机科学加拿大 
编程C,C ++,Java,PHP,Ruby,图灵,VB  

用户名:   Password: 
 登记登记   
 [表现]击败了我最佳时间的裤子
指数 -> 竞赛
转到页面 1, 2  下一页
查看上一个主题 可打印的版本下载主题订阅本主题私人信息刷新页面 查看下一个主题
作者 信息
魔鬼




邮政发布: 星期四,2008年7月31日晚上8:34  帖子主题:[性能]击败了我最佳时间的裤子

我相信你们中的一些人比我的编码更聪明,更好。我真的很奇怪的代码优化......以及如何使计算机快速运行。所以,我想看到一些比我更好的代码(并且一些代码比我的代码更糟糕,所以我不会感到太糟糕的是一个巨大的菜鸟)。我姿势的问题很简单:


使用您选择的语言和方法,查找和列出1(非常大)之间的所有素数......尽可能快地。

您需要能够将您的结果输出到文件,或者(例如,您可以使用命令行参数)。
您需要在运行程序时给我一些修改n的方式(我想运行几个不同的n值,所以我可以制作一个漂亮的图形或somesuch)。

理想情况下,击败我的实现:
代码:

使用文件输出
N       Time (seconds, approximate)
10M     < 0.8
100米    9
1B      92

没有输出
N       Time (seconds, approximate)
10M     < 0.3
100米    6
1B      65


比赛结束时,我会发布我的实施。我很确定它是对的,但我可能是错的 - 我只手动检查最多100左右的数字。

预期文件大小,根据我的实现(每个数字在其自己的线上)
10m - > ~5.0 MB
100米 - > 48.7 MB
1B - > 478.7 MB


规则:
这主要是为了乐趣(我几乎没有捐赠,虽然我想要位为顺序)。最后的获奖者将在我的一台计算机上判断(可能是笔记本电脑或新桌面)。

2.我可以在C,C ++或Java代码中运行任何内容:
2.A)C(++)中的任何内容都与G ++或GCC(版本4.2.3)编译
2.b)Java中的任何内容都必须能够使用JVM 1.6.0_06运行

3.我可以提供备用语言,只要:
3.A)您将我指出,用于安装必要的工具
3.b)所需的工具是免费的,在Ubuntu或Windows XP上可用。然而,我更愿意在Ubuntu中保持测试。

4.您的程序必须编译和执行,没有错误,塞格福尔或其他顽皮。失败的程序将不会被计算在内。

5.如果你击败我的时间超过50%,史诗般的胜利。

6.是的,我知道这个问题的优化是奇迹,但我发现它有趣。

计算机规格,对于那些好奇的人:
桌面:E6600 @ 2.4GHz,2GB DDR2 RAM,64位Ubuntu 8.04.1,Seagate上的Reiserfs 7200.10
笔记本电脑:T5400 @ 1.66GHz(锁定),2GB DDR2 RAM,32位Ubuntu 8.04.1,EXT3上的WD 120GB驱动器
>>在你提醒我之前,我会用拱门或Gentoo更好的纯粹表现,让我突破你:我是一个巨大的linux noob,所以它是一个奇迹完全正确安装了ubuntu。
赞助
赞助
赞助
赞助
Rizzix.




邮政发布: 星期四,2008年7月31日10:48 PM  帖子主题:Re:[性能]击败我最佳时间的裤子

嗯,原始速度将(最有可能)通过低级C + SIMD扩展获得。假设所有实现使用相同的算法(当然假设您的算法可以利用SIMD扩展,则无法击败该速度。

而且,其次,Ubuntu实际上优化了。 微笑
魔鬼




邮政发布: 星期四,2008年7月31日下午11:35  帖子主题:Re:[性能]击败我最佳时间的裤子

所以?继续发布一些东西,我有兴趣看到它。供参考,我的实现是java,所以我确定 某人 可以弄清楚一个击败它的方法(我有一个c版本,但我还没有为它做文件io)。
Rizzix.




邮政发布: 星期四,2008年7月11日下午11:51  帖子主题:Re:[性能]击败我最佳时间的裤子

引用:
所以?
嗯,我正在质疑这一挑战的目的。
魔鬼




邮政发布: 星期四,2008年7月31日11:54 PM  帖子主题:Re:[性能]击败我最佳时间的裤子

我想看看这样的东西。我很奇怪地在实际表现关键的应用中完成的,而不是我现在正在工作的东西(测试代码是跛脚)。

加上这是我的半分手试图呼吸一些人的生命回到Compsci.ca ......这个论坛在夏令时变得非常无聊。
Rizzix.




邮政发布: 星期五2008年8月1日上午12:00  帖子主题:Re:[性能]击败我最佳时间的裤子

啊那么好。但是,我可以建议你参加的每个人都应该从他们的基准中排除他们程序的“启动”时间?毕竟,你做到了,在你的Java实现中。另外指定运行的数量和每个运行中使用的不同数据集的数量。
魔鬼




邮政发布: 星期五2008年8月1日12:57 AM  帖子主题:Re:[性能]击败我最佳时间的裤子

啊,好的,可能是一个良好的计划:

排除您的启动时间(但不是内存分配):
我从Eclipse内运行了我的测试(使用相同的JVM),因此您可以排除启动时间(在C程序的情况下可能会忽略不计;实际上没有时间进入Main())。尽可能准确地完成所有的时间,或者依靠我正确使用时间命令......

审判过程
在测试每个程序时,我将花5个运行和平均结果为n = 10m,100m和1b。假设我有时间,我会在没有文件IO的情况下做两个,但我会先用文件IO做。当然,您欢迎来到自己的测试。只要我自己的测试终止并获得等级“LOLCAT”而不是实际时间(有时候非常懒惰),那么运行超过五倍的测试。
taferret.




邮政发布: 星期五2008年8月1日上午6:17  帖子主题:Re:[性能]击败我最佳时间的裤子

http://ferret22ca.googlepages.com/soln.txt 是我在java的解决方案,它可以基本上削减了我的系统上的一半......(amd x2 4200+,4GB RAM,Vista 64bit)将其运行而不破坏Java,您必须在您使用时使用-xmx1224m将其编译为10亿或java将抱怨在内存中......更改数字,只需将最大更改为所需的任何数字......

P.S.我要试着更难的筛子,但然后我懒得......哈哈
赞助
赞助
赞助
赞助
Zylum.




邮政发布: 星期五2008年8月1日7:06 AM  帖子主题:Re:[性能]击败我最佳时间的裤子

我的C解决方案在使用-o标志编译时在约37秒内运行,在1B案例上没有输出......它只使用1B位,所以它没有太糟糕的空间明智。这是具有夫妇优化的基本筛子,用于速度和空间。

C:
#包括<stdio.h>
#包括<time.h>
int main(int argc,char * argv []) {
       clock_t时间=时钟();
        int N = atoi(argv[1]);
        uint p[N/32+1];
        int i, j, NP = 0;
        for (i = 0; i <= N>>5; i++) p[i] = 0;
        for (i = 2; i < sqrt(N); i++)
                if (0 == (p[i>>5] & (1 << ((i-1) & 31))))
                        for (j = i<<1; j < N; j += i)
                                p[j>>5] |= 1 << ((j-1) & 31);
        for (i = 2; i < N; i+=2)
                if (0 == (p[i>>5] & (1 << ((i-1) & 31)))) {
                        NP++;
                        //printf("\n%d", i);
                }
        printf("\nPRIMES: %d\n", NP+1);
        printf("TIME: %d\n", clock() - time);
        return 0;
}
Zeroth.




邮政发布: 星期五2008年8月1日上午8:15  帖子主题:Re:[性能]击败我最佳时间的裤子

魔鬼在哪里的代码?这个想法是我们应该知道你做了什么,以及你使用的算法。我很快就会去旅行,所以我不能参加。所以,相反,我会用包含最快的主要发现算法的纸张留下所有纸张。

http://citeseer.ist.psu.edu/atkin99prime.html

如果我有时间,我会在大会中实施。 扭曲邪恶
魔鬼




邮政发布: 星期五2008年8月1日8:26 AM  帖子主题:Re:[性能]击败我最佳时间的裤子

@Theferret:你的解决方案似乎快速运行(我没有工作中没有参考机器,所以我在服务器类机上测试了它;我必须在回家时检查。它似乎很好,但是,我很难相信这是完全相同的算法的时间不到一半。

也许我应该手动彻底终结我拥有的访问者方法和输出方法。方法调用可能会产生巨大的差异,并且Java可能不会像它一样纳入它们。

@Zylum:您的解决方案拒绝在工作中编译机;它抱怨不知道uint和atoi。我只能假设这是我的错,因为我是一个巨大的n noob ...有帮助吗?

很好地完成了......假设您的解决方案尽可能快地求助,您很好,真正打败了我。
魔鬼




邮政发布: 周五8月1日,2008年8:31 AM  帖子主题:Re:[性能]击败我最佳时间的裤子

@zeroth:我用了一个简单的攻击算法(它以某人命名,但我不记得他们的名字)。它是这样的:

1.假设每个数字都是素数。
2.从n = 2开始,每当n是素数时,消除n的倍数,顺序地进行;列出您消除的每个N,因为您这样做。

我目前的代码是一团糟,而不是我的。我实施的东西比我必须更多的企业(例如,使用输出方法而不是在那里的行)。我会清理它,再次测试它,然后允许它显示它在这里的丑陋面孔。
Zylum.




邮政发布: 星期五2008年8月1日11:32 AM  帖子主题:Re:[性能]击败我最佳时间的裤子

我在Cygwin上编写了GCC,所以它应该在Linux下编译精细 非难
蜡烛




邮政发布: 星期五2008年8月1日11:42 AM  帖子主题:Re:Re:[性能]击败我最佳时间的裤子

魔鬼@ 2008年8月1日,08:31写道:
@zeroth:我用了一个简单的攻击算法(它以某人命名,但我不记得他们的名字。

筛子的筛子
魔鬼




邮政发布: 星期五2008年8月1日12:44 PM  帖子主题:Re:[性能]击败我最佳时间的裤子

@zylum:你能给确切的命令行吗?这可能不是链接你的东西。什么文件夹我把它置于什么关系?

@vermette:谢谢。
从上一个显示帖子:   
   指数 -> 竞赛
查看上一个主题 告诉一个朋友可打印的版本下载主题订阅本主题私人信息刷新页面 查看下一个主题

12  [ 25 Posts ]
转到页面 1, 2  下一页
跳到:   


Style:  
搜索: