编程时，我们经常需要对数组进行排序。为此，我们使用Java在Arrays类中提供的内置方法，即sort（）。sort（）方法使用merge sort或Tim sort对数组元素进行排序。在这两种情况下，sort（）方法都会对数组的元素进行顺序排序。 在Java8中，为排序引入了一个新的API，即并行排序。
并行排序使用 分支/聚合活动 Java 7中引入的框架，用于将排序任务分配给线程池中可用的多个线程。Fork/Join实现了 工作窃取算法 在空闲线程中，可以窃取在另一个线程中排队的任务。
例如，下面的代码是一个程序，它使用 数组。排序（） 和 数组。并行排序（） .本程序仅测量这两种方法之间的性能差异：
// Java program to demonstrate time taken by sort() // and parallelSort() methods. import java.util.Arrays; public class ParallelSortTest { private static final int BASE_ARRAY_SIZE = 10000 ; // A utility function to generate and return an // an array of given size filled with randomly // generated elements. public static double [] generateArray( int size) { if (size <= 0 || size > Integer.MAX_VALUE) return null ; double [] result = new double [size]; for ( int i = 0 ; i < size; i++) result[i] = Math.random(); return result; } // Driver code to compare two sortings public static void main(String[] args) { for ( int i = 1 ; i < 10000 ; i *= 10 ) { int size = BASE_ARRAY_SIZE * i; double [] arr1 = generateArray(size); // Creating a copy of arr1 so that we can // use same content for both sortings. double [] arr2 = Arrays.copyOf(arr1, arr1.length); System.out.println( "Array Size: " + size); // Sorting arr1[] using serial sort long startTime = System.currentTimeMillis(); Arrays.sort(arr1); long endTime = System.currentTimeMillis(); System.out.println( "Time take in serial: " + (endTime - startTime) + "ms." ); // Sorting arr2[] using serial sort startTime = System.currentTimeMillis(); Arrays.parallelSort(arr2); endTime = System.currentTimeMillis(); System.out.println( "Time take in parallel: " + (endTime - startTime) + "ms." ); System.out.println(); } } } |
环境：
2.6 GHz Intel Core i7 java version "1.8.0_25"
注： 由于数组中的随机值，所需时间可能会有所不同。
这两种算法的主要区别如下：
1) 数组。排序（） ：是一种顺序排序。
- API使用单线程进行操作。
- 执行该操作需要更长的时间。
2. 数组。ParallelSort（）： 是一种并行排序。
- API使用多个线程进行操作。
- 当元素较多时，速度较快，而元素较少时速度较慢。
分析： 结果表明，在多核机器上进行并行排序可以在100万个或更多元素的情况下实现性能改进。虽然低于此阈值，但实际上可能比顺序排序慢。这个结果符合预期，合适的规模可能是100万。你的里程可能会有所不同，这取决于你的环境。
说明： 现在，让我们看一下代码，以了解这种并行排序是如何工作的。
public static void parallelSort(double[] a) {
int n = a.length, p, g;
if (n <= MIN_ARRAY_SORT_GRAN ||
(p = ForkJoinPool.getCommonPoolParallelism()) == 1)
DualPivotQuicksort.sort(a, 0, n - 1, null, 0, 0);
else
new ArraysParallelSortHelpers.FJDouble.Sorter
(null, a, new double[n], 0, n, 0,
((g = n / (p << 2)) <= MIN_ARRAY_SORT_GRAN) ?
MIN_ARRAY_SORT_GRAN : g).invoke();
}
正如我们所见，存在最小粒度（java.util.Arrays.MIN_ARRAY_SORT_GRAN=8192[0x2000]），如果数组长度小于最小粒度，则使用DualPivotQuicksort对其进行排序。直接排序，而不是排序任务分区。通常，使用较小的大小会导致任务之间的内存争用，从而不太可能实现并行加速。 另一个值得注意的问题是ForkJoinPool。getCommonPoolParallelism（）返回公共池的目标并行级别（默认情况下，等于Runtime.getRuntime（）中可用处理器的数量）。可用的处理器（）。如果你的机器只有一个工作线程，它也不会使用并行任务。 当数组长度达到最小粒度，并且有超过1个工作线程时，将使用 并行排序法 .这里使用ForkJoin公共池来执行并行任务。
参考： http://download.java.net/lambda/b84/docs/api/java/util/Arrays.html#parallelSort%28int
本文由 萨乌米娅·米什拉 .如果你喜欢GeekSforgek，并想贡献自己的力量，你也可以使用 贡献极客。组织 或者把你的文章寄到contribute@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上，并帮助其他极客。
如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
