Java で SoE アルゴを簡単に実装しました (最後にコードを示します)。デュアル コア AMD プロセッサでの出力は次のとおりです。
割り当て: 31 肉: 10140 リスト: 10171 準備終了: 10187
「肉」セクションは、予想どおり最大の時間を消費します。
私が観察したことの 1 つは、 using
Math.pow(variable, 2)は よりも遅いということでした(variable * variable)。関数のジャンプ以外にも、他にもオーバーヘッドがあるのではないかと思います。Math.pow(x, 2) には 2、3 などの累乗の最適化がありますか? Java のネイティブのアルゴリズムよりもはるかに高速な乗算アルゴリズムを備えたユーザー提供の Java ライブラリがいくつかあるため、質問します。
ここに私の質問があります：
肉のセクションにどのような算術最適化を提案できますか? モジュラス演算子を完全に回避する方法はありますか?
start == end の場合、関数は機能しません。sieve(4, 4) を実行すると、返される配列の長さは 1: [4] になります。私は何を間違っていますか？[] (基本的に新しい 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;
}
}