«1. Обзор

В этом кратком руководстве мы сравним две операции сортировки Arrays.sort(Object[]) и Arrays.sort(int[]).

Сначала опишем каждый метод отдельно. После этого мы напишем тесты производительности, чтобы измерить время их работы.

2. Arrays.sort(Object[])

Прежде чем мы двинемся дальше, важно иметь в виду, что Arrays.sort() работает как для примитивных, так и для ссылочных массивов.

Arrays.sort(Object[]) принимает ссылочные типы.

Например, у нас есть массив объектов Integer: 

Integer[] numbers = {5, 22, 10, 0};

Чтобы отсортировать массив, мы можем просто использовать: 

Arrays.sort(numbers);

Теперь массив чисел содержит все элементы в порядке возрастания: ~ ~~ 

[0, 5, 10, 22]

Arrays.sort(Object[]) основан на алгоритме TimSort, что дает нам временную сложность O(n log(n)). Короче говоря, TimSort использует алгоритмы сортировки вставками и сортировки слиянием. Однако он по-прежнему медленнее по сравнению с другими алгоритмами сортировки, такими как некоторые реализации QuickSort.

3. Arrays.sort(int[])

С другой стороны, Arrays.sort(int[]) работает с примитивными массивами целых чисел.

Точно так же мы можем определить массив примитивов int[]: 

int[] primitives = {5, 22, 10, 0};

И отсортировать его с помощью другой реализации Arrays.sort(int[]). На этот раз, приняв массив примитивов: 

Arrays.sort(primitives);

Результат этой операции ничем не будет отличаться от предыдущего примера. И элементы в массиве примитивов будут выглядеть так: 

[0, 5, 10, 22]

Под капотом он использует алгоритм быстрой сортировки Dual-Pivot. Его внутренняя реализация из JDK 10 обычно быстрее, чем традиционная быстрая сортировка с одним сводом.

Этот алгоритм предлагает O(n log(n)) среднюю временную сложность. Это отличное среднее время сортировки для многих коллекций. Более того, он имеет то преимущество, что находится полностью на месте, поэтому не требует дополнительного хранения.

Хотя в худшем случае его временная сложность равна O(n2).

4. Сравнение времени

Итак, какой алгоритм быстрее и почему? Давайте сначала рассмотрим теорию, а затем проведем конкретные тесты с JMH.

4.1. Качественный анализ

Arrays.sort(Object[]) обычно медленнее по сравнению с Arrays.sort(int[]) по нескольким причинам.

Во-первых, это разные алгоритмы. QuickSort часто быстрее, чем Timsort.

Во-вторых, как каждый метод сравнивает значения.

Видите ли, поскольку Arrays.sort(Object[]) должен сравнивать один объект с другим, он должен вызывать метод compareTo каждого элемента. По крайней мере, это требует поиска метода и помещения вызова в стек в дополнение к тому, чем на самом деле является операция сравнения.

С другой стороны, Arrays.sort(int[]) может просто использовать примитивные реляционные операторы, такие как \u003c и \u003e, которые представляют собой инструкции с одним байт-кодом.

4.2. Параметры JMH

Наконец, давайте выясним, какой метод сортировки работает быстрее с фактическими данными. Для этого мы будем использовать инструмент JMH (Java Microbenchmark Harness) для написания тестов производительности.

Итак, мы проведем очень простой тест. Он не исчерпывающий, но даст нам представление о том, как мы можем подойти к сравнению методов сортировки Arrays.sort(int[]) и Arrays.sort(Integer[]).

В нашем тестовом классе мы будем использовать аннотации конфигурации: 

@BenchmarkMode(Mode.AverageTime)
@OutputTimeUnit(TimeUnit.MILLISECONDS)
@Measurement(batchSize = 100000, iterations = 10)
@Warmup(batchSize = 100000, iterations = 10)
public class ArraySortBenchmark {
}

Здесь мы хотим измерить среднее время для одной операции (Mode.AverageTime) и отобразить наши результаты в миллисекундах (TimeUnit.MILLISECONDS). Кроме того, с помощью параметра batchSize мы говорим JMH выполнить 100 000 итераций, чтобы убедиться, что наши результаты имеют высокую точность.

4.3. Сравнительные тесты

Перед запуском тестов нам нужно определить контейнеры данных, которые мы хотим отсортировать: 

@State(Scope.Thread)
public static class Initialize {
    Integer[] numbers = {-769214442, -1283881723, 1504158300, -1260321086, -1800976432, 1278262737, 
      1863224321, 1895424914, 2062768552, -1051922993, 751605209, -1500919212, 2094856518, 
      -1014488489, -931226326, -1677121986, -2080561705, 562424208, -1233745158, 41308167 };
    int[] primitives = {-769214442, -1283881723, 1504158300, -1260321086, -1800976432, 1278262737, 
      1863224321, 1895424914, 2062768552, -1051922993, 751605209, -1500919212, 2094856518, 
      -1014488489, -931226326, -1677121986, -2080561705, 562424208, -1233745158, 41308167};
}

Давайте выберем числа Integer[] и массив примитивных элементов int[] примитивов. Аннотация @State указывает, что переменные, объявленные в классе, не будут участвовать в выполнении эталонных тестов. Однако затем мы можем использовать их в наших методах тестирования.

Теперь мы готовы добавить первый микротест для Arrays.sort(Integer[]): 

@Benchmark
public Integer[] benchmarkArraysIntegerSort(ArraySortBenchmark.Initialize state) {
    Arrays.sort(state.numbers);
    return state.numbers;
}

Далее, для Arrays.sort(int[]): 

@Benchmark
public int[] benchmarkArraysIntSort(ArraySortBenchmark.Initialize state) {
    Arrays.sort(state.primitives);
    return state.primitives;
}

4.4. Результаты теста

«Наконец, мы запускаем наши тесты и сравниваем результаты: 

Benchmark                   Mode  Cnt  Score   Error  Units
benchmarkArraysIntSort      avgt   10  1.095 ± 0.022  ms/op
benchmarkArraysIntegerSort  avgt   10  3.858 ± 0.060  ms/op

Из результатов видно, что метод Arrays.sort(int[]) работает лучше, чем Arrays.sort(Object[]) в нашем тесте, вероятно, по ранее выявленным нами причинам.

И хотя цифры, кажется, подтверждают нашу теорию, хотя нам нужно провести тестирование с большим разнообразием входных данных, чтобы получить лучшее представление.

Кроме того, имейте в виду, что цифры, которые мы приводим здесь, являются просто результатами тестов JMH, поэтому мы всегда должны тестировать в рамках нашей собственной системы и среды выполнения.

4.5. Почему тогда Тимсорт?

Тогда нам, вероятно, следует задать себе вопрос. Если QuickSort работает быстрее, почему бы не использовать его для обеих реализаций?

Видите ли, QuickSort нестабилен, поэтому мы не можем использовать его для сортировки объектов. По сути, если два целых числа равны, не имеет значения, что их относительный порядок остается прежним, поскольку одно 2 ничем не отличается от другого 2. Однако с объектами мы можем сортировать по одному атрибуту, а затем по другому, что делает начальный порядок важным.

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

В этой статье мы сравнили два метода сортировки, доступные в Java: Arrays.sort(int[]) и Arrays.sort(Integer[]). Кроме того, мы обсудили алгоритмы сортировки, используемые в их реализациях.

Наконец, с помощью эталонных тестов производительности мы показали примерное время работы каждого варианта сортировки.

Как обычно, полный код этой статьи доступен на GitHub.