阿里淘系第五面coding题：实现亿级int数据量的一个array求和

阿里淘系第五面coding题：实现亿级int数据量的一个array求和"/>

阿里淘系第五面coding题：实现亿级int数据量的一个array求和

阿里淘系第五面coding题：实现亿级int数据量的一个array求和，接下来由你表演

先讲方案，再讲实现

文章目录

• 阿里淘系第五面coding题：实现亿级int数据量的一个array求和，接下来由你表演
• 方案思路：
• 一、普通循环累加
• • 💡通过遍历整个数组，并将每个元素累加到一个变量中，最后得到总和
• 二、多线程求和
• • 💡将数组拆分为多个子数组，然后使用多个线程并行计算每个子数组的和，最后将各个子数组的和相加得到总和
• 三、使用并行流（Parallel Stream）
• • 💡Java 8引入了Stream API，通过将数组转换成并行流，可以使用内置的并行处理能力进行求和
• 四、使用Fork/Join
• • 💡将任务分解为多个子任务，并使用 fork() 方法在新线程中异步执行子任务，最后通过 join() 方法等待子任务的执行结果，并将其合并成整个任务的结果便得到总和
• 五、总结

方案思路：

Tips：下列代码实现效果与计算机自身CPU的计算能力、数据量、线程数相关，本文测试数据仅供参考！

一、普通循环累加

💡通过遍历整个数组，并将每个元素累加到一个变量中，最后得到总和

    public static void testCycleComputing(){Random random = new Random();int[] array = new int[100000000];Arrays.fill(array, random.nextInt(10000));long startTime = System.currentTimeMillis();int result = 0;for (int i = 0; i < array.length; i++) {result += array[i];}long endTime = System.currentTimeMillis();System.out.printf("总计为：%d ,总耗时：%s ms",result,(endTime - startTime));}

结果耗时如下：
总计为：2127125760 ,总耗时：67 ms

二、多线程求和

💡将数组拆分为多个子数组，然后使用多个线程并行计算每个子数组的和，最后将各个子数组的和相加得到总和

public static void testThreadCal(){Random random = new Random();int[] array = new int[100000000];Arrays.fill(array, random.nextInt(10000));CalThread[] threads = new CalThread[4];int numThreads = 2;int blockSize = array.length / numThreads; // 每个线程处理的子数组大小long startTime = System.currentTimeMillis();// 创建并启动线程for (int i = 0; i < numThreads; i++) {int start = i * blockSize;int end = (i == numThreads - 1) ? array.length : start + blockSize;threads[i] = new CalThread(array, start, end);threads[i].start();}int result = 0;// 等待所有线程执行完毕，并累加各个子数组的和for (int i = 0; i < numThreads; i++) {try {threads[i].join();result += threads[i].getPartialSum();} catch (InterruptedException e) {e.printStackTrace();}}long endTime = System.currentTimeMillis();System.out.printf("总计为：%d ,总耗时：%s ms",result,(endTime - startTime));}

结果耗时如下：
总计为：-767641600 ,总耗时：46 ms

三、使用并行流（Parallel Stream）

💡Java 8引入了Stream API，通过将数组转换成并行流，可以使用内置的并行处理能力进行求和

    public static void testParallel(){Random random = new Random();int[] array = new int[100000000];Arrays.fill(array, random.nextInt(10000));long startTime = System.currentTimeMillis();int result = Arrays.stream(array).parallel().sum();long endTime = System.currentTimeMillis();System.out.printf("总计为：%d ,总耗时：%s ms",result,(endTime - startTime));}

结果耗时如下：
总计为：1305686784 ,总耗时：116 ms

四、使用Fork/Join

💡将任务分解为多个子任务，并使用 fork() 方法在新线程中异步执行子任务，最后通过 join() 方法等待子任务的执行结果，并将其合并成整个任务的结果便得到总和

import java.util.Arrays;
import java.util.Random;
import java.util.concurrent.ForkJoinPool;
import java.util.concurrent.RecursiveTask;public class SumArrayExample {private static final int THRESHOLD = 100000; // 阈值public static void main(String[] args) {int[] arr = new int[100000000];Random random = new Random();Arrays.fill(arr,  random.nextInt(10000));ForkJoinPool pool = new ForkJoinPool();long startTime = System.currentTimeMillis();int result = pool.invoke(new SumArrayTask(arr, 0, arr.length)); // 执行任务long endTime = System.currentTimeMillis();System.out.printf("总计为：%d ,总耗时：%s ms",result,(endTime - startTime));}static class SumArrayTask extends RecursiveTask<Integer> {private int[] arr;private int start;private int end;public SumArrayTask(int[] arr, int start, int end) {this.arr = arr;this.start = start;this.end = end;}@Overrideprotected Integer compute() {if (end - start <= THRESHOLD) { // 如果数据量小于阈值，直接求和int sum = 0;for (int i = start; i < end; i++) {sum += arr[i];}return sum;} else { // 如果数据量较大，将任务分解为子任务int mid = (start + end) / 2;SumArrayTask leftTask = new SumArrayTask(arr, start, mid);SumArrayTask rightTask = new SumArrayTask(arr, mid, end);leftTask.fork();rightTask.fork();return leftTask.join() + rightTask.join();}}}
}

首先生成了一个长度为 100000000 的 int 数组，将其随机填充。然后创建了 Fork/Join 线程池，并在主线程中调用 pool.invoke() 方法执行任务。
在 SumArrayTask 类中，我们判断当前任务的数据量是否小于阈值，如果小于阈值，则直接求和；否则，将任务分解为两个子任务，分别计算并返回结果。

结果耗时如下：
总计为：-386664192 ,总耗时：50 ms

五、总结

像面试这种编码题时不用急着想最优解，面试官更多的是看你了解的广度是否达到他的预期！