0

1から100万までの数字から素数を取り出すプログラムを作成したのですが、処理する時間を短縮するため搭載されているプロセッサを可能な限り使いたいと考えております。

int core = Runtime.getRuntime().availableProcessors(); を使えば実現できそうなのですが、どう組み込んだらいいのかがわかりません。参考になるプログラムやサイトなどを教えていただけないでしょうか。

public class primenumber{
    public static void main(String[] args) {

        int u=0;

        long startTime = 0;
        long estimatedTime = 0;

        System.out.println("Prime number counting started");
        startTime = System.nanoTime(); 

        r:
        for(int i=2;i<=100000;i++){
            for(int j=2;j<i;j++){
                if(i%j==0)continue r;
            }
            u++;
            System.out.print(i+" ");
        }

        estimatedTime = System.nanoTime() - startTime;
        System.out.println("Started time:"+startTime);
        System.out.println("Complete. Time:"+estimatedTime);
        System.out.println("Number of prime number:"+u);

    }
}
3
  • 1
    質問の主旨とは関係ないのですが、二重ループの for(int j=2;j<i;j++)for(int j=2;j<((int)(i/2)+1);j++) に変更すると計算量が半減するので処理時間も1/2程度になります。
    – user39889
    Commented 2020年10月11日 13:36
  • 1
    sqrt(i) にすればもっと減ります
    – 774RR
    Commented 2020年10月11日 22:00
  • 「100万まで」程度の固定値ならエラトステネスの篩なんかの方がコア数が大したことないときには高速になりますね。並列化がしにくいんで使えるコア数が多い環境だと微妙ですが。
    – OOPer
    Commented 2020年10月12日 2:26

1 件の回答 1

5

素数を判定するメソッドをつくって、

static boolean isPrime(int number) {
    if(number <= 2)
        return number == 2;
    else
        return (number % 2) != 0
                && IntStream.rangeClosed(3, (int) Math.sqrt(number))
                        .filter(n -> n % 2 != 0)
                        .noneMatch(n -> (number % n == 0));
}

Stream APIで呼び出せば、自動的に並列化されて処理時間を短縮できるはずです。

IntStream.range(1, 100000).parallel().filter(primenumber::isPrime)
    .forEach(i -> System.out.print(i + " "));

順序を保証したい場合は、.parallel()を取り除いてください。

私の手元で計測した結果では、処理時間が約3秒から約0.4秒に短縮されました。

8
  • FYI: Streams終端操作にforEachではなくforEachOrderedメソッドを使うと、.parallel()で並列処理を行いつつも出力順序の保証を行えます。
    – yohjp
    Commented 2020年10月13日 6:23
  • 1
    @yohjp コメントありがとうございます。今、手元で実験したみたのですが、.parallel()付きの.forEach().forEachOrdered()に変更するとさらに短時間に処理が終わりました。.forEachOrdered()で順序を維持する分、処理は遅くなり、結果的には.parallel()を付けない.forEach()の処理時間に近づくと予想していましたが、実際には.parallel().forEachOrdered()が最速でした。これについて考えられる理由はありますかね? Commented 2020年10月13日 8:50
  • 興味深い速度データですね。ちなみにforEachOrderedの順序保証は並列動作性能にさほど悪影響を与えずに実装可能なものです。今回forEachの方が速くなったのは、isPrimeの処理負荷が入力値に対して不均衡なこと、区間分割の粒度が変わったことによる副作用なのではと推測します。
    – yohjp
    Commented 2020年10月13日 9:08
  • 1
    文字だけの説明は厳しいですが起こりえるシナリオとして:forEachは入力区間を均等分割/forEachOrderedは小さい区間から次第に処理粒度を増やしていく戦略と仮定すると、isPrimeは入力値が大きくなるほど計算時間が増大するため、区間均等分割では後半区間を受け持つスレッドは不利になり、結果的にforEachOrderedの方が計算資源を効率的に使うことができたのかもしれません(すべて妄想です)これは並列処理におけるタスク粒度分割とスケジューリング問題ですね。
    – yohjp
    Commented 2020年10月13日 9:13
  • 1
    JMHで真面目に計測してみたら、.parallel()付きの.forEach()が最速でした。 Commented 2020年12月2日 13:07

この質問に回答するには、ログインする必要があります。

求めていた回答ではありませんか? のタグが付いた他の質問を参照する。