質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

新規登録して質問してみよう
ただいま回答率
85.50%
Java

Javaは、1995年にサン・マイクロシステムズが開発したプログラミング言語です。表記法はC言語に似ていますが、既存のプログラミング言語の短所を踏まえていちから設計されており、最初からオブジェクト指向性を備えてデザインされています。セキュリティ面が強力であることや、ネットワーク環境での利用に向いていることが特徴です。Javaで作られたソフトウェアは基本的にいかなるプラットフォームでも作動します。

Q&A

解決済

5回答

4572閲覧

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

opyon

総合スコア1009

Java

Javaは、1995年にサン・マイクロシステムズが開発したプログラミング言語です。表記法はC言語に似ていますが、既存のプログラミング言語の短所を踏まえていちから設計されており、最初からオブジェクト指向性を備えてデザインされています。セキュリティ面が強力であることや、ネットワーク環境での利用に向いていることが特徴です。Javaで作られたソフトウェアは基本的にいかなるプラットフォームでも作動します。

0グッド

1クリップ

投稿2018/08/11 08:01

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

参考にした例題元 リンク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(); }

ソースコード

java

1 /** 2 * 問題 https://projecteuler.net/problem=7 3 * 最初の6つの素数:2,3,5,7,11,13を列挙すると、6番目の素数は13であることが分かります。 4 * 10001番目の素数は何ですか? 5 * 6 * @param num 自然数num番目の素数を求める 7 */ 8 static void func(int num) { 9 10 List<Integer> list = new ArrayList<Integer>(); 11 list.add(2);//最初の素数2を初期値として格納しておく 12 int i = 1;//最初のループでi=1+2=3となり3から素数判定する 13 14 while (list.size() < num) { 15 i+=2;//偶数をスキップ 16 for (int j = 0; j < list.size(); j++) { 17 if (i % list.get(j) == 0) { 18 break; 19 } else if (!list.contains(i) && j == list.size()-1) { 20 list.add(i);//リストに発見した素数を格納 21 } 22 } 23 } 24 System.out.println(list.size() + ":" + list.get(list.size() - 1)); 25 } 26

出力結果例
6:13
0ms


試したこと

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

わからないこと

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

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

気になる質問をクリップする

クリップした質問は、後からいつでもMYページで確認できます。

またクリップした質問に回答があった際、通知やメールを受け取ることができます。

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

guest

回答5

0

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

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

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

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

Java

1 static boolean isPrime(final int x) { 2 // 平方根まで判定すれば、良いです。 3 final double sqrtNum = Math.sqrt(x); 4 for (int i = 3; i <= sqrtNum; i += 2) { 5 if (x % i == 0) { 6 return false; 7 } 8 } 9 return true; 10 } 11 12 static void func(final int num) { 13 HashSet<Integer> primes = new LinkedHashSet<>(); 14 primes.add(2);// 最初の素数2を初期値として格納しておく 15 int i = 1;// 最初のループでi=1+2=3となり3から素数判定する 16 int last_prime = 0; 17 while (primes.size() < num) { 18 i += 2;// 偶数をスキップ 19 if (isPrime(i)) { 20 primes.add(i); 21 last_prime = i; 22 } 23 } 24 // sizeを使わなくても、引数のnumと最後の素数を変数に退避しておけばよいです。 25 System.out.println(num + ":" + last_prime); 26 }

10001:104743
22ms

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


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

投稿2018/08/11 10:24

編集2018/08/11 11:53
umyu

総合スコア5846

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

umyu

2018/08/11 11:53

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

2018/08/11 12:18

ありがとうございますとても参考になります jvisualvmを早速使ってみたところ main()やfunc()のメソッド単位で計測出来るようでしたが、 今回問題になっていたListクラスのどのメソッドがボトルネックになっているかまでは視覚化は出来ないようです。(もしかしたらやり方があるのかもしれませが) 一般的なアプリケーションでは複数のメソッドを使うのは当然でしょうから、 そういった場合には役に立つのだろうと想像できます。 配列やArrayListやHash?などの使い分けは自分にはまだ難しいです。 コードを途中まで書いてこれじゃダメだなと変えたりしてるレベルです。 用途に合わせて選べるようになりたいものです。
opyon

2018/08/11 12:46

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

2018/08/11 13:13 編集

@opyonさんへ データ構造とアルゴリズム コレクション編 (C++, Java, C#) https://qiita.com/asksaito/items/98501845e07c0203b2b7 私の回答のツッコミポイントは素数リストから全数探索する必要があるので、LinkedHashSetを使う意味がほぼないという点でしょうか。n番目の素数を調べたいので、メモリ上に保持する必要はなく、isPrimeの結果がtrueならカウントをインクリメントするだけでよいかと。
opyon

2018/08/11 13:33

そうですよね写経しててリストの中の素数を使っていないことに気づいたので改造してるところです。 今回の例題の解を求めるだけならリストは無くても良いと思いました。 リストはリストで使うケースが多いと思うのでそれはそれで勉強になりました。 ただ、LinkedHashSetに格納した値を取得する方法が分からずに検索してましたが、 どうやら最後の値を取り出したりすることは出来ない仕様のようでした。 これはこれでまたどこかで使い所があるのだろうと妄想したりしています。
opyon

2018/08/11 13:48

ありがとうございます
guest

0

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

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

java

1public class Prime { 2 3 public static void main(String[] args) { 4 5 Scanner sc = new Scanner(System.in); 6 int n = Integer.parseInt(sc.nextLine()); 7 8 int count = 0; 9 int answer = 1; 10 11 while(count < n){ 12 if(is_prime(++answer)){ 13 count++; 14 } 15 } 16 System.out.println(n + "番目の素数は" + answer); 17 } 18 19 public static boolean is_prime(int n) 20 { 21 for(int i = 2; i <= Math.sqrt(n); i++){ 22 if(n % i == 0){ 23 return false; 24 } 25 } 26 return true; 27 } 28}

<実行結果>

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

投稿2018/08/11 13:40

退会済みユーザー

退会済みユーザー

総合スコア0

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

opyon

2018/08/11 13:59

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

0

ベストアンサー

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

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

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

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

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

java

1 public int indexOf(Object o) { 2 if (o == null) { 3 for (int i = 0; i < size; i++) 4 if (elementData[i]==null) 5 return i; 6 } else { 7 for (int i = 0; i < size; i++) 8 if (o.equals(elementData[i])) 9 return i; 10 } 11 return -1; 12 }

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

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

java

1 public int size() { 2 return size; 3 } 4 public E get(int index) { 5 rangeCheck(index); 6 7 return elementData(index); 8 }

#####最後に

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

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

投稿2018/08/11 08:41

編集2018/08/11 08:46
BluOxy

総合スコア2663

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

opyon

2018/08/11 08:48

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

2018/08/11 08:51

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

0

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

java

1 public static void main(String[] args) { 2 long start = System.currentTimeMillis(); 3 4 func2(10001); 5 6 long end = System.currentTimeMillis(); 7 System.out.println((end - start) + "ms"); 8 } 9

java

1 //umyuさんコード写経 2 static boolean isPrime(int num) { 3 4 final double sqrtNum = Math.sqrt(num); 5 6 for (int i = 3; i <= sqrtNum; i += 2) { 7 if (num % i == 0) { 8 return false; 9 } 10 } 11 return true; 12 } 13

java

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

出力結果
10001:104743
7ms

投稿2018/08/11 13:57

opyon

総合スコア1009

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

opyon

2018/08/11 14:01

100001:1299721 193ms
guest

0

修正前

java

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

修正後

java

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

投稿2018/08/11 08:54

opyon

総合スコア1009

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

opyon

2018/08/11 08:56

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

あなたの回答

tips

太字

斜体

打ち消し線

見出し

引用テキストの挿入

コードの挿入

リンクの挿入

リストの挿入

番号リストの挿入

表の挿入

水平線の挿入

プレビュー

15分調べてもわからないことは
teratailで質問しよう!

ただいまの回答率
85.50%

質問をまとめることで
思考を整理して素早く解決

テンプレート機能で
簡単に質問をまとめる

質問する

関連した質問