n番目の素数を求める処理が重い

Question

正解結果は出せるが処理が重い

参考にした例題元　リンクURL
5000番目で約1分弱、10001番目だと約4分半も掛かってしまいます。

	public static void main(String[] args) {

		long start = System.currentTimeMillis();

		func(6);

//		func(6); 	//0ms		//13
//		func(10); 	//1ms		//29
//		func(100); 	//5ms		//541
//		func(1000); 	//360ms		//7919
		
//		func(5000);	//54,440ms	//48611       'i++;
//		func(5000);	//53,471ms	//48611       'i+=2;
		
//		func(10001);	//262,829ms	//104743	'i++;
//		func(10001);	//266,841ms	//104743	'i+=2;
		
		long end = System.currentTimeMillis();
		System.out.println((end - start) + "ms");
		System.out.println();

	}

ソースコード

	/**
	 * 問題　https://projecteuler.net/problem=7
	 * 最初の6つの素数：2,3,5,7,11,13を列挙すると、6番目の素数は13であることが分かります。
	 * 10001番目の素数は何ですか？
	 * 
	 * @param num 自然数num番目の素数を求める
	 */
	static void func(int num) {

		List<Integer> list = new ArrayList<Integer>();
		list.add(2);//最初の素数2を初期値として格納しておく
		int i = 1;//最初のループでi=1+2=3となり3から素数判定する

		while (list.size() < num) {
			i+=2;//偶数をスキップ
			for (int j = 0; j < list.size(); j++) {
				if (i % list.get(j) == 0) {
					break;
				} else if (!list.contains(i) && j == list.size()-1) {
					list.add(i);//リストに発見した素数を格納
				}
			}
		}
		System.out.println(list.size() + ":" + list.get(list.size() - 1));
	}

出力結果例
6:13
0ms

---

試したこと

Whileループカウンターのi+=2;にすることで偶数はスキップするようにしました。
速度変化は誤差程度の範囲で特に改善されませんでした。

わからないこと

• 例題なので答えがすぐに表示される解法があるのではないか
• ボトルネックになっているのはどこなのか
• そもそもこれ以上改善の余地があるのか

素数 10001などで検索しましたが改善出来そうなものは見つけられませんでした。
初歩的なことしか実装出来ていないと思いますがアドバイスやヒントなど頂けましたら幸いです。

Answer 1

ArrayListは要素数が動的に変更できる点以外は配列と同じなので存在チェックは配列と同じで内部の要素を全部たどります。

Listインタフェースのサイズ変更可能な配列の実装です。

存在チェックを行いたい時はソートして2分探索で検索するか
Collections#binarySearch

素数は重複値が存在しないので、LinkedHashSetやBitSetを使ってくださいな。

	static boolean isPrime(final int x) {
		// 平方根まで判定すれば、良いです。
		final double sqrtNum = Math.sqrt(x);
		for (int i = 3; i <= sqrtNum; i += 2) {
			if (x % i == 0) {
				return false;
			}
		}
		return true;
	}

	static void func(final int num) {
		HashSet<Integer> primes = new LinkedHashSet<>();
		primes.add(2);// 最初の素数2を初期値として格納しておく
		int i = 1;// 最初のループでi=1+2=3となり3から素数判定する
		int last_prime = 0;
		while (primes.size() < num) {
			i += 2;// 偶数をスキップ
			if (isPrime(i)) {
				primes.add(i);
				last_prime = i;
			}
		}
		// sizeを使わなくても、引数のnumと最後の素数を変数に退避しておけばよいです。
		System.out.println(num + ":" + last_prime);
	}

10001:104743
22ms

■参考情報
エラトステネスの篩で調べる 素数判定の上限と平方根の関係性

---

プログラムのどこに時間がかかっているのかを調べたい時はプロファイラーを使います。
JDKに付属しているのだとjvisualvmとかでしょうか。

Comments

[umyu]

書いた後にいろいろ突っ込まれるポイントがあることに気づきました（汗）

[opyon]

ありがとうございますとても参考になります

jvisualvmを早速使ってみたところ
main()やfunc()のメソッド単位で計測出来るようでしたが、
今回問題になっていたListクラスのどのメソッドがボトルネックになっているかまでは視覚化は出来ないようです。（もしかしたらやり方があるのかもしれませが）

一般的なアプリケーションでは複数のメソッドを使うのは当然でしょうから、
そういった場合には役に立つのだろうと想像できます。

配列やArrayListやHash?などの使い分けは自分にはまだ難しいです。
コードを途中まで書いてこれじゃダメだなと変えたりしてるレベルです。
用途に合わせて選べるようになりたいものです。

[opyon]

コードも写経しながら確認してみます

[umyu]

