1. Обзор
В этом кратком руководстве мы сравним два Массива.сортировка(Объект[]) и Массивы.сортировка(int []) | сортировка операции .
Во-первых, мы опишем каждый метод отдельно. После этого мы напишем тесты производительности, чтобы измерить время их работы.
2. Массивы.сортировка(Объект[])
Прежде чем мы двинемся дальше, важно иметь в виду, что Arrays.sort() работает как для массивов примитивного, так и ссылочного типов.
Массивы.сортировка(Объект[]) принимает ссылочные типы .
Например, у нас есть массив Целых объектов:
Integer[] numbers = {5, 22, 10, 0};Для сортировки массива мы можем просто использовать:
Arrays.sort(numbers);
Теперь массив чисел содержит все свои элементы в порядке возрастания:
[0, 5, 10, 22]
Массивы.сортировка(Объект[]) основана на алгоритме TimSort, дающем нам временную сложность O(n log(n)) . Короче говоря, TimSort использует Сортировку вставки и Сортировку слияния алгоритмы. Однако он все еще медленнее по сравнению с другими алгоритмами сортировки, такими как некоторые реализации быстрой сортировки.
3. Массивы.сортировка(int[])
С другой стороны, Arrays.sort(int[]) работает с примитивными int массивами.
Аналогично, мы можем определить int[] массив примитивов:
int[] primitives = {5, 22, 10, 0};И отсортируйте его с помощью другой реализации Arrays.sort(int[]) . На этот раз, принимая массив примитивов:
Arrays.sort(primitives);
Результат этой операции ничем не будет отличаться от предыдущего примера. И элементы в массиве примитивы будут выглядеть так:
[0, 5, 10, 22]
Под капотом он использует алгоритм быстрой сортировки с двумя поворотами . Его внутренняя реализация из JDK 10, как правило, быстрее, чем традиционная быстрая сортировка с одним поворотом.
Этот алгоритм предлагает O(n log(n)) среднюю временную сложность . Это отличное среднее время сортировки для многих коллекций. Кроме того, он имеет то преимущество, что полностью находится на месте, поэтому не требует дополнительного хранения.
Хотя, в худшем случае, его временная сложность составляет O(n 2 ) .
4. Сравнение по Времени
Итак, какой алгоритм быстрее и почему? Давайте сначала займемся теорией, а затем проведем несколько конкретных тестов с помощью JMH.
4.1. Качественный Анализ
Массивы.сортировка(объект[]) обычно выполняется медленнее по сравнению с Массивы.сортировка(int[]) по нескольким разным причинам.
Во – первых, это разные алгоритмы. Быстрая сортировка часто быстрее, чем Timsort.
Во-вторых, как каждый метод сравнивает значения.
См., поскольку Массивы.сортировка(объект[]) необходимо сравнить один объект с другим, ему необходимо вызвать метод compareTo каждого элемента. По крайней мере, для этого требуется поиск метода и отправка вызова в стек в дополнение к любой операции сравнения на самом деле.
С другой стороны, Arrays.sort(int[]) может просто использовать примитивные операторы отношения , такие как < и > , которые являются инструкциями с одним байт-кодом.
4.2. Параметры JMH
Наконец, давайте выясним какой метод сортировки работает быстрее с фактическими данными . Для этого мы будем использовать инструмент JMH (Java Microbenchmark Жгут проводов) для написания наших контрольных тестов.
Итак, мы просто проведем здесь очень простой тест. Это не является исчерпывающим, но даст нам представление о том, как мы можем подойти к сравнению Arrays.sort(int[]) и Arrays.sort( Целое число[] ) методам сортировки.
В нашем контрольном классе мы будем использовать аннотации конфигурации:
@BenchmarkMode(Mode.AverageTime)
@OutputTimeUnit(TimeUnit.MILLISECONDS)
@Measurement(batchSize = 100000, iterations = 10)
@Warmup(batchSize = 100000, iterations = 10)
public class ArraySortBenchmark {
}Здесь мы хотим измерить среднее время для одной операции ( Режим.среднее время) и отображать наши результаты в миллисекундах ( Единица времени.МИЛЛИСЕКУНДЫ) . Кроме того, с помощью параметра 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};
}Давайте выберем Целочисленные[] числа и int [] |/примитивы массив примитивных элементов. Аннотация @State указывает, что переменные, объявленные в классе, не будут частью выполнения контрольных тестов. Однако затем мы можем использовать их в наших тестовых методах.
Теперь мы готовы добавить первый микро-бенчмарк для массивов.сортировка(Целое число[]) :
@Benchmark
public Integer[] benchmarkArraysIntegerSort(ArraySortBenchmark.Initialize state) {
Arrays.sort(state.numbers);
return state.numbers;
}Далее, для массивов.сортировка(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[]) метод выполняется лучше, чем Массивы.сортировка(Объект[]) в нашем тесте, вероятно, по ранее выявленным причинам.
И хотя цифры, по-видимому, подтверждают нашу теорию, хотя нам нужно было бы провести тестирование с большим разнообразием входных данных, чтобы получить лучшую идею.
Кроме того, имейте в виду, что цифры, которые мы приводим здесь, являются просто результатами тестирования JMH – поэтому мы всегда должны тестировать в рамках нашей собственной системы и среды выполнения.
4.5. Зачем Тогда Тимсорт?
Тогда, наверное, нам следует задать себе вопрос. Если QuickSort работает быстрее, почему бы не использовать его для обеих реализаций?
Видите ли, Быстрая сортировка не стабильна , поэтому мы не можем использовать ее для сортировки Объектов . В принципе, если два int s равны, не имеет значения, что их относительный порядок остается неизменным, так как один 2 ничем не отличается от другого 2. С объектами, однако, мы можем сортировать по одному атрибуту, а затем по другому, что делает важным начальный порядок.
5. Заключение
В этой статье мы сравнили два метода сортировки, доступных в Java: Arrays.sort(int[]) и Arrays.sort( Целое число[] ) . Кроме того, мы обсудили алгоритмы сортировки, используемые в их реализациях.
Наконец, с помощью контрольных тестов производительности мы показали примерное время выполнения каждого параметра сортировки |/.
Как обычно, полный код этой статьи доступен на GitHub .