1. Обзор
В этом кратком руководстве мы сравним две операции сортировки Arrays.sort(Object[]) и Arrays.sort(int[]) .
Во-первых, мы опишем каждый метод отдельно. После этого мы напишем тесты производительности, чтобы измерить время их работы.
2. Массивы.sort(Объект[])
Прежде чем мы двинемся дальше, важно иметь в виду, что 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. Массивы.sort(int[])
С другой стороны, Arrays.sort(int[]) работает с примитивными массивами целых чисел.
Точно так же мы можем определить массив int[] примитивов:
int[] primitives = {5, 22, 10, 0};
И отсортируйте его с помощью другой реализации Arrays.sort(int[]) . На этот раз, принимая массив примитивов:
Arrays.sort(primitives);
Результат этой операции ничем не будет отличаться от предыдущего примера. И элементы в массиве примитивов будут выглядеть так:
[0, 5, 10, 22]
Под капотом используется алгоритм Dual-Pivot Quicksort . Его внутренняя реализация из JDK 10 обычно быстрее, чем традиционная быстрая сортировка с одним сводом.
Этот алгоритм предлагает O(n log(n)) среднюю временную сложность . Это отличное среднее время сортировки для многих коллекций. Более того, он имеет то преимущество, что находится полностью на месте, поэтому не требует дополнительного хранения.
Хотя в худшем случае его временная сложность составляет O(n 2 ) .
4. Сравнение времени
Итак, какой алгоритм быстрее и почему? Давайте сначала рассмотрим теорию, а затем проведем конкретные тесты с JMH.
4.1. Качественный анализ
Arrays.sort(Object[]) обычно медленнее по сравнению с Arrays.sort(int[]) по нескольким причинам.
Во-первых, это разные алгоритмы. QuickSort часто быстрее, чем Timsort.
Во-вторых, как каждый метод сравнивает значения.
Видите ли, поскольку Arrays.sort(Object[]) должен сравнивать один объект с другим, он должен вызывать метод compareTo каждого элемента. По крайней мере, это требует поиска метода и помещения вызова в стек в дополнение к тому, чем на самом деле является операция сравнения.
С другой стороны, Arrays.sort(int[]) может просто использовать примитивные реляционные операторы, такие как < и > , которые представляют собой инструкции с одним байт-кодом.
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 нестабилен , поэтому мы не можем использовать его для сортировки объектов . По сути, если два int равны, не имеет значения, что их относительный порядок остается прежним, поскольку один 2 ничем не отличается от другого 2. Однако с объектами мы можем сортировать по одному атрибуту, а затем по другому, что делает начальный порядок важным .
5. Вывод
В этой статье мы сравнили два метода сортировки, доступные в Java: Arrays.sort(int[]) и Arrays.sort( Integer[] ) . Кроме того, мы обсудили алгоритмы сортировки, используемые в их реализациях.
Наконец, с помощью эталонных тестов производительности мы показали примерное время работы каждого `` варианта сортировки.
Как обычно, полный код для этой статьи доступен на GitHub .