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

2023-11-03 10:12

本文主要是介绍阿里淘系第五面coding题:实现亿级int数据量的一个array求和,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

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

先讲方案,再讲实现


文章目录

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


方案思路:

1、普通循环累加
2、多线程求和
3、使用并行流(Parallel Stream)
4、使用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

五、总结

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

这篇关于阿里淘系第五面coding题:实现亿级int数据量的一个array求和的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/337469

相关文章

Qt把文件夹从A移动到B的实现示例

《Qt把文件夹从A移动到B的实现示例》本文主要介绍了Qt把文件夹从A移动到B的实现示例,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学... 目录如何移动一个文件? 如何移动文件夹(包含里面的全部内容):如何删除文件夹:QT 文件复制,移动(

Flask 验证码自动生成的实现示例

《Flask验证码自动生成的实现示例》本文主要介绍了Flask验证码自动生成的实现示例,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习... 目录生成图片以及结果处理验证码蓝图html页面展示想必验证码大家都有所了解,但是可以自己定义图片验证码

VSCode配置Anaconda Python环境的实现

《VSCode配置AnacondaPython环境的实现》VisualStudioCode中可以使用Anaconda环境进行Python开发,本文主要介绍了VSCode配置AnacondaPytho... 目录前言一、安装 Visual Studio Code 和 Anaconda二、创建或激活 conda

使用mvn deploy命令上传jar包的实现

《使用mvndeploy命令上传jar包的实现》本文介绍了使用mvndeploy:deploy-file命令将本地仓库中的JAR包重新发布到Maven私服,文中通过示例代码介绍的非常详细,对大家的学... 目录一、背景二、环境三、配置nexus上传账号四、执行deploy命令上传包1. 首先需要把本地仓中要

JAVA封装多线程实现的方式及原理

《JAVA封装多线程实现的方式及原理》:本文主要介绍Java中封装多线程的原理和常见方式,通过封装可以简化多线程的使用,提高安全性,并增强代码的可维护性和可扩展性,需要的朋友可以参考下... 目录前言一、封装的目标二、常见的封装方式及原理总结前言在 Java 中,封装多线程的原理主要围绕着将多线程相关的操

MySQL中实现多表查询的操作方法(配sql+实操图+案例巩固 通俗易懂版)

《MySQL中实现多表查询的操作方法(配sql+实操图+案例巩固通俗易懂版)》本文主要讲解了MySQL中的多表查询,包括子查询、笛卡尔积、自连接、多表查询的实现方法以及多列子查询等,通过实际例子和操... 目录复合查询1. 回顾查询基本操作group by 分组having1. 显示部门号为10的部门名,员

java导出pdf文件的详细实现方法

《java导出pdf文件的详细实现方法》:本文主要介绍java导出pdf文件的详细实现方法,包括制作模板、获取中文字体文件、实现后端服务以及前端发起请求并生成下载链接,需要的朋友可以参考下... 目录使用注意点包含内容1、制作pdf模板2、获取pdf导出中文需要的文件3、实现4、前端发起请求并生成下载链接使

Java的volatile和sychronized底层实现原理解析

《Java的volatile和sychronized底层实现原理解析》文章详细介绍了Java中的synchronized和volatile关键字的底层实现原理,包括字节码层面、JVM层面的实现细节,以... 目录1. 概览2. Synchronized2.1 字节码层面2.2 JVM层面2.2.1 ente

Linux下修改hostname的三种实现方式

《Linux下修改hostname的三种实现方式》:本文主要介绍Linux下修改hostname的三种实现方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录linux下修改ho编程stname三种方式方法1:修改配置文件方法2:hFvEWEostnamectl命

Java实现数据库图片上传功能详解

《Java实现数据库图片上传功能详解》这篇文章主要为大家详细介绍了如何使用Java实现数据库图片上传功能,包含从数据库拿图片传递前端渲染,感兴趣的小伙伴可以跟随小编一起学习一下... 目录1、前言2、数据库搭建&nbsChina编程p; 3、后端实现将图片存储进数据库4、后端实现从数据库取出图片给前端5、前端拿到