1

来自 Project Euler 的问题 10：

该程序针对较小的数字运行，并在数十万中缓慢爬行。在 200 万时，即使该程序似乎仍在运行，也无法显示答案。

我正在尝试实施Eratosthenes 的筛子。它应该非常快。我的方法有什么问题？

import java.util.ArrayList;

public class p010
{
  /**
   * The sum of the primes below 10 is 2 + 3 + 5 + 7 = 17
   * Find the sum of all the primes below two million.
   * @param args
   */
  public static void main(String[] args)
  {
    ArrayList<Integer> primes = new ArrayList<Integer>();
    int upper = 2000000;
    for (int i = 2; i < upper; i++)
    {
      primes.add(i);
    }
    int sum = 0;
    for (int i = 0; i < primes.size(); i++)
    {
      if (isPrime(primes.get(i)))
      {
        for (int k = 2; k*primes.get(i) < upper; k++)
        {
          if (primes.contains(k*primes.get(i)))
          {
            primes.remove(primes.indexOf(k*primes.get(i)));
          }
        }
      }
    }
    for (int i = 0; i < primes.size(); i++)
    {
      sum += primes.get(i);
    }
    System.out.println(sum);
  }

  public static boolean isPrime(int number)
  {
    boolean returnVal = true;
    for (int i = 2; i <= Math.sqrt(number); i ++)
    {
      if (number % i == 0)
      {
        returnVal = false;
      }
    }
    return returnVal;
  }

}
4

5 回答 5

5

您似乎正在尝试实施 Eratosthenes 筛子，它应该表现得更好O(N^2)（事实上，维基百科说它是O(N log(log N))......）。

根本问题是您对数据结构的选择。您已选择将剩余的素数候选集表示为ArrayList素数。这意味着您要查看一个数字是否仍在集合中的测试需要O(N)进行比较......N剩余素数的数量在哪里。然后你正在使用ArrayList.remove(int)删除非素数......这O(N)也是。

所有这些加起来使您的 Sieve实现比O(N^2).

解决方案是将 替换为ArrayList<Integer>数组boolean[]中的位置（索引）boolean表示数字的位置，布尔值表示该数字是素数/可能是素数，还是不是素数。

（还有其他我没有注意到的问题......请参阅其他答案。）

于 2013-06-02T00:53:57.433 回答
3

这里有几个问题。首先，让我们谈谈算法。您的isPrime方法实际上正是筛子旨在避免的事情。当您在筛子中找到一个数字时，您已经知道它是质数，您无需对其进行测试。如果它不是素数，它已经作为一个较小数字的因素被消除了。

所以，第 1 点：

  • 您可以完全消除该isPrime方法。它永远不应该返回 false。

然后，存在实施问题。primes.contains并且primes.remove是问题。它们在 上以线性时间运行ArrayList，因为它们需要检查每个元素或重写后备数组的大部分。

第 2 点：

  • 将值标记到位（使用boolean[]，或使用其他更合适的数据结构。）

我通常使用类似boolean primes = new boolean[upper+1], 并定义n为包含 if !(primes[n])。（我只是忽略元素 0 和 1，所以我不必减去索引。）要“删除”一个元素，我将其设置为 true。我想你也可以使用类似TreeSet<Integer>的东西。使用boolean[]，该方法几乎是瞬时的。

第 3 点：

  • sum需要很长。答案（大约 1.429e11）大于整数的最大值（2^31-1）

如果你愿意，我可以发布工作代码，但这是一个测试输出，没有剧透：

public static void main(String[] args) {
    long value;
    long start;
    long finish;

    start = System.nanoTime();
    value = arrayMethod(2000000);
    finish = System.nanoTime();
    System.out.printf("Value: %.3e, time: %4d ms\n", (double)value, (finish-start)/1000000);

    start = System.nanoTime();
    value = treeMethod(2000000);
    finish = System.nanoTime();
    System.out.printf("Value: %.3e, time: %4d ms\n", (double)value, (finish-start)/1000000);
}

输出：

Using boolean[]
    Value: 1.429e+11, time:   17 ms
Using TreeSet<Integer>
    Value: 1.429e+11, time: 4869 ms

编辑： 由于发布了剧透，这是我的代码：

