论坛 › Java › Java多线程效率-素数计算

方兆国 发表于 2013-07-19 13:31

Java多线程效率-素数计算

JavaNative 单线程实现
Number of primes under 10000000 is664579
Time taken is 21.640470622 s

JavaPure 单线程实现：
Number of primes under 10000000 is665025
Time taken is 29.615632484 s

JavaPure 4线程实现：
Number of primes under 10000000 is665025
Time taken is 12.943822983 s

JavaPure 5线程实现：
Number of primes under 10000000 is665025
Time taken is 11.316296326 s

JavaPure 6线程实现：
Number of primes under 10000000 is665025
Time taken is 11.852669045 s

JavaPure 7线程实现：
Number of primes under 10000000 is665024
Time taken is 11.875677067 s

JavaPure 8线程实现：
Number of primes under 10000000 is665025
Time taken is 11.583545436 s

JavaPure 9线程实现：
Number of primes under 10000000 is665025
Time taken is 11.472949961 s

JavaPure 4Mix线程实现：
Number of primes under 10000000 is664579
Time taken is 10.488330912 s

JavaPure 5Mix线程实现：
Number of primes under 10000000 is664579
Time taken is 10.491616154 s

JavaPure 6Mix线程实现：
Number of primes under 10000000 is664579
Time taken is 10.480008206 s

JavaPure 7Mix线程实现：
Number of primes under 10000000 is664579
Time taken is 10.357619101 s

JavaPure 8Mix线程实现：
Number of primes under 10000000 is664579
Time taken is 10.43754778 s

JavaPure 9Mix线程实现：
Number of primes under 10000000 is664579
Time taken is 10.511800879 s

方兆国 发表于 2013-07-19 13:32

先上主函数package com.fangzhaoguo.primefinder;

public class Main {

        public static void main(String[] args) {
                timeAndCompute(10000000);
        }

        public static void timeAndCompute(final long number) {
                long start = 0, numberofPrime = 0, end = 0;
                NativePrimeFinder nativePrimeFinder = new NativePrimeFinder();
                start = System.nanoTime();
                numberofPrime = nativePrimeFinder.countPrime(number);
                end = System.nanoTime();
                System.out.println("\nJavaNative 单线程实现");
                System.out.println("Number of primes under " + number + " is"
                                + numberofPrime);
                System.out.println("Time taken is " + (end - start) / 1.0e9 + " s");

                SequentialPrimeFinder sequentialPrimeFinder = new SequentialPrimeFinder();
                start = System.nanoTime();
                numberofPrime = sequentialPrimeFinder.countPrime(number);
                end = System.nanoTime();
                System.out.println("\nJavaPure 单线程实现：");
                System.out.println("Number of primes under " + number + " is"
                                + numberofPrime);
                System.out.println("Time taken is " + (end - start) / 1.0e9 + " s");

                for (int i = 4; i < 10; i++) {
                        ConcurrentPrimeFinder concurrentPrimeFinder = new ConcurrentPrimeFinder(
                                        i);
                        start = System.nanoTime();
                        numberofPrime = concurrentPrimeFinder.countPrime(number);
                        end = System.nanoTime();
                        System.out.println("\nJavaPure " + i + "线程实现：");
                        System.out.println("Number of primes under " + number + " is"
                                        + numberofPrime);
                        System.out.println("Time taken is " + (end - start) / 1.0e9 + " s");
                }

                for (int i = 4; i < 10; i++) {
                        MixConcurrentPrimeFinder mixConcurrentPrimeFinder = new MixConcurrentPrimeFinder(
                                        i);
                        start = System.nanoTime();
                        numberofPrime = mixConcurrentPrimeFinder.countPrime(number);
                        end = System.nanoTime();
                        System.out.println("\nJavaPure " + i + "Mix线程实现：");
                        System.out.println("Number of primes under " + number + " is"
                                        + numberofPrime);
                        System.out.println("Time taken is " + (end - start) / 1.0e9 + " s");
                }
        }
}

方兆国 发表于 2013-07-19 13:34

package com.fangzhaoguo.primefinder;

public abstract class AbstractPrimeFinder {

        public abstract boolean isPrime(final long number);

        public abstract int countPrime(final long number);

        public abstract int countPrime(final long lower, final long upper);
}这是一个虚基类,其实也可以写成接口,不过感觉用处不大;
下面的四个例子中,除了JavaNative的例子没有用到这个类,其他三个纯Java的例子都用到了

方兆国 发表于 2013-07-19 13:36

JavaNative的Java类package com.fangzhaoguo.primefinder;

