arrays.sort和arrays.parallelsort区别

codingman included in Java Collections

2020-04-12 871 words 2 minutes

Contents

1. 概述

我们都使用过*Arrays.sort()*对对象或基元数组进行排序。在 JDK 8 中，创建者增强了 API 以提供一种新方法：Arrays.parallelSort()。

在本教程中，我们将比较*sort()和parallelSort()*方法。

2. Arrays.sort()

*Arrays.sort()*方法对对象或基元数组进行排序。**此方法中使用的排序算法是 Dual-Pivot Quicksort 。**换句话说，它是快速排序算法的自定义实现，以实现更好的性能。 此方法是单线程的，有两种变体：

sort(array) – 将整个数组按升序排序
sort(array, fromIndex, toIndex) – 仅对从 fromIndex到toIndex的元素进行排序

让我们看一下这两种变体的示例：

@Test
public void givenArrayOfIntegers_whenUsingArraysSortMethod_thenSortFullArrayInAscendingOrder() {
    int[] array = { 10, 4, 6, 2, 1, 9, 7, 8, 3, 5 };
    int[] expected = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
    Arrays.sort(array);
    assertArrayEquals(expected, array);
}
@Test
public void givenArrayOfIntegers_whenUsingArraysSortWithRange_thenSortRangeOfArrayAsc() {
    int[] array = { 10, 4, 6, 2, 1, 9, 7, 8, 3, 5 };
    int[] expected = { 10, 4, 1, 2, 6, 7, 8, 9, 3, 5 };
    Arrays.sort(array, 2, 8);
    assertArrayEquals(expected, array);
}

让我们总结一下这种方法的优缺点：

优点	缺点
在较小的数据集上快速工作	大型数据集的性能下降
	未使用系统的多个核心

3. Arrays.parallelSort()

此方法还对对象或基元数组进行排序。与*sort()*类似，它也有两种变体来对完整数组和部分数组进行排序：

@Test
public void givenArrayOfIntegers_whenUsingArraysParallelSortMethod_thenSortFullArrayInAscendingOrder() {
    int[] array = { 10, 4, 6, 2, 1, 9, 7, 8, 3, 5 };
    int[] expected = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
    Arrays.parallelSort(array);
    assertArrayEquals(expected, array);
}
@Test
public void givenArrayOfIntegers_whenUsingArraysParallelSortWithRange_thenSortRangeOfArrayAsc() {
    int[] array = { 10, 4, 6, 2, 1, 9, 7, 8, 3, 5 };
    int[] expected = { 10, 4, 1, 2, 6, 7, 8, 9, 3, 5 };
    Arrays.parallelSort(array, 2, 8);
    assertArrayEquals(expected, array);
}

*parallelSort()在功能上有所不同。与sort()*使用单个线程按顺序对数据进行排序不同，它使用并行排序合并排序算法。它将数组分解为子数组，这些子数组本身已排序然后合并。

为了执行并行任务，它使用ForkJoin池。

但我们需要知道它只有在满足某些条件时才使用并行性。如果数组大小小于或等于 8192 或处理器只有一个内核，则它使用顺序 Dual-Pivot Quicksort 算法。否则，它使用并行排序。

让我们总结一下使用它的优点和缺点：

优点	缺点
为大型数据集提供更好的性能	较小的阵列速度较慢
利用系统的多个核心

4. 比较

现在让我们看看这两种方法如何处理不同大小的数据集。以下数字是使用JMH 基准测试得出的。测试环境使用AMD A10 PRO 2.1Ghz四核处理器和JDK 1.8.0_221：

数组大小	Arrays.sort()	Arrays.parallelSort()
1000	o.048	0.054
10000	0.847	0.425
100000	7.570	4.395
1000000	65.301	37.998