超えることを求めて、計算はNの素数の個数に等しくありません
最近の2日間はグループの友達とN以下の素数の個数を計算することを議論した.最も直接的なアルゴリズムは、各数iについて、計算iを2からiの平方根で割ったものであり、いずれかを除去できることは、iが素数ではないことを示している.しかし,このアルゴリズムは効率が低く,大きな改善空間があり,異なる方法で改善されている.
liuyh17211の考え方はアルゴリズムの改良であり、さんじゅつきほんていりによれば、いずれの合数も2つ以上の素数の積として表すことができるので、iが素数であるか否かを判断するには、iを2からiの平方根の間の素数で割るだけでよい、またjava計算平方根の算出効率も高くなく、このような考え方で改造したアルゴリズムの効率が大幅に向上し、Nが10000,000の場合,素朴なアルゴリズムの約1/7程度の時間がかかり,この方法は単核または多核の機械に有効である.しかし、このアルゴリズムは1つのスレッドしか使用されず、マルチコアプロセッサではリソースを十分に利用していない.
群友宝を洗って山を定めるが提供する構想はマルチスレッドを利用して、機械のcpuを十分に利用することであるが、アルゴリズムの上であまり最適化していない.この方式はホストのcpuコア数と使用するスレッド数と密接に関連しており、効果も非常に明らかで、彼のクアッドコアマシンでは、8つのスレッドを使用する場合、計算時間はほとんど素朴な方法の1/4余りである.全体的にマルチスレッドはアルゴリズム最適化よりも少し悪い.
liuyh17211は,この2つの最適化方式を組み合わせるとより効果的であるべきであると考え,まず単一スレッドでNの平方根の素数配列を計算し,その後マルチスレッドセグメントで素数個数を計算し,最後にまとめた.しかし、この方式はアルゴリズムが複雑で、コードも長い.アルゴリズムが完了したら、私のデュアルコア4スレッドマシンで4つのスレッドで走って、最適化アルゴリズムの約40%を費やします.
週末にliuyh17211でコードを家のシングルコアマシンに持って行って測定したところ、シングルコアのマシンではマルチスレッドの役割が小さく、最適化アルゴリズムの収益はほとんど損失していないことが分かった.
現在、このアルゴリズムはマルチコアマシン上で効率が高く、ここで効率の高いアルゴリズムと改善構想を求め、Java Developers 67844123への交流も歓迎している.
すべてのコードを添付し、宝を洗って山を定めるから提供されたマルチスレッド計算コードに改めて感謝します.
liuyh17211の考え方はアルゴリズムの改良であり、さんじゅつきほんていりによれば、いずれの合数も2つ以上の素数の積として表すことができるので、iが素数であるか否かを判断するには、iを2からiの平方根の間の素数で割るだけでよい、またjava計算平方根の算出効率も高くなく、このような考え方で改造したアルゴリズムの効率が大幅に向上し、Nが10000,000の場合,素朴なアルゴリズムの約1/7程度の時間がかかり,この方法は単核または多核の機械に有効である.しかし、このアルゴリズムは1つのスレッドしか使用されず、マルチコアプロセッサではリソースを十分に利用していない.
群友宝を洗って山を定めるが提供する構想はマルチスレッドを利用して、機械のcpuを十分に利用することであるが、アルゴリズムの上であまり最適化していない.この方式はホストのcpuコア数と使用するスレッド数と密接に関連しており、効果も非常に明らかで、彼のクアッドコアマシンでは、8つのスレッドを使用する場合、計算時間はほとんど素朴な方法の1/4余りである.全体的にマルチスレッドはアルゴリズム最適化よりも少し悪い.
liuyh17211は,この2つの最適化方式を組み合わせるとより効果的であるべきであると考え,まず単一スレッドでNの平方根の素数配列を計算し,その後マルチスレッドセグメントで素数個数を計算し,最後にまとめた.しかし、この方式はアルゴリズムが複雑で、コードも長い.アルゴリズムが完了したら、私のデュアルコア4スレッドマシンで4つのスレッドで走って、最適化アルゴリズムの約40%を費やします.
週末にliuyh17211でコードを家のシングルコアマシンに持って行って測定したところ、シングルコアのマシンではマルチスレッドの役割が小さく、最適化アルゴリズムの収益はほとんど損失していないことが分かった.
現在、このアルゴリズムはマルチコアマシン上で効率が高く、ここで効率の高いアルゴリズムと改善構想を求め、Java Developers 67844123への交流も歓迎している.
すべてのコードを添付し、宝を洗って山を定めるから提供されたマルチスレッド計算コードに改めて感謝します.
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.concurrent.Callable;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;
import java.util.concurrent.FutureTask;
/**
*
* @author [email protected]
*/
public class PrimeCount {
//
private static final int cpuNum = Runtime.getRuntime().availableProcessors();
/**
* @param args
* @throws Exception
*/
public static void main(String[] args) throws Exception {
int max = 10000000;
long begin = System.currentTimeMillis();
int count = primaevalCounting(max);
long end = System.currentTimeMillis();
System.out.println("primaevalCounting prime count=" + count + ",time cost=" + (end - begin)+"ms");
begin = System.currentTimeMillis();
count = optimizedCounting(max);
end = System.currentTimeMillis();
System.out.println("optimizedCounting prime count=" + count + ",time cost=" + (end - begin)+"ms");
begin = System.currentTimeMillis();
count = multThreadPrimaevalCounting(max);
end = System.currentTimeMillis();
System.out.println("multThreadPrimaevalCounting prime count=" + count + ",time cost=" + (end - begin)+"ms");
begin = System.currentTimeMillis();
count = multThreadOptimizedcounting(max);
end = System.currentTimeMillis();
System.out.println("multThreadOptimizedcounting prime count=" + count + ",time cost=" + (end - begin)+"ms");
System.exit(0);
}
/**
* +
*
* @param x
* @return
*/
public static int primaevalCounting(int x){
int count = 0;
for(int i = 2 ; i <= x ; i++){
boolean isPrime = true;
int sqrt = (int)Math.sqrt(i);
for(int j = 2 ; j <= sqrt ; j++){
if(i % j == 0){
isPrime = false;
break;
}
}
if(isPrime){
count++;
}
}
return count;
}
/**
* +
* cpu
* @param N
* @return
*/
private static int optimizedCounting(int N){
int n = (int)Math.sqrt(N);
int[] primeList = new int[n];
int max = 0;
int primeCount = 0,d = 1,product = 1;
boolean isPrime = true;
for(int i = 2 ; i < N ; i++){
if(i > product){
d++;
product = d*d;
}
for(int j = 0 ; j < max ; j++){
int primeNum = primeList[j];
if(primeNum > d){
break;
}
if(i%primeNum == 0){
isPrime = false;
break;
}
}
if(isPrime){
if(i < n){
primeList[primeCount] = i;
max++;
}
primeCount++;
}
isPrime = true;
}
return primeCount;
}
/**
* +
* @param x
* @return
*/
public static int multThreadPrimaevalCounting(int x) throws Exception{
int threadNum = cpuNum > 4 ? cpuNum : 4;
int size = x/threadNum;
int count = 0;
List<PrimaevalCounting> countList = new ArrayList<PrimaevalCounting>();
List<FutureTask<Integer>> taskList = new ArrayList<FutureTask<Integer>>();
ExecutorService exec = Executors.newFixedThreadPool(5);
PrimaevalCounting first = new PrimaevalCounting(2, size);
countList.add(first);
FutureTask<Integer> task = new FutureTask<Integer>(first);
exec.submit(task);
taskList.add(task);
for(int i=1;i<threadNum;i++){
PrimaevalCounting pre = countList.get(i-1);
int begin = pre.end+1;
int end = begin +size;
if(end>x){
end=x;
}
PrimaevalCounting counter = new PrimaevalCounting(begin, end);
countList.add(counter);
task = new FutureTask<Integer>(counter);
exec.submit(task);
taskList.add(task);
}
for(FutureTask<Integer> t : taskList){
count += t.get();
}
return count;
}
/**
*
* @author [email protected]
*
*/
public static class PrimaevalCounting implements Callable<Integer> {
public int begin = 0;
public int end = 0;
public PrimaevalCounting(int begin, int end) {
this.begin = begin;
this.end = end;
}
@Override
public Integer call() throws Exception {
int c = 0;
for (int i = begin; i <= end; i++) {
int s = (int) Math.sqrt(i);
boolean f = true;
for (int j = 2; j <= s; j++) {
if (i % j == 0) {
f = false;
break;
}
}
if (f) {
c++;
}
}
return c;
}
}
/**
* +
* @param x
* @return
* @throws Exception
*/
public static int multThreadOptimizedcounting(int x) throws Exception {
int threadNum = cpuNum > 4 ? cpuNum : 4;
int size = x / threadNum;
int count = 0;
List<OptimizedCounting> countList = new ArrayList<OptimizedCounting>();
List<FutureTask<Integer>> taskList = new ArrayList<FutureTask<Integer>>();
int[] primeArray = initPrimeArray(x);
ExecutorService exec = Executors.newFixedThreadPool(10);
OptimizedCounting first = new OptimizedCounting((int)Math.sqrt(x) + 1, size, primeArray);
countList.add(first);
FutureTask<Integer> task = new FutureTask<Integer>(first);
exec.submit(task);
taskList.add(task);
for(int i = 1 ; i < threadNum ; i++){
OptimizedCounting pre = countList.get(i-1);
int begin = pre.end+1;
int end = begin +size;
if(end > x){
end=x;
}
OptimizedCounting counter = new OptimizedCounting(begin, end, primeArray);
countList.add(counter);
task = new FutureTask<Integer>(counter);
exec.submit(task);
taskList.add(task);
}
for(FutureTask<Integer> t : taskList){
count += t.get();
}
return count + primeArray.length;
}
/**
* 2 x ，
* @param x
* @return
*/
private static int[] initPrimeArray(int x) {
int n = (int)Math.sqrt(x);
int[] primeArray = new int[n];
int max = 0;
int primeCount = 0,d = 1,product = 1;
boolean isPrime = true;
for(int i = 2 ; i <= n ; i++){
if(i > product){
d++;
product = d * d;
}
for(int j = 0 ; j < max ; j++){
int primeNum = primeArray[j];
if(primeNum > d){
break;
}
if(i % primeNum == 0){
isPrime = false;
break;
}
}
if(isPrime){
if(i < n){
primeArray[primeCount] = i;
max++;
}
primeCount++;
}
isPrime = true;
}
return Arrays.copyOf(primeArray, max);
}
/**
*
* @author [email protected]
*
*/
public static class OptimizedCounting implements Callable<Integer> {
private int begin = 0;
private int end = 0;
private int[] primeArray;
public OptimizedCounting(int begin, int end, int[] primeArray) {
this.begin = begin;
this.end = end;
this.primeArray = primeArray;
}
@Override
public Integer call() throws Exception {
int c = 0;
// ，
int d = (int)Math.sqrt(begin) + 1,prod = begin;
boolean isPrime = true;
for (int i = begin ; i <= end ; i++) {
if(i > prod){
d++;
prod = d * d;
}
for (int j = 0 ; j < primeArray.length && primeArray[j] <= d ; j++) {
if (i % primeArray[j] == 0) {
isPrime = false;
break;
}
}
if (isPrime) {
c++;
}
isPrime = true;
}
return c;
}
}
}