Java多线程+分治求和,太牛了

简介: `shigen`,一位擅长Java、Python、Vue和Shell的博主,分享编程知识和成长体验。在一次面试中因对高并发问题准备不足而受挫,随后深入学习,研究了线程池和经典案例——计算1亿数字的和。采用分治策略,`shigen`实现了Java版的归并排序,并对比了Python的简洁实现。通过多线程和分段求和优化,展示了如何高效解决大数求和问题,引入了分治思想的递归任务来进一步提升性能。未来将探讨`forkjoin`框架。关注`shigen`,每天学习新知识!

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版归并排序

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一起,每天不一样!

目录
相关文章
|
8天前
|
安全 Java 测试技术
Java并行流陷阱:为什么指定线程池可能是个坏主意
本文探讨了Java并行流的使用陷阱,尤其是指定线程池的问题。文章分析了并行流的设计思想,指出了指定线程池的弊端,并提供了使用CompletableFuture等替代方案。同时,介绍了Parallel Collector库在处理阻塞任务时的优势和特点。
|
4天前
|
安全 Java 开发者
深入解读JAVA多线程:wait()、notify()、notifyAll()的奥秘
在Java多线程编程中,`wait()`、`notify()`和`notifyAll()`方法是实现线程间通信和同步的关键机制。这些方法定义在`java.lang.Object`类中,每个Java对象都可以作为线程间通信的媒介。本文将详细解析这三个方法的使用方法和最佳实践,帮助开发者更高效地进行多线程编程。 示例代码展示了如何在同步方法中使用这些方法,确保线程安全和高效的通信。
22 9
|
7天前
|
存储 安全 Java
Java多线程编程的艺术:从基础到实践####
本文深入探讨了Java多线程编程的核心概念、应用场景及其实现方式,旨在帮助开发者理解并掌握多线程编程的基本技能。文章首先概述了多线程的重要性和常见挑战,随后详细介绍了Java中创建和管理线程的两种主要方式:继承Thread类与实现Runnable接口。通过实例代码,本文展示了如何正确启动、运行及同步线程,以及如何处理线程间的通信与协作问题。最后,文章总结了多线程编程的最佳实践,为读者在实际项目中应用多线程技术提供了宝贵的参考。 ####
|
4天前
|
监控 安全 Java
Java中的多线程编程:从入门到实践####
本文将深入浅出地探讨Java多线程编程的核心概念、应用场景及实践技巧。不同于传统的摘要形式,本文将以一个简短的代码示例作为开篇,直接展示多线程的魅力,随后再详细解析其背后的原理与实现方式,旨在帮助读者快速理解并掌握Java多线程编程的基本技能。 ```java // 简单的多线程示例:创建两个线程,分别打印不同的消息 public class SimpleMultithreading { public static void main(String[] args) { Thread thread1 = new Thread(() -> System.out.prin
|
7天前
|
Java
JAVA多线程通信:为何wait()与notify()如此重要?
在Java多线程编程中,`wait()` 和 `notify()/notifyAll()` 方法是实现线程间通信的核心机制。它们通过基于锁的方式,使线程在条件不满足时进入休眠状态,并在条件满足时被唤醒,从而确保数据一致性和同步。相比其他通信方式,如忙等待,这些方法更高效灵活。 示例代码展示了如何在生产者-消费者模型中使用这些方法实现线程间的协调和同步。
21 3
|
6天前
|
安全 Java
Java多线程集合类
本文介绍了Java中线程安全的问题及解决方案。通过示例代码展示了使用`CopyOnWriteArrayList`、`CopyOnWriteArraySet`和`ConcurrentHashMap`来解决多线程环境下集合操作的线程安全问题。这些类通过不同的机制确保了线程安全,提高了并发性能。
|
7天前
|
Java
java小知识—进程和线程
进程 进程是程序的一次执行过程,是系统运行的基本单位,因此进程是动态的。系统运行一个程序即是一个进程从创建,运行到消亡的过程。简单来说,一个进程就是一个执行中的程序,它在计算机中一个指令接着一个指令地执行着,同时,每个进程还占有某些系统资源如CPU时间,内存空间,文件,文件,输入输出设备的使用权等等。换句话说,当程序在执行时,将会被操作系统载入内存中。 线程 线程,与进程相似,但线程是一个比进程更小的执行单位。一个进程在其执行的过程中产生多个线程。与进程不同的是同类的多个线程共享同一块内存空间和一组系统资源,所以系统在产生一个线程,或是在各个线程之间做切换工作时,负担要比
17 1
|
7天前
|
Java UED
Java中的多线程编程基础与实践
【10月更文挑战第35天】在Java的世界中,多线程是提升应用性能和响应性的利器。本文将深入浅出地介绍如何在Java中创建和管理线程,以及如何利用同步机制确保数据一致性。我们将从简单的“Hello, World!”线程示例出发,逐步探索线程池的高效使用,并讨论常见的多线程问题。无论你是Java新手还是希望深化理解,这篇文章都将为你打开多线程的大门。
|
8天前
|
安全 Java 编译器
Java多线程编程的陷阱与最佳实践####
【10月更文挑战第29天】 本文深入探讨了Java多线程编程中的常见陷阱,如竞态条件、死锁、内存一致性错误等,并通过实例分析揭示了这些陷阱的成因。同时,文章也分享了一系列最佳实践,包括使用volatile关键字、原子类、线程安全集合以及并发框架(如java.util.concurrent包下的工具类),帮助开发者有效避免多线程编程中的问题,提升应用的稳定性和性能。 ####
33 1
|
11天前
|
存储 设计模式 分布式计算
Java中的多线程编程:并发与并行的深度解析####
在当今软件开发领域,多线程编程已成为提升应用性能、响应速度及资源利用率的关键手段之一。本文将深入探讨Java平台上的多线程机制,从基础概念到高级应用,全面解析并发与并行编程的核心理念、实现方式及其在实际项目中的应用策略。不同于常规摘要的简洁概述,本文旨在通过详尽的技术剖析,为读者构建一个系统化的多线程知识框架,辅以生动实例,让抽象概念具体化,复杂问题简单化。 ####