Сравнение на времето на Arrays.sort (Object) и Arrays.sort (int)

1. Общ преглед

В този кратък урок, ние ще се сравняват двете Arrays.sort (Object []) и (инт []) Arrays.sort сортиране операции .

Първо ще опишем всеки метод поотделно. След това ще напишем тестове за производителност, за да измерим времето им на работа.

2. Arrays.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 използва алгоритмите Insertion sort и MergeSort. Въпреки това, той все още е по-бавен в сравнение с други алгоритми за сортиране като някои от внедренията QuickSort.

3. Arrays.sort (int [])

От друга страна, Arrays.sort (int []) работи с примитивни масиви int .

По същия начин можем да дефинираме масив int [] от примитиви:

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

И го сортирайте с друго изпълнение на Arrays.sort (int []) . Този път приемаме масив от примитиви:

Arrays.sort(primitives);

Резултатът от тази операция няма да се различава от предишния пример. И елементите в примитивния масив ще изглеждат така:

[0, 5, 10, 22]

Под капака той използва алгоритъм за двойно завъртане Quicksort. Вътрешното му внедряване от JDK 10 обикновено е по-бързо от традиционната едноосева Quicksort.

Този алгоритъм предлага 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 []) може просто да използва примитивни релационни оператори като < и > , които са инструкции за единичен байт код.

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}; }

Нека да избират [] цели числа и 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. Защо Timsort тогава?

We should probably ask ourselves a question, then. If QuickSort is faster, why not use it for both implementations?

See, QuickSort isn't stable, so we can't use it to sort Objects. Basically, if two ints are equal, it doesn't matter that their relative order stays the same since one 2 is no different from another 2. With objects though, we can sort by one attribute and then another, making the starting order matter.

5. Conclusion

В тази статия сравнихме два метода за сортиране, налични в Java: Arrays.sort (int []) и Arrays.sort ( Integer [] ) . Освен това обсъдихме алгоритмите за сортиране, използвани в техните реализации.

И накрая, с помощта на бенчмарк тестове за ефективност, показахме примерно време за изпълнение на всекиопция за сортиране.

Както обикновено, пълният код за тази статия е достъпен в GitHub.