shigen
坚持更新文章的博客写手,擅长Java、python、vue、shell等编程语言和各种应用程序、脚本的开发。记录成长,分享认知,留住感动。
个人IP:shigen
最近的一个面试,shigen
简直被吊打,简历上写了熟悉高并发。完了面试官不按照套路出牌,我说了我用了countdownLanch
,他问forkjoin
了解吗?LRU
怎么设计……一脸懵,尴尬的直接抠脚。
赶紧花时间研究了,顺便看了一下线程池,看到了这样一个经典的案例:
求1-10000_0000的和。
没错,别眼花,是1-1个亿个数字的和。别告诉我,直接循环相加,那就回家等通知吧。
好的,前提就聊到这。看看我这一段炫酷的代码:
天啊,task+递归,和着在线程池不断的玩呗。
一看这种分而治之
,像极了传说中的二分法,经典的分治思想。等等,我咋这么熟悉!
没错,经典的归并排序
,就是这样子的!花了一小时,把这个算法用Java
写出来了。shigen
之前可是用的python
写算法。
java版归并排序
public class MergeSortDemo {
// 归并排序
static void mergeSort(int[] arr, int left, int right) {
if (left < right) {
int mid = (left + right) / 2;
// 简直直接mid
mergeSort(arr, left, mid);
mergeSort(arr, mid + 1, right);
merge(arr, left, mid, right);
}
}
private static void print(int[] arr) {
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + " ");
}
System.out.println();
}
private static void merge(int[] arr, int left, int mid, int right) {
// 构建一个临时数组暂存arr[left, right]之间有序的元素
int[] temp = new int[right - left + 1];
int i = left, j = mid + 1, k = 0;
// while的临界条件需注意,此时分段有序数组合并
// [1,2,3] + [1,3,4,5,6] mid = 4
while (i <= mid && j <= right) {
if (arr[i] < arr[j]) {
temp[k++] = arr[i++];
} else {
temp[k++] = arr[j++];
}
}
// 剩下的元素直接追加即可,两个while只会走一个
while (i <= mid) {
temp[k++] = arr[i++];
}
while (j <= right) {
temp[k++] = arr[j++];
}
// 将temp[] => arr[left, right]
for (i = 0; i < temp.length; i++) {
arr[left + i] = temp[i];
}
}
public static void main(String[] args) {
int[] arr = {
1, 432, 1, 3243, 54, 32, -10, 43, 90};
mergeSort(arr, 0, arr.length - 1);
print(arr);
}
}
看似很复杂,其实一点也不简单。注意点写在代码里了。只能说用Java写算法,真的头大。
python版归并排序
没错,就短短的四行。简洁多了。
接下来,就是重点,如何求1-1个亿数字的和呢?多线程+分段会是不错的选择。
- 1-1_0000
- 1_0001-2_0000
- 2_0001-3_0000
- ……
- 9999_0000-10000_0000
原理就是这个原理,多线程分段的求和,最后再把总体的和算出来。至少两点是确定的,线程池+Futuretask
。
多线程求和
public class ThreadPoolDemo {
@SneakyThrows
public static void main(String[] args) {
int[] arr = new int[10_0000];
for (int i = 0; i < arr.length; i++) {
arr[i] = i + 1;
}
StopWatch stopWatch = new StopWatch();
stopWatch.start();
ExecutorService executor = Executors.newFixedThreadPool(10);
int sum = 0;
int chunkSize = arr.length / 10;
for (int i = 0; i < 10; i++) {
int start = i * chunkSize;
int end = (i == 9) ? arr.length : (start + chunkSize);
sum += executor.submit(new SumTask(arr, start, end)).get();
}
executor.shutdown();
stopWatch.stop();
System.out.println("Sum of 1 to 100000 is: " + sum);
System.out.println("代码执行时间:" + stopWatch.getLastTaskTimeMillis() + "毫秒");
}
}
class SumTask implements Callable<Integer> {
private final int[] arr;
private final int start;
private final int end;
public SumTask(int[] arr, int start, int end) {
this.arr = arr;
this.start = start;
this.end = end;
}
@Override
public Integer call() {
int sum = 0;
for (int i = start; i < end; i++) {
sum += arr[i];
}
return sum;
}
}
看着很多,核心的一段就是这个:
for (int i = 0; i < 10; i++) {
int start = i * chunkSize;
int end = (i == 9) ? arr.length : (start + chunkSize);
sum += executor.submit(new SumTask(arr, start, end)).get();
}
创建任务->装进线程池->获得结果->关闭线程池。
但是,在这种情况下,还能继续的优化吗?其实也是可以的,因为现在数组还是太长了,而且计算的线程不是足够的多,性能上肯定不是最优的。
多线程+分治求和
这就是今天的主角:多线程+分治
实现求和。还是先看代码:
public class SumRecursive {
public static class RecursiveSumTask implements Callable<Long> {
// 拆分粒度
public static final int THRESHOLD = 10_0000;
int low;
int high;
int[] arr;
ExecutorService executorService;
RecursiveSumTask(ExecutorService executorService, int[] arr, int low, int high) {
this.executorService = executorService;
this.arr = arr;
this.low = low;
this.high = high;
}
@Override
public Long call() throws Exception {
long result = 0;
if (high - low < THRESHOLD) {
for (int i = low; i < high; i++) {
result += arr[i];
}
} else {
int mid = (low + high) / 2;
RecursiveSumTask leftTask = new RecursiveSumTask(executorService, arr, low, mid);
RecursiveSumTask rightTask = new RecursiveSumTask(executorService, arr, mid, high);
Future<Long> lr = executorService.submit(leftTask);
Future<Long> rr = executorService.submit(rightTask);
result = lr.get() + rr.get();
}
return result;
}
}
@SneakyThrows
public static void main(String[] args) {
int[] arr = new int[10000_0000];
for (int i = 0; i < arr.length; i++) {
arr[i] = i + 1;
}
StopWatch stopWatch = new StopWatch();
stopWatch.start();
ExecutorService executorService = Executors.newCachedThreadPool();
RecursiveSumTask recursiveSumTask = new RecursiveSumTask(executorService, arr, 0, arr.length);
Long result = executorService.submit(recursiveSumTask).get();
executorService.shutdown();
stopWatch.stop();
System.out.println("Sum of 1 to 100000 is: " + result);
System.out.println("代码执行时间:" + stopWatch.getLastTaskTimeMillis() + "毫秒");
}
}
说实话,代码在显示器上显示真的太好看了,忍不住的截图分享了。
那这里的不同点在于使用了分治思想,当我们的数组的长度小于阈值的时候,就直接计算和;但是大于阈值的之后,就会继续的拆分。
总之总体的设计和逻辑真的像极了上文提到的MergeSort
,先分的足够小,然后合并,获得最终的结果。
当然,这种设计也并不是最好的,因为我们的线程池设计,或者说线程池等待队列的大小是不好把控的,所以我们线程池的等待队列是2147483647
长度的同步队列。完了,又要考虑到OOM
!
接下来会分享
forkjoin
,期待继续关注!文章代码点击这里。
与shigen一起,每天不一样!