java 10000阶乘_Java ForkJoinPool: 3秒计算100万的阶乘
問題背景&思路
如果需要計算100的階乘,那應該怎么做?
方法1:
for循環(默認,單線程)
方法2:
多線程,MapReduce思想
main線程開啟多個子任務(個數=CPU核心數),放到線程池執行,每個子任務統計from ~ to的正整數,然后返回本次計算的結果;然后main線程拿到所有子任務的返回結果后再次統計
任務: SumTask implements Callable,返回統計結果Future
方法3:
ForkJoinPool,遞歸任務,MapReduce思想
任務:SumTask extends RecursiveTask,返回統計結果BigDecimal
任務中判斷,當需要統計的數>某個閾值時,拆分成兩個任務;否則直接執行并返回
這個閾值時多少合適?經過測試后,當計算10000的階乘時,方法1略快于方法2,所以這個閾值就定位10000
上代碼
為了方便測試,先定義了一個接口:
package com.wz.poc.forkjoin;
import java.math.BigDecimal;
/**
* @author liweizhi
* @date 2020/12/31
*/
public interface Calculator {
/**
* 求傳進來數的階乘
*
* @param number
* @return 總和
*/
BigDecimal factorial(long number);
}
單線程循環
package com.wz.poc.forkjoin;
import java.math.BigDecimal;
/**
* @author liweizhi
* @date 2020/12/31
*/
public class ForLoopCalculator implements Calculator {
@Override
public BigDecimal factorial(long number) {
BigDecimal ret = new BigDecimal(1);
for (long i = 1; i <= number; i++) {
ret = ret.multiply(BigDecimal.valueOf(i));
}
return ret;
}
}
普通線程池,多線程
package com.wz.poc.forkjoin;
import java.math.BigDecimal;
import java.util.ArrayList;
import java.util.List;
import java.util.concurrent.Callable;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;
import java.util.concurrent.Future;
/**
* @author liweizhi
* @date 2020/12/31
*/
public class ExecutorServiceCalculator implements Calculator {
@Override
public BigDecimal factorial(long number) {
List> results = new ArrayList<>();
// 把任務分解為 n 份，交給 n 個線程處理 4核心 就等分成4份唄
// 然后把每一份都扔個一個SumTask線程 進行處理
long pageSize = number / parallism;
for (int i = 0; i < parallism; i++) {
long from = i * pageSize + 1; //開始位置
long to = i == parallism - 1 ? number : Math.min(from + pageSize - 1, number); //結束位置
//扔給線程池計算
results.add(pool.submit(new SumTask(from, to)));
}
// 把每個線程的結果相加，得到最終結果 get()方法 是阻塞的
// 優化方案：可以采用CompletableFuture來優化 JDK1.8的新特性
BigDecimal ret = BigDecimal.valueOf(1);
for (Future f : results) {
try {
ret = f.get().multiply(ret);
} catch (Exception ignore) {
}
}
// 方便測試程序退出
pool.shutdown();
return ret;
}
private static final int parallism = Runtime.getRuntime().availableProcessors();
private static final ExecutorService pool = Executors.newFixedThreadPool(parallism);
//處理計算任務的線程
private static class SumTask implements Callable {
private long from;
private long to;
public SumTask(long from, long to) {
this.from = from;
this.to = to;
}
@Override
public BigDecimal call() {
BigDecimal ret = new BigDecimal(1);
for (long i = from; i <= to; i++) {
ret = ret.multiply(BigDecimal.valueOf(i));
}
return ret;
}
}
}
ForkJoinPool
package com.wz.poc.forkjoin;
import java.math.BigDecimal;
import java.util.concurrent.ForkJoinPool;
import java.util.concurrent.RecursiveTask;
/**
* @author liweizhi
* @date 2020/12/31
*/
public class ForkJoinCalculator implements Calculator {
@Override
public BigDecimal factorial(long number) {
BigDecimal invoke = pool.invoke(new SumTask(1, number));
// 方便測試程序退出
pool.shutdown();
return invoke;
}
private static final ForkJoinPool pool = new ForkJoinPool();
//執行任務RecursiveTask：有返回值 RecursiveAction：無返回值
private static class SumTask extends RecursiveTask {
private long from;
private long to;
public SumTask(long from, long to) {
this.from = from;
this.to = to;
}
//此方法為ForkJoin的核心方法：對任務進行拆分 拆分的好壞決定了效率的高低
@Override
protected BigDecimal compute() {
// 當需要計算的數字個數小于1_0000時，直接采用for loop方式計算結果
if (to - from < 1_0000) {
BigDecimal ret = new BigDecimal(1);
for (long i = from; i <= to; i++) {
ret = ret.multiply(BigDecimal.valueOf(i));
}
return ret;
} else { // 否則，把任務一分為二，遞歸拆分(注意此處有遞歸)到底拆分成多少分 需要根據具體情況而定
long middle = (from + to) / 2;
SumTask taskLeft = new SumTask(from, middle);
SumTask taskRight = new SumTask(middle + 1, to);
taskLeft.fork();
taskRight.fork();
return taskLeft.join().multiply(taskRight.join());
}
}
}
}
測試main方法
package com.wz.poc.forkjoin;
import java.math.BigDecimal;
import java.time.Duration;
import java.time.Instant;
/**
* @author liweizhi
* @date 2020/12/31
*/
public class MainTest {
public static void main(String[] args) {
long numbers = 100_0000;
Calculator forLoopCalculator = new ForLoopCalculator();
Calculator executorServiceCalculator = new ExecutorServiceCalculator();
Calculator forkJoinCalculator = new ForkJoinCalculator();
Instant start, end;
// 熱熱身
forLoopCalculator.factorial(10000);
start = Instant.now();
BigDecimal result_1 = forLoopCalculator.factorial(numbers);
end = Instant.now();
System.out.println("forLoopCalculator耗時：" + Duration.between(start, end).toMillis() + "ms");
start = Instant.now();
BigDecimal result_2 = executorServiceCalculator.factorial(numbers);
end = Instant.now();
System.out.println("executorServiceCalculator：" + Duration.between(start, end).toMillis() + "ms");
start = Instant.now();
BigDecimal result_3 = forkJoinCalculator.factorial(numbers);
end = Instant.now();
System.out.println("forkJoinCalculator：" + Duration.between(start, end).toMillis() + "ms");
System.out.println("三者是否相等" + (result_1.equals(result_2) && result_1.equals(result_3)));
}
}
測試結果
電腦信息
我的電腦是一臺筆記本,聯想的thinkbook2021,
魯大師電腦概覽:
電腦型號聯想 20VF 筆記本電腦 (掃描時間：2020年12月31日)
操作系統Windows 10 64位 ( DirectX 12 )
處理器AMD Ryzen 5 4600U with Radeon Graphics 六核
主板聯想 LNVNB161216 ( AMD PCI 標準主機 CPU 橋 )
內存16 GB ( DDR4 3200MHz )
主硬盤三星 MZALQ512HALU-000L2 ( 512 GB / 固態硬盤 )
主顯卡AMD Radeon Graphics ( 512 MB / 聯想 )
顯示器友達 AUO683D ( 14 英寸 )
聲卡瑞昱 @ AMD High Definition Audio 控制器
網卡瑞昱 RTL8168/8111/8112 Gigabit Ethernet Controller / 聯想
三種方法輸出結果(計算1萬,10萬,100萬的階乘)
10000:
forLoopCalculator耗時：27ms
executorServiceCalculator：28ms
forkJoinCalculator：36ms
10_0000:
forLoopCalculator耗時：2905ms
executorServiceCalculator：393ms
forkJoinCalculator：151ms
100_0000:
forLoopCalculator耗時：351565ms
executorServiceCalculator：17955ms
forkJoinCalculator：2667ms
三者是否相等true
本文地址：https://blog.csdn.net/weixin_42008012/article/details/112008229
如您對本文有疑問或者有任何想說的，請點擊進行留言回復，萬千網友為您解惑！
總結
以上是生活随笔為你收集整理的java 10000阶乘_Java ForkJoinPool: 3秒计算100万的阶乘的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： impala元数据放到mysql_imp
- 下一篇： java的基础语法是什么_java语法基