エラトステネスの篩をJavaの標準ライブラリを使って実装してみる

はじめに

普段はパッケージソフトの開発をしていますが、最近競プロをはじめました。
普段のコードの書き方と全然違っていたので戸惑いが大きく（こんなコード書いたらぶっ殺されるなと思いながら問題解いてます）、これを普段やるように実装してみたらどうなるだろうかと思っていました。

そんなとき、@nkojima さんの【Java】エラトステネスの篩で素数を求めると【Java】エラトステネスの篩で素数を求める（その2）を読んで、ちょうどよい題材になりそうだと思い、標準ライブラリを使って可読性を上げてみました。

この際なので、コレクションの使い分けも合わせてやってみます。

コード

【Java】エラトステネスの篩で素数を求める（その2）を参考に、探索リストをArrayList、HashSet、ArrayList<Boolean>に変えて実装してみました。

ListImplement.java

package practise.algorithm.eratosthenes.qiita;

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class ListImplement {
    private static final int MIN_PRIME_NUMBER = 2;

    public static void main(String[] args) {
        new ListImplement().execute();
    }

    private void execute() {
        Scanner sc = new Scanner(System.in);
        int maxNumber = sc.nextInt();

        List<Integer> primeNumbers = enumeratePrimeNumbers(maxNumber);

        System.out.println(primeNumbers.toString());
    }

    private List<Integer> enumeratePrimeNumbers(int maxNumber) {
        List<Integer> targets = createSearchTargets(maxNumber);

        sieve(targets, maxNumber);

        return targets;
    }

    //2～maxNumberまでの探索リストを作る
    private List<Integer> createSearchTargets(int maxNumber) {
        List<Integer> targets = new ArrayList<>(maxNumber);
        for(int i = MIN_PRIME_NUMBER; i <= maxNumber; i++) {
            targets.add(i);
        }
        return targets;
    }

    //探索リストの先頭値の倍数を探索リストからふるい落とす
    //上記を探索リストの先頭値がmaxNumberの平方根に達するまで行う。
    private void sieve(List<Integer> targets, int maxNumber) {
        int sqrt = (int)  Math.sqrt(maxNumber);
        for(int i = MIN_PRIME_NUMBER; i <= sqrt; i++) {
            int firstNum = i;
            if(targets.contains(firstNum)) {//★★★篩の目かどうかを判定する部分★★★
                //先頭値の2乗まではすでに篩落とされているので
                for(int j = firstNum * firstNum; j <= maxNumber; j += firstNum) {
                    targets.remove(Integer.valueOf(j));//★★★篩をかける部分★★★
                }
            }
        }
    }

}

SetImplement.java

package practise.algorithm.eratosthenes.qiita;

import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;

public class SetImplement {
    private static final int MIN_PRIME_NUMBER = 2;

    public static void main(String[] args) {
        new SetImplement().execute();
    }

    private void execute() {
        Scanner sc = new Scanner(System.in);
        int maxNumber = sc.nextInt();

        Set<Integer> primeNumbers = enumeratePrimeNumbers(maxNumber);

        System.out.println(primeNumbers.toString());
    }

    private Set<Integer> enumeratePrimeNumbers(int maxNumber) {
        Set<Integer> targets = createSearchTargets(maxNumber);

        sieve(targets, maxNumber);

        return targets;
    }

    //2～maxNumberまでの数値リストを作る
    private Set<Integer> createSearchTargets(int maxNumber) {
        Set<Integer> targets = new HashSet<>(maxNumber);
        for(int i = MIN_PRIME_NUMBER; i <= maxNumber; i++) {
            targets.add(i);
        }
        return targets;
    }

    //探索リストの先頭値の倍数を探索リストからふるい落とす
    //上記を探索リストの先頭値がmaxNumberの平方根に達するまで行う。
    private void sieve(Set<Integer> targets, int maxNumber) {
        int sqrt = (int)  Math.sqrt(maxNumber);
        for(int i = MIN_PRIME_NUMBER; i <= sqrt; i++) {
            int firstNum = i;
            if(targets.contains(firstNum)) {//★★★篩の目かどうかを判定する部分★★★
                //先頭値の2乗まではすでに篩落とされているので
                for(int j = firstNum * firstNum; j <= maxNumber; j += firstNum) {
                    targets.remove(j);//★★★篩をかける部分★★★
                }
            }
        }
    }
}

BooleanArrayListImplement.java