public class NativePrimeFinder {
        static {
                System.loadLibrary("libJavaNative_PrimeFinder");
        }

        public NativePrimeFinder() {

        }

        public native boolean isPrime(final long number);

        public native int countPrime(final long number);

        public native int countPrime(final long lower, final long upper);
}
JavaNative的C头文件,这里只是将#include <jni.h>修改成#include "jni.h"/* DO NOT EDIT THIS FILE - it is machine generated */
#include "jni.h"
/* Header for class com_fangzhaoguo_primefinder_NativePrimeFinder */

#ifndef _Included_com_fangzhaoguo_primefinder_NativePrimeFinder
#define _Included_com_fangzhaoguo_primefinder_NativePrimeFinder
#ifdef __cplusplus
extern "C" {
#endif
        /*
       * Class:   com_fangzhaoguo_primefinder_NativePrimeFinder
       * Method:    isPrime
       * Signature: (J)Z
       */
        JNIEXPORT jboolean JNICALL Java_com_fangzhaoguo_primefinder_NativePrimeFinder_isPrime(
                        JNIEnv *, jobject, jlong);

        /*
       * Class:   com_fangzhaoguo_primefinder_NativePrimeFinder
       * Method:    countPrime
       * Signature: (J)I
       */
        JNIEXPORT jint JNICALL Java_com_fangzhaoguo_primefinder_NativePrimeFinder_countPrime__J(
                        JNIEnv *, jobject, jlong);

        /*
       * Class:   com_fangzhaoguo_primefinder_NativePrimeFinder
       * Method:    countPrime
       * Signature: (JJ)I
       */
        JNIEXPORT jint JNICALL Java_com_fangzhaoguo_primefinder_NativePrimeFinder_countPrime__JJ(
                        JNIEnv *, jobject, jlong, jlong);

#ifdef __cplusplus
}
#endif
#endif
JavaNative的C源文件/*
* com_fangzhaoguo_primefinder_NativePrimeFinder.c
*
*Created on: 2013年7月18日
*      Author: root
*/

#include "com_fangzhaoguo_primefinder_NativePrimeFinder.h"

#include <stdio.h>
#include <math.h>

JNIEXPORT jboolean JNICALL Java_com_fangzhaoguo_primefinder_NativePrimeFinder_isPrime(
                JNIEnv *env, jobject obj, jlong number) {
        jlong i = 0;
        if (1 >= number) {
                return 0;
        }
        for (i = 2; i <= sqrt(number); i++) {
                if (0 == number % i) {
                        return 0;
                }
        }
        return 1;
}

JNIEXPORT jint JNICALL Java_com_fangzhaoguo_primefinder_NativePrimeFinder_countPrime__J(
                JNIEnv *env, jobject obj, jlong number) {
        jint total = 0;
        jlong i = 0;
        for (i = 2; i < number; i++) {
                if (Java_com_fangzhaoguo_primefinder_NativePrimeFinder_isPrime(env, obj,
                                i)) {
                        total++;
                }
        }
        return total;
}

JNIEXPORT jint JNICALL Java_com_fangzhaoguo_primefinder_NativePrimeFinder_countPrime__JJ(
                JNIEnv *env, jobject obj, jlong lower, jlong upper) {
        jint total = 0;
        jlong i = 0;
        for (i = lower; i < upper; i++) {
                if (Java_com_fangzhaoguo_primefinder_NativePrimeFinder_isPrime(env, obj,
                                i)) {
                        total++;
                }
        }
        return total;
}

方兆国 发表于 2013-07-19 13:37

java单线程类package com.fangzhaoguo.primefinder;

public class SequentialPrimeFinder extends AbstractPrimeFinder {

        public SequentialPrimeFinder() {
        }

        public boolean isPrime(final long number) {
                if (1 >= number) {
                        return false;
                }
                for (long i = 2; i < Math.sqrt(number); i++) {
                        if (0 == number % i) {
                                return false;
                        }
                }
                return true;
        }

        @Override
        public int countPrime(long number) {
                int total = 0;
                for (long i = 2; i < number; i++) {
                        if (isPrime(i)) {
                                total++;
                        }
                }
                return total;
        }

        @Override
        public int countPrime(long lower, long upper) {
                int total = 0;
                for (long i = lower; i < upper; i++) {
                        if (isPrime(i)) {
                                total++;
                        }
                }
                return total;
        }

}

方兆国 发表于 2013-07-19 13:39

Java多线程的类
在这个类中，没有对运算进行优化，只是简单的将计算区域划分为与线程个数相同的几个部分package com.fangzhaoguo.primefinder;

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.concurrent.TimeUnit;

