java – 改进主筛算法
|
我正在尝试制作一个不错的
Java程序,从1到N生成素数(主要用于Project Euler问题).
目前,我的算法如下： 初始化一个布尔数组(如果N足够大则初始化为bitarray),因此它们都是假的,并且存储了一组用于存储素数的整数. 设置一个整数,s等于最低素数,(即2) s是< = sqrt(N) 在数组/位阵列中将s的所有倍数(从s ^ 2开始)设置为true. 找到array / bitarray中的下一个最小索引,该索引为false,将其用作s的新值. ENDWHILE. 遍历数组/位阵列,对于每个假的值,将相应的索引放在primes数组中. 现在,我尝试跳过不是6k 1或6k 5形式的数字,但这只能让我加速?2倍,而我看到程序的运行速度比我的速度快(尽管代码非常复杂),如一个here 我该怎么做才能改善？ 编辑：好的,这是我的实际代码(对于1E7的N)： int l = 10000000,n = 2,sqrt = (int) Math.sqrt(l);
boolean[] nums = new boolean[l + 1];
int[] primes = new int[664579];
while(n <= sqrt){
for(int i = 2 * n; i <= l; nums[i] = true,i += n);
for(n++; nums[n]; n++);
}
for(int i = 2,k = 0; i < nums.length; i++) if(!nums[i]) primes[k++] = i;
在我的2.0GHz机器上运行大约350ms. 解决方法
s是< = sqrt(N)
人们在这种算法中经常犯的一个错误就是不预先计算平方根. while (s <= sqrt(N)) {
比…慢得多 int limit = sqrt(N);
while (s <= limit) {
但总的来说,Eiko的评论是正确的.如果您希望人们提供低级优化,您必须提供代码. 更新好的,现在关于你的代码. 您可能会注意到代码中的迭代次数比“l”略大. (你可以把计数器放在第一个’for’循环中,它只会大2-3倍)显然,你的解决方案的复杂性不能低于O(l)(你不能低于’l) ‘迭代). 真正有用的是有效地访问内存.请注意,写这篇文章的人试图减少存储空间,不仅仅是因为他的内存贪婪.制作紧凑型阵列可以让您更好地使用缓存,从而提高速度. 我刚用int []替换了boolean []并立即获得了x2速度增益. (和8倍内存)我甚至没有尝试有效地做到这一点. UPDATE2这很简单.您只需用[i / 32] | = 1<<来替换每个赋值a [i] = true (i2)和每个读操作a [i]与(a [i / 32]&(1<(i2)))！= 0.并且boolean [] a与int [] a,显然. 从第一个替换它应该清楚它是如何工作的：如果f(i)为真,那么在整数a [i / 32]中的位1,在位置i2(Java中的int恰好是32位,就像你一样知道). 您可以更进一步,用i>>替换i / 32 5,i2与i& 31.您还可以预先计算所有1<< j为数组中0到31之间的每个j. 但遗憾的是,我不认为在Java中你可以接近C.更不用说,那家伙使用了许多其他棘手的优化,我同意如果他发表评论,他的价值可能会更高. （编辑：李大同） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |