前回の[アルゴリズム]素数を求める～エラトステネスの篩～の改良版を作ってみた
前回作ったものは何も考えずにwikipediaさんに言われた通りそのままにやったのでやっぱり効率が悪かった。
しかも、ある数が素数かどうか調べるためにまたリストを走査しなきゃいけなかった。これは明らかに欠陥ｗ
ってことでboolean配列にして添字の数が素数ならtrueとするようにした
こうするのが本当なんですよねきっとｗ
final int MAX = 1000000 + 1;
boolean[] primes = new boolean[MAX];
primes[2] = true;
for (int i = 3; i < MAX; i += 2) {
primes[i] = true;
}
for (int i = 3; i * i < MAX; i += 2) {
if (primes[i]) {
for (int j = i * 2; j < MAX; j += i) {
primes[j] = false;
}
}
}
やってることは前回と同じ
効率化のために2の倍数は最初から除外するようにした
前回のソースと今回のソースでどれだけ速度が違うかテストしてみました
100万までの素数を求めるまでの時間を計測
前回のと今回のを交互に実行、それぞれ合計11回繰り返し、一番遅かったものを除外
計10回の平均をとりました
これだけ繰り返してるとメモリの確保に時間がかかって大きな誤差が生まれるので
オブジェクト生成の時間は含めないことにしました
Test.java
import java.util.Iterator;
import java.util.LinkedList;
public class Test {
public static void main(String[] args) {
final int N = 10;
long sum = 0, sum2 = 0;
long time;
long m = 0, m2 = 0;
final int MAX = 1000000;
System.out.println("\t前回\t改良版");
for (int i = 1; i <= N+1; i++) {
System.out.print(i + "回目\t");
System.out.print(time = eratosthenes(MAX));
m = Math.max(m, time);
sum += time;
System.out.print("\t");
System.out.println(time = eratosthenes2(MAX));
m2 = Math.max(m2, time);
sum2 += time;
}
System.out.println("-------------------------");
System.out.println("平均\t" + (sum-m)/N + "\t" + (sum2-m2)/N);
}
static long eratosthenes(int max) {
LinkedList primes = new LinkedList();
LinkedList numbers = new LinkedList();
long time = System.currentTimeMillis();
for (int i = 2; i <= max; i++) {
numbers.add(i);
}
int prime;
Iterator it;
do {
prime = numbers.getFirst();
primes.add(prime);
it = numbers.iterator();
while (it.hasNext()) {
if (it.next() % prime == 0)
it.remove();
}
} while (numbers.getLast() > prime * prime);
it = numbers.iterator();
while (it.hasNext()) {
primes.add(it.next());
}
return System.currentTimeMillis() - time;
}
static long eratosthenes2(int max) {
int _max = max + 1;
boolean[] primes = new boolean[_max];
long time = System.currentTimeMillis();
primes[2] = true;
for (int i = 3; i < _max; i += 2) {
primes[i] = true;
}
for (int i = 3; i * i < _max; i += 2) {
if (primes[i]) {
for (int j = i * 2; j < _max; j += i) {
primes[j] = false;
}
}
}
return System.currentTimeMillis() - time;
}
}
出力結果
前回 改良版 1回目 6309 20 2回目 6169 10 3回目 6209 10 4回目 6329 10 5回目 6349 10 6回目 6299 20 7回目 6339 10 8回目 6279 10 9回目 6299 20 10回目 6360 10 11回目 6449 10 ------------------------- 平均 6294 12
違いすぎるｗ
前回のが効率悪すぎただけですねすいませんｗ
{
stage.removeEventListener(Event.ENTER_FRAME, onEnterFrameHandler);
return;
}
var p:Point = new Point(line.endP.x + line.distance * a * Math.cos(line.angle + RAD), line.endP.y + line.distance * a * Math.sin(line.angle+RAD));
var newLine:Line = new Line(line.endP, p);
list.push(newLine);
stage.addChild(newLine);
p = new Point(line.endP.x + line.distance * a * Math.cos(line.angle - RAD), line.endP.y + line.distance * a * Math.sin(line.angle - RAD));
newLine = new Line(line.endP, p);
list.push(newLine);
stage.addChild(newLine);
}
}
}
