«Arrays.sort против Arrays.parallelSort»

«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. В противном случае используется параллельная сортировка.

Давайте обобщим преимущества и недостатки его использования:

4. Сравнение

Давайте теперь посмотрим, как оба метода работают с наборами данных разного размера. Приведенные ниже цифры получены с использованием сравнительного анализа JMH. В тестовой среде используется четырехъядерный процессор AMD A10 PRO 2,1 ГГц и JDK 1.8.0_221:

5. Заключение

В этой быстрой статье мы увидели, чем отличаются функции sort() и parallelSort().

Основываясь на результатах производительности, мы можем сделать вывод, что parallelSort() может быть лучшим выбором, когда у нас есть большой набор данных для сортировки. Однако в случае массивов меньшего размера лучше использовать sort(), так как он обеспечивает лучшую производительность.

Как всегда, полный исходный код доступен на GitHub.