Home Article Practice 素数搜索关键步骤与核心代码分析

素数搜索关键步骤与核心代码分析

2024-06-08 18:10  views:198  source:许某    

AbstractPrimeFinder是整个素数搜索的核心类,其中定义主要的搜寻规则和过程,其核心代码实现如下
:public abstract class AbstractPrimeFinder {//素数的判断过程pu
blic boolean isPrime(final int number){if(number <= 1)
return false;for(int i=2;i<=Math.sqrt(number);i++)if(nu
mber % i==0) return false;return true;}//计算一个区间内的素数的个数p
ublic int countPrimesInRange(final int lower,final int
upper){int total=0;for (int i=lower;i<=upper;i++)if(isP
rime(i)) total++;return total;}//统计程序计算素数所花费的时间public v
oid timeAndCompute(final int number){final long start =
System.nanoTime();final long numberOfPrimes = countPri
mes(number);final long end = System.nanoTime();System.o
ut.printf("Number of primes under %d is %d\n",number,nu
mberOfPrimes);System.out.println("Time (seconds) taken
is:"+(end-start)/1.0e9);}//子类继承实现的抽象方法public abstract i
nt countPrimes(final int number);}在AbstractPrimeFinder基
类中,将素数的寻找过程拆分为素数的判断(isPrime方法)、区间素数的寻找(countPrimesInRan
ge方法)和统计程序寻找最大素数的时间消耗(timeAndCompute方法)。countPrime()方法被
声明为abstract类型,用作素数寻找的入口方法,需要不同的子类进行覆盖实现,不同的执行方式将在此方法中定义
。在timeAndCompute()方法中,调用了此时被声明为abstract类型的countPrimes()
方法,这是面向对象程序设计中一条比较重要的设计方法。SinglePrimeFinder是素数寻找的普通版本,默
认情况下都是基于单线程的方式来执行的。其核心代码实现如下:public class SingleThreadP
rimeFinder extends AbstractPrimeFinder {// 实现父类中的方法@Ove
rridepublic int countPrimes(int number) {return this.co
untPrimesInRange(1, number);}//程序主方法public static void
main(String[] args) {new SingleThreadPrimeFinder().time
AndCompute(30000000);}}在此单线程版本中,countPrimes()方法接收number
参数作为搜索区间的上限,直接调用在基类中声明定义的countPrimesInRange()方法,基于1~num
ber进行素数的搜寻。在main()方法中创建SingleThreadPrimeFinder类的实例,并调用t
imeAndCompute()方法。启动素数的搜寻,并记录其中消耗的时间。在timeAndComputer()
方法中将基于面向对象技术中的多态方式调用countPrimes()方法,从而执行真正的搜寻操作。Concurr
entPrimeFinder实现了素数寻找的多线程版本,其核心代码实现如下:public class Conc
urrentPrimeFinder extends AbstractPrimeFinder {private
final int poolSize;//创建线程池的大小private final int numberOf
Parts;//任务的份数//构造方法初始化线程的个数和任务的划分public ConcurrentPrime
Finder(final int poolSize, final int numberOfParts) {th
is.poolSize = poolSize;this.numberOfParts = numberOfPar
ts;}@Overridepublic int countPrimes(final int number) {
int count=0;//统计各区间的素数个数try {final List> partitions = n
ew ArrayList>();final int chunksPerPartion=number /numb
erOfParts;for(int i=0; ifinal int lower = (i*chunksPerP
artion)+1;final int upper = (i==numberOfParts-1)? numbe
r:lower+chunksPerPartion-1;partitions.add(new Callable(
) {@Overridepublic Integer call() {return countPrimesIn
Range(lower,upper);}});}final ExecutorService executorP
ool = Executors.newFixedThreadPool(poolSize);//在线程池中创建线
程final List> resultFromParts = executorPool.invokeAll(p
artitions,10000,TimeUnit.SECONDS);executorPool.shutdown
();//执行完成之后关闭线程池for(final Future result:resultFromParts
)//统计各任务的素数个数count += result.get();}catch (Exception ex
){throw new RuntimeException(ex);}return count;}//启动4个线
程,4个分组方式来计算public static void main(String[] args){new C
oncurrentPrimeFinder(4,4).timeAndCompute(30000000);}}Co
ncurrentPrimeFinder类中定义了两个属性。poolSize用来定义线程池的大小,表示在程序中可
以并发执行的线程数量。numberOfParts定义了素数搜寻的区间数量。例如,搜寻区间为10 000,设置n
umberOfParts为4,则会生成0~2 500、2 501~5 000、5 001~7 500和7 50
1~10 000 4个搜寻的子区间。这些划分的好处在于,可以充分发挥当前硬件中多线程的优势。将各个区间的搜寻并
发处理,可以极大地提升整个程序的搜寻效率,缩短消耗的时间。类中声明了构造方法ConcurrentPrimeFi
nder()。其中,poolSize和numberOfParts作为入口参数,在构造方法中赋值给实例的对应属性
。countPrime()方法中定义了基于多线程技术实现的素数搜寻过程。在方法实现中,首先声明List的列表结
构,用于存放拆分之后的具体线程任务。Callable是Java语言实现线程并返回结果值的一种实现方式。搜寻素数
的过程根据区间数量进行拆分,并将每一个子区间封装到Callable的对象之内,同时将Callable对象放入L
ist的列表之内。基于Executors工具类声明了poolSize大小的执行线程池。调用线程池executo
rPool的invokeAll()方法,执行List列表中存放的Callable线程任务。在线程池执行完毕,调
用shutdown()方法,关闭线程池。遍历线程池执行的结果resultFromParts,并将其中的结果进行
累计,得到最终的素数个数。在整个执行过程中,线程池存在异常发生的可能,需要进行异常的捕获。这里使用try…ca
tch进行异常的捕获。当异常发生时,将异常栈的信息输出到控制台。对于线程池中的异常,在当前方法中无法处理,于是
创建新的RuntimeException,抛出给调用者,交由调用者根据具体情况来处理。在main()方法中,创
建ConcurrentPrimeFinder实例,指定poolSize为4,素数搜索区间为4,在1~30 00
0 000区间中搜寻存在的素数数量。在此多线程版本中,使用了ExecutorService类型的线程池。基于E
xecutors的线程创建方式和Callable的线程实现方式。此案例是将一个大的执行区间拆分为了若干个彼此独
立的子区间,并将它们分别放入Callable的线程实现中。



Disclaimer: The above articles are added by users themselves and are only for typing and communication purposes. They do not represent the views of this website, and this website does not assume any legal responsibility. This statement is hereby made! If there is any infringement of your rights, please contact us promptly to delete it.

字符:    改为:
去打字就可以设置个性皮肤啦!(O ^ ~ ^ O)