Java8 時代の素数の求め方

投稿日時: 投稿者:

「創るJava」 の著者である、きしださんが「Java8時代の文字列連結まとめ」という面白い記事を書いてくれた。

文字列連結だと Java8 での Stream API でコネコネしても感動的な結果は得られず残念な結果となった。

つまり文字列連結は今まで通りのほうが速いよってことのようです。

さて、それではあまりにも Java8 の Stream API が可愛そうなので Stream API 威力を発揮するようなプログラムを組んでみます。

といっても簡単でシンプルなものにします。

みんな大好き素数を表示させるプログラムです。

素数と言えばエラトステネスの篩だと誰もが思うのですが、それは無かったことにしてください。(￣。￣;)

それでは一番シンプルで Java8 じゃないプログラムを組んでみました。

package jp.yucchi.primenumber_old;

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

/**
 *
 * @author Yucchi
 */
public class PrimeNumber_Old {

    private static final int UP_NUMBER = 32_000_000;

    public static void main(String[] args) {

        long startTime = System.nanoTime();

        List primes = new ArrayList<>();

        for (int i = 2; i < UP_NUMBER + 1; i++) {
            if ((i & 0b1) == 0 && i > 0b10) {
                continue;
            }
            int j;
            for (j = (int) Math.sqrt(i); i % j != 0; j--) {
            }
            if (j == 0b1 && i != 0b1) {
                primes.add(i);
            }
        }

        System.out.println(primes.size() + "個の素数を検出しました。");

        long time = System.nanoTime() - startTime;
        System.out.println((int) (time * 1e-9) / 3_600 + "時間"
                + (int) ((time * 1e-9) / 60) % 60 + "分"
                + (int) (time * 1e-9 % 60) + "秒"
                + Double.toString((time * 1e-9 % 60) % 1).substring(2));

//        for (Integer result : primes) {
//            System.out.println(result);
//        }

    }

}

このプログラムは 32,000,000 までの自然数に素数がいくつあるか検出し、その処理時間を計測しています。

ちなみに検出された素数はコメントアウトしてある部分を解除すれば表示されます。

それでは気になる処理時間は次のようにけっこう時間かかってます。(>_<｡)

1973815個の素数を検出しました。
0時間2分53秒40869402600000626

それではこのプログラムを現代的に並行処理させてみます。

これも Java8 じゃないプログラムです。

そう、Executor を使って平行処理プログラムを組んでみました。

package jp.yucchi.primenumber4executor;

import java.lang.management.ManagementFactory;
import java.util.ArrayList;
import java.util.List;
import java.util.concurrent.Callable;
import java.util.concurrent.ExecutionException;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;
import java.util.concurrent.Future;
import java.util.logging.Level;
import java.util.logging.Logger;

/**
 *
 * @author Yucchi
 */
public class PrimeNumber4Executor implements Callable>{
    
    private static final int UP_NUMBER = 32_000_000;
    private final int from;
    private final int to;

    public PrimeNumber4Executor(final int from, final int to) {
        this.from = from;
        this.to = to;
    }

    public static void main(String[] args) {
        
        long startTime = System.nanoTime();
        
        final int procs = ManagementFactory.getOperatingSystemMXBean().getAvailableProcessors();
        ExecutorService executor = Executors.newFixedThreadPool(procs);
        final int range = UP_NUMBER / procs;
        List>> futures = new ArrayList<>();
        for (int i = 0; i < procs; i++) {
            final int from = i * range + 1;
            final int to = (i + 1) * range;
            futures.add(executor.submit(new PrimeNumber4Executor(from, to)));
        }
        
        executor.shutdown();
        
        List totalPrimes = new ArrayList<>();
        
        for (Future> future : futures) {
            try {
                List primes = future.get();
                totalPrimes.addAll(primes);
            } catch (InterruptedException | ExecutionException ex) {
                Logger.getLogger(PrimeNumber4Executor.class.getName()).log(Level.SEVERE, null, ex);
            }
        }

        
        System.out.println(totalPrimes.size() + "個の素数を検出しました。");
        long time = System.nanoTime() - startTime;
        System.out.println((int) (time * 1e-9) / 3_600 + "時間"
                + (int) ((time * 1e-9) / 60) % 60 + "分"
                + (int) (time * 1e-9 % 60) + "秒"
                + Double.toString((time * 1e-9 % 60) % 1).substring(2));
        
//        for (Integer result : totalPrimes){
//            System.out.println(result);
//        }
       
    }
    
