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
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);
}}
それに Java8 に慣れるとこちらの方がソースコードの可読性が良いと思うようになります。 さぁ、Java8 時代の素数を求めるコードの処理速度はどうなんだ！?
1973815個の素数を検出しました。
0時間0分3秒5042672730000004
なんと！ Executor 使って並行処理してプログラムより５倍近く高速に処理されてます！
この Java8 時代のプログラムですが 20 行目の parallel() メソッドをコメントアウトして
シーケンシャル処理させると処理時間は次のようになりました。
1973815個の素数を検出しました。
0時間0分49秒009503713000000857
0時間0分49秒009503713000000857
一番最初に紹介した古いプログラムよりかは高速ですね。でも。遅いよね。
0 件のコメント:
コメントを投稿