はじめに
前回の投稿のコードは、@swordone さんからの指摘で「リストを全探査して割り算して篩い落とす」という高コストなコードだと判明しました。
そこで、@swordone さんから頂いたヒントを基にして、コードを大幅に直してみました。
コード
前回のコードとの違いは以下の通りです。
- 探索リストを
List<Integer>
からboolean[]
に変更。- 「2から上限値までのリスト」の代わりに、「2から上限値までの添え字のリスト」としました。
- 最初に配列の全要素を素数扱い(true)としておき、篩い落とす時に素数以外の値(false)としました。
- 「リストを全探査して割り算して篩い落とす」のではなく、「篩い落とす値の要素にランダムアクセスして篩い落とす」形に変更。
- for文のインクリメントを「1ずつ増加」ではなく、「現在の素数(firstNum)の値ずつ増加」させることで、現在の素数(firstNum)の倍数だけを篩い落としています。
PrimeNumberFinder.java
static void printPrimeNumbers2(int maxNumber) {
// ステップ1:「2から上限値までの整数」を探索リストに入れる。
boolean[] targetNumbers = new boolean[maxNumber + 1];
Arrays.fill(targetNumbers, true);
targetNumbers[0] = false;
targetNumbers[1] = false;
// 素数リスト
List<Integer> primeNumbers = new ArrayList<Integer>();
int sqrt = (int) Math.sqrt(maxNumber);
// ステップ3:探索リストの先頭の値が、引数の平方根に達するまでふるい落とし操作を続ける。
for(int i=2; i<=sqrt; i++) {
// ステップ2:探索リストの先頭の数を素数とし、その倍数を探索リストから篩い落とす。
// ※この時、既に篩い落とされた数(false)は除外する。
int firstNum = i;
if (targetNumbers[i]) {
for (int j=i*firstNum; j<targetNumbers.length; j+=firstNum) {
targetNumbers[j] = false;
}
}
}
// ステップ4:探索リストに残った値を素数リストに移して処理終了。
for (int i=2; i<targetNumbers.length; i++) {
if (targetNumbers[i]) {
primeNumbers.add(i);
}
}
// 素数の表示
System.out.println(primeNumbers.stream().map(pNum -> pNum.toString()).collect(Collectors.joining("\t")));
}
どれだけ高速化したか?
- 前回のコードと比べて、10倍以上高速化していました。
- ギレン総帥じゃなくても「圧倒的じゃないか、我が軍は。」と言いたくなるほどの差です。
上限値が$10^2$ | 上限値が$10^3$ | 上限値が$10^4$ | 上限値が$10^5$ | |
---|---|---|---|---|
前回のコード | 54ms | 55ms | 61ms | 102ms |
今回のコード | 0ms | 1ms | 1ms | 9ms |
まとめ
- 今回のコードを通じて、「計算量」を考慮した開発が重要だと再認識させられました。
- 今回のコードでも、まだまだ改善できるポイントはあると思いますが...
- @swordone さん、色々とヒントを頂き有難うございました。