订阅业界RSS CSDN首页> 业界

第四期POWER8大赛算法分析:bool量标记排除法

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

摘要:计算10亿以内所有的质数,这是一个很有趣的数学题,但在计算上却不是一件容易的事情。在编程过程中,首先考虑以下几个方面……

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

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

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

到目前为止,已经有数百名开发者报名并参加了此次大赛,为了让更多的开发者更深入了解POWER8大赛的运算技巧。经Power8大赛组委会邀请,第四期POWER8大赛参赛者纪文杰将作对其提交的算法进行剖析。

第四期Power8大赛,纪文杰最终程序运行时间为12.35s。以下是算法具体分析内容:

计算10亿以内所有的质数,这是一个很有趣的数学题,但在计算上却不是一件容易的事情。在编程过程中,首先考虑以下几个方面:硬件能力(文件读写速度、power8的主频等)、算法本身的冗余计算(整数重复判断等),同时在测试中寻找质数产生与数据文件输出的最佳匹配方案。最后通过与其他几位参赛沟通与测试,最终认为bool量标记排除法最适合此次大赛试题。

Step 1:一个整数的最大质数公因子不会超过该数的平方根,首先需要获得10亿的平方根(约为31623)以内的所有质数,31623以内的质数也是取31623的平方根以内的所有质数进行计算。这样,利用质数定义算出前40个质数,再利用前40质数获得31623以内的质数表。

Step 2:建立以1-10亿为偏移量的bool标记数组,全部初始化为false,使用mmap写文件。

Step 3:排除1-10亿中可被2、3、5整除后的数据集合,用数学表达式表示剩下的整数集合,30i + m, (m = 1, 7, 11, 13, 17, 19, 23, 29)在表达式表示的整数集合中循环排除以大于5且小于31623质数表中一个质数为第一项,该质数的30倍为公差的等差数列上的整数,(以质数7为例)能被2,3,5,7整除的整数表达式Y = 7*30*i + 7*m。其中, m = 1, 7, 11, 13, 17, 19, 23, 29,是30(2*3*5)以内的质数;i满足Y < 10^9。在该集合中的整数对应的bool量标记为true(表示该整数不是质数),反之为false。

Step 4: Step 3中获得的数据集合,数据对应bool标记为false的即是质数,写到文件并计数,最后输出质数总数与质数文件。

写在最后,质数文件输出上,我没有过多的测试,只是从基本的几种方法(write、fwrite、mmap),看到网上的测试结果和自己在power8上的测试,mmap比fwrite要快,但也要有8-9秒写完500MB质数文件。

0
0