4

我用 Java 快速实现了 SoE 算法（代码在最后）。我的双核 AMD 处理器上的输出是：

分配：31
肉类：10140
上市：10171
筹备结束：10187

  • 正如预期的那样，“肉类”部分消耗了最长时间。

  • 我的一个观察结果是 usingMath.pow(variable, 2)比(variable * variable). 我认为除了函数跳转之外，可能还有其他开销。

  • Math.pow(x, 2) 是否对 2、3 等的幂进行了优化？我问是因为那里有一些用户贡献的 Java 库，它们的乘法算法比 Java 的本机算法快得多。

以下是我的问题：

  • 您可以向“肉类”部分建议哪些算术优化？有什么办法可以完全避免模运算符？

  • 当 start == end 时该功能不起作用。如果我做 sieve(4, 4)，返回的数组长度为 1: [4]。我究竟做错了什么？它应该返回 []（基本上是 new int(0)）。

  • 您知道哪些与快速数字/数学相关的 Java 库？

谢谢阅读。最后这是我写的代码：不是 GangOfFour/TopCoder 质量，但也不是太可悲（我希望！而且 SO 的代码格式有点……奇怪？）：

import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;
public class Sieve {

    public static void main(String[] args) {

        /* small test */
        int[] primes = sieve(1, 1000000);
    }

    /**
     * returns an array of prime integers
     * in the given range
     * 
     * @param start     range start
     * @param end       range end
     * @return
     */
    private static int[] sieve(int start, int end) {

        long startTime = System.currentTimeMillis();

        /* some basic range checks */
        if(end < start || start < 1 || end  < 1) {
            throw new ArithmeticException("Messed up input");
        }

        /* generate ints within range */
        int[] naturals = new int[end-start+1];
        for (int j = 0; j < end - start + 1; j++) {
            naturals[j] = start + j;
        }
        System.out.println("Allocation: \t" + (System.currentTimeMillis() - startTime));

        /* init running prime to start, and increment until
         * running prime squared is greater than the end
         */
        for (int runningPrime = (start == 1 ? 2: start); end > runningPrime*runningPrime; runningPrime++) {
            for (int i = runningPrime; i < naturals.length; i++) {
                if(-1 != naturals[i]) {
                    if(naturals[i] % runningPrime == 0) {
                        naturals[i] = -1;
                    }
                }
            }
        }
        System.out.println("Meat: \t\t" + (System.currentTimeMillis() - startTime));

        if(naturals[0] == 1) {
            naturals[0] = -1;
        }

        /* list primes */
        List list = new ArrayList();
        for (int i = 0; i < naturals.length; i++) {
            if(-1 != naturals[i])
                list.add(naturals[i]);
        }
        System.out.println("Listing: \t" + (System.currentTimeMillis() - startTime));

        /* create the return int array */
        int[] primes = new int[list.size()];
        int k = 0;
        for (Iterator iterator = list.iterator(); iterator.hasNext();) {
            primes[k++] = ((Integer) iterator.next()).intValue();
        }

        System.out.println("Preparing end: \t" + (System.currentTimeMillis() - startTime));
        return primes;
    }
}

感谢所有的反馈。这是下面的固定版本（直到有人设法再次打破它:)

import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;

public class Sieve {
    public static void main(String[] args) {
        /* small test */
        int[] primes = sieve(2, 5);
        System.out.println("Number of primes: " + primes.length);
        for (int i : primes) {
            System.out.println(i);
        }
    }

/**
 * returns an array of prime integers
 * in the given range
 * 
 * @param start     range start
 * @param end       range end
 * @return
 */
private static int[] sieve(int start, int end) {

    long startTime = System.currentTimeMillis();

    /* some basic range checks */
    if(end < start || start < 1 || end  < 1) {
        throw new ArithmeticException("Messed up input");
    }

    /* generate ints within range */
    int[] naturals = new int[(int)Math.floor((end-start+1) / 2) + 1];
    int allocator = 0;
    for (int j = 0; j < end - start + 1; j++) {
        if(!((start + j) % 2 == 0)) {
            naturals[allocator++] = start + j;
        }
    }
    System.out.println("Allocation: \t" + (System.currentTimeMillis() - startTime));

    /* init running prime to 2, and increment until
     * running prime squared is greater than the end
     */
    for (int runningPrime = 2; end >= runningPrime*runningPrime; runningPrime++) {
        for (int i = 0; i < naturals.length; i++) {
            if(-1 != naturals[i]) {
                if(naturals[i] != runningPrime && naturals[i] % runningPrime == 0) {
                    naturals[i] = -1;
                }
            }
        }
    }
    System.out.println("Meat: \t\t" + (System.currentTimeMillis() - startTime));

    if(naturals[0] == 1) {
        naturals[0] = -1;
    }

    /* list primes */
    List list = new ArrayList();
    for (int i = 0; i < naturals.length; i++) {
        if(-1 != naturals[i])
            list.add(naturals[i]);
    }
    System.out.println("Listing: \t" + (System.currentTimeMillis() - startTime));

    /* create the return int array */
    int size = list.size();
    int k = 0;

    /* tricky tricky :) */
    if(start <= 2) {
        size += 1;
        k = 1;
    }

    int[] primes = new int[size];

    if(start <= 2) {
        primes[0] = 2;
    }

    for (Iterator iterator = list.iterator(); iterator.hasNext();) {
        primes[k++] = ((Integer) iterator.next()).intValue();
    }

    System.out.println("Preparing end: \t" + (System.currentTimeMillis() - startTime));
    return primes;
    }
}
4