public class ConcurrentPrimeFinder extends AbstractPrimeFinder {

        private int poolSize;

        public ConcurrentPrimeFinder(int poolSize) {
                // this.poolSize = Runtime.getRuntime().availableProcessors();
                this.poolSize = poolSize;
        }

        public boolean isPrime(final long number) {
                if (1 >= number) {
                        return false;
                }
                for (long i = 2; i < Math.sqrt(number); i++) {
                        if (0 == number % i) {
                                return false;
                        }
                }
                return true;
        }

        @Override
        public int countPrime(long number) {
                int total = 0;
                List<Callable<Integer>> partitions = new ArrayList<Callable<Integer>>();
                long part = number / poolSize;
                for (int i = 0; i < poolSize; i++) {
                        final long low = (i * part) + 1;
                        final long up = (i == poolSize - 1) ? number : low + part - 1;
                        partitions.add(new Callable<Integer>() {

                                @Override
                                public Integer call() throws Exception {
                                        return countPrimeInRange(low, up);
                                }
                        });
                }

                ExecutorService executorService = Executors
                                .newFixedThreadPool(poolSize);
                try {
                        List<Future<Integer>> reFutures = executorService.invokeAll(
                                        partitions, 10000, TimeUnit.SECONDS);
                        executorService.shutdown();
                        for (Future<Integer> result : reFutures) {
                                total += result.get();
                        }
                } catch (InterruptedException e) {
                        e.printStackTrace();
                } catch (ExecutionException e) {
                        e.printStackTrace();
                }
                return total;
        }

        @Override
        public int countPrime(long lower, long upper) {
                int total = 0;
                return total;
        }

        private int countPrimeInRange(long lower, long upper) {
                int total = 0;
                for (long i = lower; i < upper; i++) {
                        if (isPrime(i)) {
                                total++;
                        }
                }
                return total;
        }
}

方兆国 发表于 2013-07-19 13:41

Java多线程的类
在这个类中，运算进行优化，首先过滤了所有的偶数，因为偶数中只有2 是素数，所以将total的初始值设为1，然后直接忽略偶数。在判断某一个数是不是素数时，不再考虑偶数问题package com.fangzhaoguo.primefinder;

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.concurrent.TimeUnit;

public class MixConcurrentPrimeFinder extends AbstractPrimeFinder {

        private int poolSize;

        public MixConcurrentPrimeFinder(int poolSize) {
                // this.poolSize = Runtime.getRuntime().availableProcessors();
                this.poolSize = poolSize;
        }

        public boolean isPrime(final long number) {
                if (1 >= number) {
                        return false;
                }
                if (3 == number || 5 == number) {
                        return true;
                }
                for (long i = 1; i < Math.sqrt(number); i++) {
                        if (0 == number % (2 * i + 1)) {
                                return false;
                        }
                }
                return true;
        }

        @Override
        public int countPrime(long number) {
                int total = 1;
                List<Callable<Integer>> partitions = new ArrayList<Callable<Integer>>();
                for (int i = 0; i < poolSize; i++) {
                        final long start = 2 * i + 3;
                        final long end = number;
                        partitions.add(new Callable<Integer>() {

                                @Override
                                public Integer call() throws Exception {
                                        return countPrimeInRange(start, end);
                                }
                        });
                }

                ExecutorService executorService = Executors
                                .newFixedThreadPool(poolSize);
                try {
                        List<Future<Integer>> reFutures = executorService.invokeAll(
                                        partitions, 10000, TimeUnit.SECONDS);
                        executorService.shutdown();
                        for (Future<Integer> result : reFutures) {
                                total += result.get();
                        }
                } catch (InterruptedException e) {
                        e.printStackTrace();
                } catch (ExecutionException e) {
                        e.printStackTrace();
                }
                return total;
        }

        @Override
        public int countPrime(long lower, long upper) {
                int total = 0;
                return total;
        }

        private int countPrimeInRange(long start, long end) {
                int total = 0;
                int part = poolSize * 2;
                for (long i = start; i < end; i += part) {
                        if (isPrime(i)) {
                                total++;
                        }
                }
                return total;
        }

}

方兆国 发表于 2013-07-19 13:42

public abstract int countPrime(final long lower, final long upper);这个函数用于计算指定范围内的素数，这例子中并没有予以实现，都是计算0-10000000之间的素数的个数

方兆国 发表于 2013-07-19 13:44

本来打算做两个JavaNative的多线程例子，可是做出来的动态链接库有问题，无法使用，详情请看

JavaNative 使用Boost多线程库的问题   
JavaNative 使用C多线程库的问题

方兆国 发表于 2013-07-19 13:48