@opyonさんへ
データ構造とアルゴリズム コレクション編 (C++, Java, C#)
https://qiita.com/asksaito/items/98501845e07c0203b2b7

私の回答のツッコミポイントは素数リストから全数探索する必要があるので、LinkedHashSetを使う意味がほぼないという点でしょうか。n番目の素数を調べたいので、メモリ上に保持する必要はなく、isPrimeの結果がtrueならカウントをインクリメントするだけでよいかと。

[opyon]

そうですよね写経しててリストの中の素数を使っていないことに気づいたので改造してるところです。
今回の例題の解を求めるだけならリストは無くても良いと思いました。
リストはリストで使うケースが多いと思うのでそれはそれで勉強になりました。

ただ、LinkedHashSetに格納した値を取得する方法が分からずに検索してましたが、
どうやら最後の値を取り出したりすることは出来ない仕様のようでした。
これはこれでまたどこかで使い所があるのだろうと妄想したりしています。

[umyu]

@opyonさんへ
LinkedHashSetで取り出したい時は配列に変換するかループで最後までまわす必要があるかと。
Java LinkedHashMap get first or last entry
https://stackoverflow.com/questions/1936462/java-linkedhashmap-get-first-or-last-entry

[opyon]

ありがとうございます

Answer 2

既に解決済みですが、リストを使わずに求める方法で実装してみました。

処理速度は速い方だと思います。

public class Prime {

    public static void main(String[] args)  {
        
        Scanner sc = new Scanner(System.in);
        int n = Integer.parseInt(sc.nextLine());
        
        int count = 0;
        int answer = 1;
        
        while(count < n){
              if(is_prime(++answer)){
                count++;
            }
        }
        System.out.println(n + "番目の素数は" + answer);
    }    
        
    public static boolean is_prime(int n)
    {
        for(int i = 2; i <= Math.sqrt(n); i++){
            if(n % i == 0){
                return false;
            }
        }
        return true;
    }
}

<実行結果>

10001番目の素数は104743 (約1秒)
100001番目の素数は1299721 (約8秒)

Comments

[opyon]

ありがとうございます
とてもシンプルですね。
解を得る要件を満たすならリストいらないんですよね最後に気づきました。

Answer 3

たかが5000回のループで時間がかかってしまうのは確かに不思議ですね。

ステップ数的に無駄な処理は、
コードにて記載されているように見えませんでした。

なので、Listクラスのメソッドが、時間がかかっていると見ます。

ArrayListクラスの中身をこのサイトから確認してみました。

#####思った点
containsメソッドは中でindexofメソッドを返しているのですが、
indexofメソッドの中身は以下のようになっています。

    public int indexOf(Object o) {
        if (o == null) {
            for (int i = 0; i < size; i++)
                if (elementData[i]==null)
                    return i;
        } else {
            for (int i = 0; i < size; i++)
                if (o.equals(elementData[i]))
                    return i;
        }
        return -1;
    }

opyon様のコード上にあるループは、int num = 10000の時、
計算が正しければfuncメソッドの中で
1~5000までの総和5000x5001/2=12502500の
回数分リストの要素にアクセスしていることになります。

一方、他のメソッドは以下のように、ステップ数的には負荷の軽いような実装に見えます。

    public int size() {
        return size;
    }
    public E get(int index) {
        rangeCheck(index);

        return elementData(index);
    }

#####最後に

それでもたかが1200万回のアクセスで遅くなる…というのも変な話ですね。
（世の中のシステムは不便になってしまいます）

とりあえずは
試しにcontainsから変えてみて、動きを確認してみると良いかもしれません

Comments

[opyon]

ありがとうございます
着目する視点がプロっぽいですね！
containsを代替え出来るか試してみます

[opyon]

確認したところ　!list.contains(i)　この条件が不要でした
この条件をはずすだけで爆速です！
ありがとうございました

Answer 4

これまでの頂いた回答を参考に改修した結果、爆速になりました！

	public static void main(String[] args) {
		long start = System.currentTimeMillis();

		func2(10001);

		long end = System.currentTimeMillis();
		System.out.println((end - start) + "ms");
	}

	//umyuさんコード写経
	static boolean isPrime(int num) {

		final double sqrtNum = Math.sqrt(num);

		for (int i = 3; i <= sqrtNum; i += 2) {
			if (num % i == 0) {
				return false;
			}
		}
		return true;
	}

	static void func2(int num) {

		int i = 1;					//最初のループでi=1+2=3となり3から素数判定する
		int primeMax = 2;			//最初の素数2を初期値として格納しておく
		int counter =1;				//最初の素数2があるので初期値は1
		
		while (counter < num) {
			i += 2;					//偶数をスキップ
			if (isPrime(i)) {
				primeMax = i;		//発見した素数を格納
				counter++;			//発見した素数をカウント
			}
		}
		System.out.println(num + ":" + primeMax);
	}

出力結果
10001:104743
7ms

Comments

[opyon]

100001:1299721
193ms

Answer 5

修正前

				} else if (!list.contains(i) && j == list.size()-1) {

修正後

				} else if (j == list.size()-1) {

Comments

[opyon]

func(10001);の結果
10001:104743
214ms