ゆっちのBlog

Java8 時代の素数の求め方

Java

「創る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<Integer> 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);
//        }

    }

}

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<Integer> 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<List<Integer>>{
    
    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<Future<List<Integer>>> 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<Integer> totalPrimes = new ArrayList<>();
        
        for (Future<List<Integer>> future : futures) {
            try {
                List<Integer> 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<Integer> call() throws Exception {
        List<Integer> 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;
    }
    
}

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<List<Integer>>{

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<Future<List<Integer>>> 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<Integer> totalPrimes = new ArrayList<>();

for (Future<List<Integer>> future : futures) {

try {

List<Integer> 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<Integer> call() throws Exception {

List<Integer> 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 を貼っておきます。

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

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<Integer> 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);
    }

}

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<Integer> 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 が使われているのが確認できますね。

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

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

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

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

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

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

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

Hatena タグ: Java

TAGS: Java | 2014年4月16日5:39 PM

« お年玉キャンペーン当たったよ(^_^) Windows 8.1 システム修復ディスク作成方法 (裏技) »

Comment

似非プログラマsays:
2015年4月2日 12:00 PM

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

返信
- ゆっちsays:
  2015年4月2日 9:58 PM
  
  あっちゃ～(^_^;
  やってしまった。
  初めは検出した素数を表示させていたので・・・
  検出した素数を数え上げるだけだと確かに無駄なことやってます。
  まだまだ修行がたりませんね。
  ありがとうございました。(^_^)
  
  返信
  - 似非プログラマsays:
    2015年4月3日 8:35 AM
    
    いえいえ ! コメントいただいて気づいたんですけど、並列化されたままの状態で forEach すると順序が保証されないですね…というわけで表示の際は直列化するように修正しました。
    
    Stream API を用いた並列化された素数検出プログラム
    
    返信
    - 似非プログラマsays:
      2015年4月3日 8:43 AM
      
      済みません、コメントの編集が出来ないので…確かに Stream のままで count やっちゃうと一覧表示出来なくなっちゃいますね…失礼しました m(_ _)m
      
      返信

月	火	水	木	金	土	日
« 1月
				1	2	3
4	5	6	7	8	9	10
11	12	13	14	15	16	17
18	19	20	21	22	23	24
25	26	27	28	29	30

Java8 時代の素数の求め方

Comment

Leave a Reply (or Cancel)

Trackback URL

Recent Comments

Java

NetBeans

カテゴリー

アーカイブ

RSS FEED

ねこび～ん

メタ情報

ゆっちのカレンダー

ゆっちのBlog

Java8 時代の素数の求め方

Comment

Leave a Reply (or Cancel)

Trackback URL

Popular post ranking

Recent Comments

Java

NetBeans

カテゴリー

アーカイブ

RSS FEED

ねこび～ん

メタ情報

ゆっちのカレンダー