5 回答 5

3

您可以通过重写内部循环来避免取模：

        for (int i = runningPrime; i < naturals.length; i++) {
            if(-1 != naturals[i]) {
                if(naturals[i] % runningPrime == 0) {
                    naturals[i] = -1;
                }
            }
        }

作为

        for (int i = runningPrime; i < naturals.length; i+=runningPrime) {
             naturals[i] = -1;
        }

我也有点担心包含start参数会使事情复杂化（考虑到 的情况sieve(4, 10)）。

于 2010-11-11T15:23:58.907 回答
1

您的解决方案不是埃拉托色尼筛。这很明显，因为您modulo在代码中使用了运算符；适当的 Eratosthenes 筛法仅在内循环中使用加法，而不是除法或模数。这是埃拉托色尼筛法的一个简单版本，它从小于 n 的素数导入和返回BitSet一个LinkedList ：LinkedListjava.util

public static LinkedList sieve(int n)
{
    BitSet b = new BitSet(n);
    LinkedList ps = new LinkedList();

    b.set(0,n);

    for (int p=2; p<n; p++)
    {
        if (b.get(p))
        {
            ps.add(p);
            for (int i=p+p; i<n; i+=p)
            {
                b.clear(i);
            }
        }
    }

    return ps;
}

基本思想是创建一个筛子（BitSet b），每个项目最初设置为Prime（表示为一个设置位），遍历筛子寻找并报告每个连续的素数，当找到一个从通过标记筛选Composite（表示为清除位）。倍数是通过加法而不是除法找到的，并且内部循环仅由加法，位清除操作，比较以寻找筛子的结尾，以及跳回到循环的开头，所以它非常快。

有一些优化可以使埃拉托色尼筛运行得更快，但这应该足以让您开始。当你准备好更多时，我谦虚地在我的博客上推荐这篇文章。

如果您想要一个不从零开始的范围内的素数，您需要一个分段的 Eratosthenes 筛。我之前在 Stack Overflow 上讨论了 Eratosthenes 的分段筛，也在我的博客上讨论过它。

于 2013-02-01T03:57:50.393 回答
1

假设我没有错过我要写的东西：

 for(int runningPrime = (start == 1 ? 2: start); end > runningPrime*runningPrime;
 runningPrime++)

作为

int limit = Math.sqrt(end);
for(int runningPrime = (start == 1 ? 2: start); runningPrime < limit; 
runningPrime++)

以防止每次迭代不必要的乘法。此外，我只会用奇数填充数组，有效地将其长度减半。

于 2010-11-11T15:20:04.630 回答
0

仅填充赔率（除了 2）、通过 runningPrime 递增和失去可分性检查（已经建议）可能是最重要的优化。

Java 的 Math.pow 用于双打！它没有对平方进行优化，主要是因为它立即将 2 重铸为双精度数。

于 2010-11-11T15:43:51.127 回答
0

在我看来，在开始优化之前，你应该修复两个严重的错误。

我将您的代码编译为 Java 程序，然后尝试计算

sieve(1, 9)

和

sieve(4,10);

第一种情况正常工作，只是 9 被认为是素数。9 的平方根是一个素数，但您的循环条件会在您到达那里之前停止筛分。

在第二种情况下，所谓的素数是 4、5、6、7、8、9、10。这是因为您跳过了范围开始以下的任何素数的筛选。那，恐怕是优化太远了:-)

于 2010-11-11T16:27:15.003 回答