public static long arrayMethod(int upper) {
    boolean[] primes = new boolean[upper+1]; 
    long sum = 0;
    for (int i = 2; i <=upper; i++) {
        if (!primes[i]) {
            sum += i;
            for (int k = 2*i; k <= upper; k+=i) {
                primes[k] = true;
            }
        }
    }
    return sum;
}

public static long treeMethod(int upper) {
    TreeSet<Integer> primes = new TreeSet<Integer>();
    for (int i = 2; i <= upper; i++) {
        primes.add(i);
    }
    long sum = 0;
    for (Integer i = 2; i != null; i=primes.higher(i)) {
        sum += i;
        for (int k = 2*i; k <= upper; k+=i) {
            primes.remove(k);
        }
    }
    return sum;
}
于 2013-06-02T00:11:23.277 回答
0

两件事情：

您的代码很难遵循。您有一个名为“素数”的列表，其中包含非素数！

此外，您应该认真考虑数组列表是否合适。在这种情况下，LinkedList 会更有效率。

为什么是这样？数组列表必须通过以下方式不断调整数组的大小：请求新内存来创建数组，然后将旧内存复制到新创建的数组中。链接列表只会通过更改指针来调整内存大小。这要快很多！但是，我不认为通过进行此更改可以挽救您的算法。

如果您需要非顺序访问项目，您应该使用数组列表，在这里，（使用合适的算法）您需要顺序访问项目。

另外，你的算法很慢。听从 SJuan76（或 gyrogearless）的建议，谢谢 sjuan76

于 2013-06-01T23:54:13.890 回答
0

你的程序不是埃拉托色尼的筛子；模运算符给出了它。您的程序将是 O(n^2)，其中适当的 Eratosthenes 筛子是 O(n log log n)，本质上是 n。这是我的版本；我将把它留给你用适当的数字数据类型翻译成 Java：

function sumPrimes(n)
    sum := 0
    sieve := makeArray(2..n, True)
    for p from 2 to n step 1
        if sieve[p]
            sum := sum + p
            for i from p * p to n step p
                sieve[i] := False
    return sum

如果你对使用素数编程感兴趣，我在我的博客上谦虚地推荐这篇文章。

于 2013-06-02T02:24:09.160 回答
0

在现代 CPU 上经典实现Eratosthenes 筛的效率的关键是直接（即非顺序）内存访问。幸运的是，ArrayList<E>确实实现了RandomAccess.

筛子效率的另一个关键是它的索引和值的混合，就像整数排序一样。实际上从序列中删除任何数字都会破坏这种无需任何计算即可直接寻址的能力。我们必须在找到它们时标记而不是删除任何组合，因此任何大于它的数字都将保留在序列中的位置。

ArrayList<Integer>可以用于此（除了占用比严格必要的更多的内存，但对于 200 万这是无关紧要的）。

因此，您的代码具有最小的编辑修复（也更改sum为long其他人指出的那样），变为

import java.util.ArrayList;

public class Main
{
  /**
   * The sum of the primes below 10 is 2 + 3 + 5 + 7 = 17
   * Find the sum of all the primes below two million.
   * @param args
   */
  public static void main(String[] args)
  {
    ArrayList<Integer> primes = new ArrayList<Integer>();
    int upper = 5000;
    primes.ensureCapacity(upper);
    for (int i = 0; i < upper; i++) {
      primes.add(i);
    }
    long sum = 0;
    for (int i = 2; i <= upper / i; i++) {
      if ( primes.get(i) > 0 ) {
        for (int k = i*i; k < upper ; k+=i) {
          primes.set(k, 0);
        }
      }
    }
    for (int i = 2; i < upper; i++) {
      sum += primes.get(i);
    }
    System.out.println(sum);
  }
}

在 Ideone 上半秒内找到 2000000 的结果。您的原始代码的预计运行时间：10 到 400 小时（！）。

当遇到慢代码时，要粗略估计运行时间，你应该总是尝试找出它的经验增长顺序：运行一些小尺寸n1，然后更大尺寸n2，记录运行时间t1和t2. 如果t ~ n^a，那么a = log(t2/t1) / log(n2/n1)。

10k .. 20k .. 40k对于您的原始代码，在上限值范围内测量的经验增长顺序N是~ N^1.7 .. N^1.9 .. N^2.1。对于固定代码，它比~ N（事实上，它~ N^0.9在测试范围内0.5 mln .. 1 mln .. 2 mln）更快。理论复杂度为O(N log (log N)).

于 2013-06-04T09:32:30.350 回答