2014年4月29日火曜日

100万個目の素数を求めるJavaソース


Java言語では素数を定義するライブラリーもあるので、そのため以下のソースコードのように簡単な素数を求めるプログラムです。
同様に100万個目の素数を求めるJavaソースを次に示します。
public class Prime {                                
                                                    
  private boolean isprime( int i )                  
  {                                                 
    int     j;                                      
                                                    
    for( j=2; j*j <= i ; ++j )                      
      if( i%j == 0 )                                
        return  false;      /* not prime */         
    return  true;                      /* prime */  
  }                                                 
                                                    
  public Prime()                                    
  {                                                 
    int     c = 0;                                  
    int     p;                                      
    int     maxprime = 0;                           
                                                    
    for( p=2; c<1000000; ++p )                      
      if( isprime( p ) ) {                          
        maxprime = p;                               
        ++c;                                        
        /*      printf( "%d\t%d\n", c, p );     */  
      }                                             
                                                    
    System.out.println( c + "\t" + maxprime );      
  }                                                 
                                                    
  public static void main(String[] args) {          
    new Prime();                                    
  }                                                 
}                                                   

timeコマンドで計測した実行時間は約6分3秒です。gccでのコンパイル時に最適化オプションを変更するなど チューニングを施せばCがJavaより速くなる可能性はあります。

$ java -version
java version "1.3.1"
Java(TM) 2 Runtime Environment, Standard Edition (build Blackdown-1.3.1-FCS)
Java HotSpot(TM) Client VM (build Blackdown-1.3.1-FCS, mixed mode)
$ javac -O Prime.java
$ time java Prime
1000000 15485863

real    6m2.813s
user    5m48.870s
sys     0m0.400s


しかし、プログラムを現代的に並行処理させていたので、Executor を使って平行処理プログラムを組んでみました。もちろん、先のプログラムより処理時間が短縮されているだろうと予想される。
結果は。。。。。。
973815個の素数を検出しました。
0時間0分14秒2449762050000004
おおっ! 凄いぞ! さすが Java5 の主役の Executor だ!
***************************
以下のソースコードを参照してください。

package  prime.test.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;
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;
    }   
}

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


package  prime.test.primenumber8executor;
import java.util.List;
import java.util.stream.Collectors;
import java.util.stream.IntStream;
public class PrimeNumber8ParallelStream {
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 使って並行処理してプログラムより5倍近く高速に処理されてます!
この Java8 時代のプログラムですが 20 行目の parallel() メソッドをコメントアウトして
シーケンシャル処理させると処理時間は次のようになりました。
1973815個の素数を検出しました。
0時間0分49秒009503713000000857
一番最初に紹介した古いプログラムよりかは高速ですね。でも。遅いよね。