1

Project Euler の問題 10:

プログラムは、より小さな数に対して実行され、10 万単位でゆっくりと実行されます。200 万では、プログラムがまだ実行されているように見えても、回答が表示されません。

エラトステネスのふるいを実装しようとしています。それは非常に速いはずです。私のアプローチの何が問題になっていますか？

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

0

最新の CPUでのエラトステネスのふるいの古典的な実装の効率の鍵は、直接(つまり、非順次)メモリ アクセスです。幸いなことに、ArrayList<E>実装しRandomAccessます。

ふるいの効率のもう 1 つの鍵は、整数の並べ替えと同様に、インデックスと値の融合です。実際にシーケンスから数値を削除すると、計算なしで直接アドレス指定するこの機能が失われます。複合体を見つけたら、削除するのではなく、マークする必要があります。そのため、それよりも大きい数値は、シーケンス内のその場所に残ります。

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 で 0.5 秒で 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.90.5 mln .. 1 mln .. 2 mlnO(N log (log N))

于 2013-06-04T09:32:30.350 に答える
0

2つのこと：

あなたのコードは従うのが難しいです。非素数を含む「素数」と呼ばれるリストがあります!

また、配列リストが適切かどうかをよく検討する必要があります。この場合、LinkedList の方がはるかに効率的です。

どうしてこれなの？配列リストは、配列を作成するために新しいメモリを要求し、新しく作成された配列に古いメモリをコピーすることによって、常に配列のサイズを変更する必要があります。リンクされたリストは、ポインターを変更することでメモリのサイズを変更するだけです。これはずっと速いです！ただし、この変更を行うことでアルゴリズムを救うことができるとは思いません。

アイテムに非連続的にアクセスする必要がある場合は、配列リストを使用する必要があります。ここでは、(適切なアルゴリズムを使用して) アイテムに順番にアクセスする必要があります。

また、あなたのアルゴリズムは遅いです.SJuan76（またはgyrogearless）のアドバイスを受けてください.sjuan76に感謝します

于 2013-06-01T23:54:13.890 に答える
0

あなたのプログラムはエラトステネスのふるいではありません。モジュロ演算子はそれを与えます。あなたのプログラムは O(n^2) になり、適切なエラトステネスのふるいは 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 に答える