并行排序

大家都知道什么是排序。有很多计算机算法出现来支持排序。一些著名的算法有快速排序、堆排序、归并排序等。

所有这些排序算法都是基于顺序排序的。这意味着单个线程用于执行完整的排序操作。然而，当需要处理大规模数据集（数十亿）时，顺序排序效率不高。这就是我们需要使用“并行排序”的地方。

Java 8的支持

从Java 8开始，集合API使用流实现了并行排序。

数组和列表是受益于并行排序的常见数据结构，并且它们直接开始支持它。然而，在Java 8之前，并行性不是直接支持的。

流和并行性

Java在Stream API中提供了并行性支持。例如，java.util.List有一个stream() 方法，它将支持并行性。您可以通过调用Stream.parallel()创建一个并行流。

List<String>list = new ArrayList<>();

list.add(“a”);

…..

list.stream().parallel()

Java在Stream API中提供了并行性支持。例如，java.util.List有一个stream() 

上面的代码将准备一个并行流以供进一步处理。类似地，数组也可以按此方式使用。我们可以通过数组创建并行流。

数组和并行排序

自Java 8起，有几种以并发方式对数组进行排序的方法。它们如下：

1. Arrays.parallelSort(array对象)
2. Arrays.stream(array对象).parallel().sorted()
3. Arrays.stream(array对象).parallel().sorted(Comparator.comparing(int ->{ ….}))

     类似地，还有一种对列表进行排序的方法。

1. list.stream().parallel().sorted()
2. list.stream().parallel().sorted(Comparator.comparing(int->{}))

然而，上述方法使用时存在一些差异。Arrays.parallelSort()和Arrays.stream(..).parallel().sorted()只能用于升序排序。但是Arrays.stream(..).parallel().sorted(Comparator.reverseOrder()) 可以用于对数组进行逆序排序。

并行排序是如何工作的？

parallelSort()方法采用分治法的方法，将数组分割成较小的单元，直到每个单元易于管理，然后逐个单独对其进行排序。然后，将这些较小的单元合并在一起，这整个操作并行进行。这种方法利用了多线程，使其更有效率和快速。

并行性值

默认情况下，当执行并行排序时，ForkJoinPool会创建一个默认的线程池。线程池的大小根据当前计算机上可用的CPU数量来确定。在大多数情况下，该值是足够的。然而，根据应用程序的需要，我们可以根据需要微调此值。在这种情况下，可以通过使用System.setProperty()方法将“java.util.concurrent.ForkJoinPool.common.parallelism”属性传递一个值来控制线程池的大小。

System.setProperty("java.util.concurrent.ForkJoinPool.common.parallelism", "10");

上面的代码将把并行性属性设置为10，ForkJoinPool框架将生成十个工作线程。您将在本文中了解到这种行为。

并行排序的基准测试

让我们开发一小段代码来演示并行排序的性能。

在这段代码中，我们将用1000万个条目填充一个列表，并在不使用并行性的情况下对其进行排序。 接下来，我们将使用并行性来对其进行排序并比较结果。

首先，使用顺序排序（不使用并行性）对列表进行排序。

排序列表使用顺序

此操作需要14389毫秒。

接下来，使用并行流对列表进行排序。

使用并行流进行列表排序

进行此操作的时间为3906毫秒。

这仅需顺序排序所需时间的一半。

这是因为并行排序利用了多个线程来进行排序操作，相比于顺序排序，它使用的是更高效的方式。请记住，在顺序排序的情况下，整个排序操作只使用一个线程。这是并行排序领先于顺序排序的主要差异。

注意：时间会在不同系统上有所不同。

JVM中发生了什么？

现在，我们将执行线程转储分析，以了解JVM内部发生了什么。这个过程将为您提供完成的线程图片，这些线程用于执行串行和并行操作。在并行排序的情况下，将使用更多线程。

我们将分析顺序和并行排序的线程转储，以找出这种区别。

顺序排序的线程转储分析

图：fastThread 工具突出显示32个可运行线程

上面是从顺序排序程序中捕获的线程转储分析报告。在上面的报告中，您可以看到有32个线程处于可运行状态。在顺序排序的情况下，Java未使用ForkJoinPool API。还请查看线程组部分。

查看完整报告。

并行排序中的线程转储

在并行性的情况下，Java使用ForkJoinPool API，它将通过一种称为“forking”的操作将任务分割成较小的块，并合并结果。这为复杂操作带来了大量的性能提升。在并行排序中，ForkJoinPool API在内部维护了一个线程池，这个线程池用于并行排序的情况。

但我们可以通过设置一个名为“java.util.concurrent.ForkJoinPool.common.parallelism”的系统属性来控制这个线程创建过程，这在文章的前一部分有提到。根据这个属性的值，ForkJoinPool API将生成尽可能多的线程。在上面的代码中，您可以看到该值为10，这意味着API将生成一个由十个工作线程组成的池。 

图：fastThread 工具突出显示42个可运行线程 

图：fastThread 工具突出显示新创建的‘ForkJoinPool.commonPool’ 

报告的线程组部分显示了ForkJoinPool API生成的工作线程数量。有十个线程处于可运行状态。您可以看到，在并行排序的情况下，与顺序排序的32个线程相比，使用了42个线程。

让我们简单介绍一下ForkJoinPool API。这个框架用于执行Java中的并行操作。这是Java进行并行操作时的默认实现。然而，这个API从Java 8开始可用。您可以从线程组图像中看到，它为这个操作生成了大约十个线程。 

报告的完整概述。

总结

并行性使代码更具可伸缩性和高效性。在上述并行排序的代码中，无需开发复杂的算法，它仍然能够达到相同的结果。这将消除为并行性开发复杂逻辑的开销。