    @Override
    public List call() throws Exception {
        List primes = new ArrayList<>();
        for (int i = from; i < to + 1; i++) {
           
            if ((i & 0b1) == 0 && i > 0b10) {
                continue;
            }
            int j;
            for (j = (int) Math.sqrt(i); i % j != 0; j--) {
             
            }
                   
            if (j == 1 && i != 1) {
                primes.add(i);
            }
        }
        return primes;
    }
    
}

実はこのプログラムは随分前に Executor の学習にネットで見つけたサンプルをほぼいただいてます。

こういうのは思いつかなかったなぁ・・・

で、きっと処理時間が短縮されているだろうと予想される結果は次のとおりです。

1973815個の素数を検出しました。
0時間0分14秒2449762050000004

おおっ！　凄いぞ！　さすが Java5 の主役の Executor だ！

ついでだから NetBeans のプロファイラでのスレッドと CPU を貼っておきます。

PrimeNumber4Executor

ex1

 

さて、そろそろ古き時代のコードは見飽きた頃合いになってきましたね。

Java8 時代の素数を求めるプログラムを組んでみました。

package jp.yucchi.primenumber4parallelstream;

import java.util.List;
import java.util.stream.Collectors;
import java.util.stream.IntStream;

/**
 *
 * @author Yucchi
 */
public class PrimeNumber4ParallelStream {

    private static final int UP_NUMBER = 32_000_000;

    public static void main(String[] args) {

        long startTime = System.nanoTime();

        List primeList = IntStream.rangeClosed(1, UP_NUMBER)
                .parallel()
                .filter(n -> ((n & 0b1) != 0 || n == 0b10) && n > 0b1)
                .filter(PrimeNumber4ParallelStream::isPrime)
                .boxed()
                .collect(Collectors.toList());

        System.out.println(primeList.size() + "個の素数を検出しました。");

        long time = System.nanoTime() - startTime;
        System.out.println((int) (time * 1e-9) / 3_600 + "時間"
                + (int) ((time * 1e-9) / 60) % 60 + "分"
                + (int) (time * 1e-9 % 60) + "秒"
                + Double.toString((time * 1e-9 % 60) % 1).substring(2));

//        primeList.forEach(System.out::println);
    }

    private static boolean isPrime(int number) {
        return IntStream.rangeClosed(2, (int) Math.sqrt(number))
                .allMatch(n -> (number % n) != 0);
    }

}

凄くシンプルで Java5 時代の Executor より綺麗です！

それに Java8 に慣れるとこちらの方がソースコードの可読性が良いと思うようになります。

さぁ、Java8 時代の素数を求めるコードの処理速度はどうなんだ！?

1973815個の素数を検出しました。
0時間0分3秒5042672730000004

なんと！ Executor 使って並行処理してプログラムより５倍近く高速に処理されてます！

ParallelStream 使いどころを誤らなければ凄く幸せになれそうな気がする。

このプログラムは parallel() メソッドをちょこっと書くだけでなんと並行処理をしてくれます。

内部でJava7 の主役？ として活躍した Fork／Join Framework が使われています。

こちらもついでにスレッドと CPU のプロファイル画像を貼っておきます。

Fork／Join Framework が使われているのが確認できますね。

PrimeNumber4ParallelStream

PPS1

 

この Java8 時代のプログラムですが 20 行目の parallel() メソッドをコメントアウトして

シーケンシャル処理させると処理時間は次のようになりました。

1973815個の素数を検出しました。
0時間0分49秒009503713000000857

一番最初に紹介した古いプログラムよりかは高速ですね。でも。遅いよね。

ちなみにスレッドモニターでシーケンシャル処理されていることが確認できます。

PrimeNumber4NonParallelStream

 

文字列連結では Java8 時代のプログラムは残念な結果となったけど素数検出プログラムでは本領発揮といったところですね！

最後に、Java8 凄い！(^_^)

Hatena タグ:

「Java8 時代の素数の求め方」への4件のフィードバック

  1. 初めまして。こちらで紹介されていたコードを試してみて、早いんですが少し無駄な処理があるような気がしたので、少し修正したものを私の Gist & はてなブログで紹介させていただきました。

    返信 ↓

コメントを残す

メールアドレスが公開されることはありません。 ※ が付いている欄は必須項目です