package practise.algorithm.eratosthenes.qiita;

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class BooleanArrayListImplement {
    private static final int MIN_PRIME_NUMBER = 2;

    public static void main(String[] args) {
        new BooleanArrayListImplement().execute();
    }

    private void execute() {
        Scanner sc = new Scanner(System.in);
        int maxNumber = sc.nextInt();

        List<Integer> primeNumbers = enumeratePrimeNumbers(maxNumber);

        System.out.println(primeNumbers.toString());
    }

    private List<Integer> enumeratePrimeNumbers(int maxNumber) {
        List<Boolean> targets = createSearchTargets(maxNumber);

        List<Integer> primeNumbers = extracePrimeNumbers(targets);

        return primeNumbers;
    }

    //0～maxNumberまでのBooleanの探索リストを作る
    //indexを探索対象の数とするため0からスタート
    //素数かどうかをbooleanで判定
    private List<Boolean> createSearchTargets(int maxNumber) {
        List<Boolean> targets = new ArrayList<>(maxNumber + 1);
        targets.add(false);//0は素数ではないので
        targets.add(false);//1は素数ではないので
        for(int i = MIN_PRIME_NUMBER; i <= maxNumber; i++) {
            targets.add(true);
        }
        return targets;
    }

    //探索リストの先頭値の倍数を探索リストからふるい落とす
    //上記を探索リストの先頭値がmaxNumberの平方根に達するまで行う。
    private List<Integer> extracePrimeNumbers(List<Boolean> targets) {
        int maxNumber = targets.size() - 1;

        sieve(targets, maxNumber);

        List<Integer> primeNumbers = convertToNumList(targets);

        return primeNumbers;
    }

    private void sieve(List<Boolean> targets, int maxNumber) {
        int sqrt = (int)  Math.sqrt(maxNumber);
        for(int i = MIN_PRIME_NUMBER; i <= sqrt; i++) {
            int firstNum = i;
            if(targets.get(i)) {//★★★篩の目かどうかを判定する部分★★★
                //先頭値の2乗まではすでに篩落とされているので
                for(int j = firstNum * firstNum; j <= maxNumber; j += firstNum) {
                    targets.set(j, false);//★★★篩をかける部分★★★
                }
            }
        }
    }

    private List<Integer> convertToNumList(List<Boolean> targets) {
        List<Integer> numbers = new ArrayList<>();
        for(int i = 0; i < targets.size(); i++) {
            if(targets.get(i)) {
                numbers.add(i);
            }
        }
        return numbers;
    }
}

速度まとめ

実行時間(5回実行した平均)のまとめです。
ArrayList<Boolean>が一番速く、ArrayListは論外ですね。
配列を使った実装にはどれも到底叶いませんが。。。

実装	上限値が$10^5$	上限値が$10^6$	上限値が$10^7$
ArrayListで実装(ListImplement.java)	3,221 ms	返って来なかった	-
HashSetで実装(SetImplement.java)	24 ms	118 ms	1,120 ms
ArrayListで実装(BooleanArrayListImplement.java)	16 ms	50 ms	1,247 ms
参考1	31 ms	276 ms	7,845 ms
参考2	4 ms	21 ms	66 ms

速度の違いが発生した原因

コードに★マークを書きましたが、以下の２箇所が大きな要因だろうなと思っています。

• 篩の目かどうかを判定する部分
• 篩をかける部分

それぞれの箇所で要素へのアクセスをしていますが、このときのアクセスの仕方は以下の通りです。

• ArrayListの実装：配列の前から順に探索
  →線形探索
• HashSetの実装：ハッシュテーブルで対象のオブジェクトにアクセス
  →ハッシュテーブルを介すが、結局ランダムアクセス
• ArrayList<Boolean>の実装：インデックスで配列にアクセス
  →ランダムアクセス

結局、計算量オーダーは、
ArrayListは$O(n^2loglogn)$、HashSetとArrayList<Boolean>は$O(nloglogn)$（実行結果を見ると、今回の実装ではこうはなっていない気が。。。）じゃないかなと思います。（loglognの部分はググりました。こんな記事もあるんですね。）

HashSetよりもArrayList<Boolean>、ArrayList<Boolean>よりも配列の方が速いのは、要素へのアクセス時にハッシュ値の計算がなかったり、配列の拡張の操作がなかったり、その他諸々の余分な操作が無いからだろうなと。

まとめ

実際にやってみて、以下のように感じました。

• 実務で使う場合は、多少速度は遅くなるものの可読性を重視するのでSetの実装にする
• スピード重視のときは、ガッツリコメント書いて配列の実装にする
• ArrayList<Boolean>使うくらいなら配列にする（どのみちコメントは必要）

競プロやると今まで見たことのないアルゴリズムがいっぱい出てきて面白うですね。
いい感じに実務活かしたいなと思うこの頃です。

最後に

• コレクション系のデータ構造を選択するときは、重複を排除する場合はSet、重複がある場合はListくらいの感覚で実装していました。 たまたま問題になるほど速度には影響出ていないかっただけで、今気づいてよかったと思いました。
• @nkojima さんが素敵な投稿をしてくださったおかげで私もしっかりと勉強できました。感謝です。
• 勉強不足なところが多々あると思いますが、おかしいところがあれば優しくマサカリを投げていただければと思います。