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

1. Обзор

Мы все использовали Arrays.sort() для сортировки массива объектов или примитивов. В JDK 8 создатели расширили API, предоставив новый метод: Arrays.parallelSort() .

В этом уроке мы проведем сравнение между методами sort() и parallelSort() .

2. Массивы.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. Массивы.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() , которая сортирует данные последовательно с помощью одного потока, она использует параллельный алгоритм сортировки sort-merge . Он разбивает массив на подмассивы, которые сами сортируются, а затем объединяются.

Для выполнения параллельных задач используется пул ForkJoin .

Но нам нужно знать, что он использует параллелизм только при соблюдении определенных условий. Если размер массива меньше или равен 8192 или процессор имеет только одно ядро, то используется последовательный алгоритм быстрой сортировки Dual-Pivot. В противном случае используется параллельная сортировка.

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

   | ПЛЮСЫ    | МИНУСЫ   | 
  | Предлагает лучшую производительность для наборов данных большого размера    | Медленнее для массивов меньшего размера   | 
  | Использует несколько ядер системы    |    | 

4. Сравнение

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

   | Размер массива    | `Массивы.sort()`    | `Массивы.parallelSort()`   | 
  | 1000    | о.048    | 0,054   | 
  | 10000    | 0,847    | 0,425   | 
  | 100000    | 7.570    | 4.395   | 
  | 1000000    | 65.301    | 37.998   | 

5. Вывод

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

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

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