我的CPU是Intel i5 430M，虚拟四核的，经过测试，感觉线程数大于等于四，加速效果比较明显，至于后面，就看不出来多少区别了

下面是没有经过优化的Java多线程运行的结果，线程数从1-39JavaNative 单线程实现
Number of primes under 10000000 is664579
Time taken is 21.359702833 s
JavaPure 单线程实现：
Number of primes under 10000000 is664579
Time taken is 29.103943469 s
JavaPure 1线程实现：
Number of primes under 10000000 is664579
Time taken is 26.835752807 s
JavaPure 2线程实现：
Number of primes under 10000000 is664579
Time taken is 17.268595996 s
JavaPure 3线程实现：
Number of primes under 10000000 is664579
Time taken is 14.083862457 s
JavaPure 4线程实现：
Number of primes under 10000000 is664579
Time taken is 12.298518244 s
JavaPure 5线程实现：
Number of primes under 10000000 is664579
Time taken is 11.293884756 s
JavaPure 6线程实现：
Number of primes under 10000000 is664579
Time taken is 11.325465024 s
JavaPure 7线程实现：
Number of primes under 10000000 is664578
Time taken is 11.738370314 s
JavaPure 8线程实现：
Number of primes under 10000000 is664579
Time taken is 11.126746332 s
JavaPure 9线程实现：
Number of primes under 10000000 is664579
Time taken is 11.155879652 s
JavaPure 10线程实现：
Number of primes under 10000000 is664579
Time taken is 11.467730438 s
JavaPure 11线程实现：
Number of primes under 10000000 is664579
Time taken is 11.723364353 s
JavaPure 12线程实现：
Number of primes under 10000000 is664579
Time taken is 11.408438917 s
JavaPure 13线程实现：
Number of primes under 10000000 is664579
Time taken is 11.049511426 s
JavaPure 14线程实现：
Number of primes under 10000000 is664579
Time taken is 11.056839138 s
JavaPure 15线程实现：
Number of primes under 10000000 is664579
Time taken is 11.129368095 s
JavaPure 16线程实现：
Number of primes under 10000000 is664579
Time taken is 11.109334184 s
JavaPure 17线程实现：
Number of primes under 10000000 is664579
Time taken is 11.158874594 s
JavaPure 18线程实现：
Number of primes under 10000000 is664579
Time taken is 11.178487773 s
JavaPure 19线程实现：
Number of primes under 10000000 is664579
Time taken is 11.120964776 s
JavaPure 20线程实现：
Number of primes under 10000000 is664579
Time taken is 11.086961562 s
JavaPure 21线程实现：
Number of primes under 10000000 is664579
Time taken is 11.007674624 s
JavaPure 22线程实现：
Number of primes under 10000000 is664579
Time taken is 11.039509868 s
JavaPure 23线程实现：
Number of primes under 10000000 is664579
Time taken is 11.145095505 s
JavaPure 24线程实现：
Number of primes under 10000000 is664579
Time taken is 10.952947299 s
JavaPure 25线程实现：
Number of primes under 10000000 is664579
Time taken is 11.076983555 s
JavaPure 26线程实现：
Number of primes under 10000000 is664579
Time taken is 10.941116983 s
JavaPure 27线程实现：
Number of primes under 10000000 is664579
Time taken is 10.94612999 s
JavaPure 28线程实现：
Number of primes under 10000000 is664579
Time taken is 11.039012597 s
JavaPure 29线程实现：
Number of primes under 10000000 is664579
Time taken is 10.939461681 s
JavaPure 30线程实现：
Number of primes under 10000000 is664579
Time taken is 10.995222494 s
JavaPure 31线程实现：
Number of primes under 10000000 is664579
Time taken is 10.992655984 s
JavaPure 32线程实现：
Number of primes under 10000000 is664579
Time taken is 10.955971225 s
JavaPure 33线程实现：
Number of primes under 10000000 is664579
Time taken is 11.044467169 s
JavaPure 34线程实现：
Number of primes under 10000000 is664579
Time taken is 10.982884492 s
JavaPure 35线程实现：
Number of primes under 10000000 is664579
Time taken is 10.987279761 s
JavaPure 36线程实现：
Number of primes under 10000000 is664579
Time taken is 11.023815067 s
JavaPure 37线程实现：
Number of primes under 10000000 is664579
Time taken is 11.085869652 s
JavaPure 38线程实现：
Number of primes under 10000000 is664579
Time taken is 10.986662023 s
JavaPure 39线程实现：
Number of primes under 10000000 is664579
Time taken is 10.963607354 s

查看完整版本: Java多线程效率-素数计算