提高黄金筛算法 [英] Improving a prime sieve algorithm

问题描述

我试图使生成的素数从1到N（主要为项目欧拉问题），一个像样的Java程序。

I'm trying to make a decent Java program that generates the primes from 1 to N (mainly for Project Euler problems).

目前，我的算法如下：

初​​始化boolean数组（或bitarray如果N足够大），所以他们都是假的，int数组存储素数发现。

Initialise an array of booleans (or a bitarray if N is sufficiently large) so they're all false, and an array of ints to store the primes found.

设置一个整数，S等于最低的黄金（即2）

Set an integer, s equal to the lowest prime, (ie 2)

虽然小号为＆lt; = SQRT（N）的

While s is <= sqrt(N)

设置在阵列/ bitarray第（从S开始^ 2）为true的倍数。

Set all multiples of s (starting at s^2) to true in the array/bitarray.

查找下一个最小的指数在数组/ bitarray这是假的，使用它作为s的新值。

Find the next smallest index in the array/bitarray which is false, use that as the new value of s.

ENDWHILE。

穿过阵列/ bitarray，并为每个值是假的，放在素数数组对应的索引。

Go through the array/bitarray, and for every value that is false, put the corresponding index in the primes array.

现在，我已经试过跳绳形式6K + 1和6K + 5的数字上，而是只给了我〜2倍加速，虽然我已经看到了程序运行几个量级的速度比我的（虽然非常令人费解code），如一个这里

Now, I've tried skipping over numbers not of the form 6k + 1 or 6k + 5, but that only gives me a ~2x speed up, whilst I've seen programs run orders of magnitudes faster than mine (albeit with very convoluted code), such as the one here

我能做些什么来改善？

编辑：好了，这里是我的实际code（N个1E7的）：

Okay, here's my actual code (for N of 1E7):

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;

运行在大约350毫秒我的2.0GHz的机器。

Runs in about 350ms on my 2.0GHz machine.

推荐答案

虽然s是＆LT; =开方（N）的
一个错误的人经常做这样的算法并不precomputing平方根。

While s is <= sqrt(N)
One mistake people often do in such algorithms is not precomputing square root.

while (s <= sqrt(N)) {

是多少，比

int limit = sqrt(N);
while (s <= limit) {

但总体上看，英子的是正确的，他的评论。如果你希望人们提供低层次的优化，你必须提供code。

But generally speaking, Eiko is right in his comment. If you want people to offer low-level optimisations, you have to provide code.

更新确定，现在你的code。

update Ok, now about your code.

您可能会注意到在code表示迭代次数比'L'大只一点。 （你可以将柜台内的第一个for循环，这将是只有2-3倍大），很明显，你的解决方案的复杂性，不能小于0（1），（你不能低于L 迭代）。

You may notice that number of iterations in your code is just little bigger than 'l'. (you may put counter inside first 'for' loop, it will be just 2-3 times bigger) And, obviously, complexity of your solution can't be less then O(l) (you can't have less than 'l' iterations).

是什么让真正的区别在于有效地访问内存。注意那个家伙是谁写的那篇文章试图减少存储容量不仅仅是因为他的记忆贪婪。使紧凑的阵列，您可以使用缓存更好，从而提高速度。

What can make real difference is accessing memory effectively. Note that guy who wrote that article tries to reduce storage size not just because he's memory-greedy. Making compact arrays allows you to employ cache better and thus increase speed.

我刚刚更换布尔[]为int []，并取得了立竿见影X2速度增益。 （和8倍的内存），我甚至没有尝试有效地做到这一点。

I just replaced boolean[] with int[] and achieved immediate x2 speed gain. (and 8x memory) And I didn't even try to do it efficiently.

UPDATE2
那很简单。您只需更换每一项任务 A [1] = TRUE 与 A [1/32] | = 1＆LT;＆LT; （I％32）每读操作 A [1] 与（A [1/32]及（ 1所述;≤（则i％32）））= 0 ！。而布尔[]一个与 INT []一个，效果显着。

update2
That's easy. You just replace every assignment a[i] = true with a[i/32] |= 1 << (i%32) and each read operation a[i] with (a[i/32] & (1 << (i%32))) != 0. And boolean[] a with int[] a, obviously.

从第一个替换，应该清楚它是如何工作的：如果 F（I）是真实的，那么就有点 1 在整数 A [1/32] ，在位置 I％32 （ INT Java中正好有32位，如你所知）。

From the first replacement it should be clear how it works: if f(i) is true, then there's a bit 1 in an integer number a[i/32], at position i%32 (int in Java has exactly 32 bits, as you know).

您可以更进一步，取代 I / 32 与 I＆GT;＆GT; 5 ， I％32 与 I和31 。您也可以precompute所有 1＆LT;＆LT; Ĵ在阵列之间0和31各学家

You can go further and replace i/32 with i >> 5, i%32 with i&31. You can also precompute all 1 << j for each j between 0 and 31 in array.

但可悲的是，我没有在Java中认为你可以亲近到C本。更何况，那家伙用了许多其他棘手的优化和我同意，他可能会一直值钱得多，如果他提出的意见。

But sadly, I don't think in Java you could get close to C in this. Not to mention, that guy uses many other tricky optimizations and I agree that his could would've been worth a lot more if he made comments.

这篇关于提高黄金筛算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！