订阅业界RSS CSDN首页> 业界

第四期POWER8大赛算法分析:欧拉筛选法

发表于2015-04-09 11:22| 次阅读| 来源未知| 0 条评论| 作者李洪亮

摘要:到目前为止,已经有数百名开发者报名并参加了此次大赛,为了让更多的开发者深入了解题目的运算技巧。Power8大赛组委会邀请大赛参赛者刘毅超,对本次“计算质数”大赛进行算法分析。

CSDNIBM联合举办的“2014 Power 8极限性能挑战赛”自正式启动以来,受到了许多编程爱好者及程序员们的关注。 该大赛以云计算的方式为开发者提供了Power 8开发环境,开发者将利用Power 8的特性,基于不同场景进行应用开发。

此次大赛主要面向广大CSDN注册开发者,大赛以云计算的方式为开发者提供了Power 8开发环境,开发者利用Power 8的特性,基于不同场景进行应用开发。此次大赛,不仅使更多的开发者充分利用了Power 8,也为开发者、技术达人提供一个展示自我的舞台。

Power 8极限性能挑战赛已成功举办三期。(第一期“博客反垃圾”、第二期“敏感词大文本过滤”第三期“文章TOP 100”)。现在,我们又迎来了极限算法挑战赛第四期本期挑战赛的题目是“计算质数”,具体任务由用户自由输出1-10亿内所有质数。需要说明的是,大赛主要考察程序的是算法的正确率及处理速度,对开发语言、开发工具并不进行限定。

到目前为止,已经有数百名开发者报名并参加了此次大赛,为了让更多的开发者深入了解题目的运算技巧。Power8大赛组委会邀请大赛参赛者刘毅超,对本次“计算质数”大赛进行算法分析。

此次Power8大赛比赛中,刘毅超提交程序最终的运行时间为3.15s,下面算法的具体分析:

int tot = 0;

for(int i=2;i<=N;i++){

         if(!check[i]){

                   prime[tot ++] = i;

         }

         for(int j=0;j<tot;j++){

                   if(i*prime[j]>N)break;

                   check[i*check[j]] = true;

                   if(i%prime[j])break;

         }

}

每个合数只会被它最小的质因数筛去,因此时间复杂度接近ON

我们知道所有的质数都是奇数(不考虑2)。那么我们完全可以从三开始,依次加2。同样,我们可以从5开始,依次加2,再加4.同样,我们可以这样把5的倍数们筛去。本人的程序只去除了23的倍数。

使用多线程:

void calInterval(int l, int r){

         l = l / 6 * 6 - 1;

         if (l < 0) l += 6;

         int conter = ct;

         for (long long i = l; i < r&&i < mx; i += 4){

                   for (int j = 2; j < conter && i >= prime[j] && i*prime[j]<mx; j++){

                            check[i*prime[j]] = 1;

                            if (i%prime[j] == 0)

                                     break;

                   }

                   i += 2;

                   if (i >= r)break;

                   for (int j = 2; j < conter && i >= prime[j] && i*prime[j]<mx; j++){

                            check[i*prime[j]] = 1;

                            if (i%prime[j] == 0)

                                     break;

                   }

         }

}

prime数组是一个小范围的素数,保证不存在更大的素数P,使得P*P>N.

值得一提的是,许多参赛者只考虑排除掉23的情况。如果排除5,将会加快运算速度。

int pos[9]={0,65000,250000,2600000,16500000,65000000,170000000,650000000,mx};

上面这是本人运用8个线程处理的8个区间,用多个线程同时排除不同区间的素数。

最后验证发现,多线程并不能使性能接近线性提高。原因是访问内存太慢,cache并不大,命中率无法提高。

经过此次验证得出来一个经验,一定要考虑cache的问题从而提高性能。例如,使用区间筛法,应该根据cache大小来优化。

输出:筛选之后,需要找到未被标记为true的位置,同样只找到不是235的倍数的位置,以此来减小复杂度。

多线程将不同区间的素数进行统计,并且将该区间的数字整理成多个字符串,每个字符串的大小为一个适宜的数据块大小,最后一个字符串大小为应有的长度。将这些数据块,通过fwrite依次输出,效率极高。

0
0