Хабр Курсы для всех
РЕКЛАМА
Практикум, Хекслет, SkyPro, авторские курсы — собрали всех и попросили скидки. Осталось выбрать!
Хабр доступен 24/7 благодаря поддержке друзей
Комментарии 11
на собеседованиях джуниоров/интернов.
это вы лично с таким встречались?
наш переделанный пузырьковый алгоритм показывает не квадратичную сложность, а обычный logN
такое ощущение, что вы ошиблись, на сколько я вижу из кода, один проход по массиву в отсортированном случае ваш Bubble Sort все равно делает, т. е. O(N) сравнений.
который может обогнать штатные методы
а со штатными методами вы вроде ничего и не сравнивали, вы сравнивали с «самописным» Quick Sort, т. е. другими словами сравнивали один велосипед с другим. Причем один из велосипедов вы доработали напильником, а второй взяли как есть.
boolean validate()
{
for (int i=0; i < array.length; i++){
if (array[i] != sortedArray[i])
return false;
}
return true;
}
Array.equals?
Точно, O(n), ошибся.
Что же касается штатных методов — в штатной сортировке нет счетчиков проверок и перестановок. Но не проблема проверить и штатный.
Добавил следующий код:
Результат:
Учитывая, что штатный сортировщик, скорее всего оптимизирован с учетом работы java-машины, весьма неплохой результат обогнать его на декрементальном массиве с пятью случайными числами велосипедом, слепленным за пару дней новичком.
Если интересно, можно скопировать реализацию штатного сортировщика, добавить в него счетчики метрик, чтобы еще больше выровнять условия. Тем не менее, я осознаю что статья полезнее для новичков, чем для про, и количество добавлений в избранное меня радует.
Что же касается штатных методов — в штатной сортировке нет счетчиков проверок и перестановок. Но не проблема проверить и штатный.
Добавил следующий код:
public void javaQuickSort() {
timeAmount = System.nanoTime();
Arrays.sort(array);
timeAmount = System.nanoTime() - timeAmount;
}
Результат:
Bubble Classic, random array Compares: 50 005 000, Switches: 24 750 505, Time: 116 024 377
QuickSort, random array Compares: 436 415, Switches: 22 062, Time: 2 783 738
Bubble Advanced, random array Compares: 45 003 506, Switches: 10 067 942, Time: 58 992 210
Java sort, random array Compares: 0, Switches: 0, Time: 504 525
Bubble Classic, decremental array Compares: 50 005 000, Switches: 50 005 000, Time: 46 714 701
QuickSort, decremental array Compares: 153 632, Switches: 5 000, Time: 199 326
Bubble Advanced, decremental array Compares: 60 022 000, Switches: 30 003 000, Time: 44 974 788
Java sort, decremental array Compares: 0, Switches: 0, Time: 192 186
Bubble Classic, incremental array Compares: 50 005 000, Switches: 24 995, Time: 24 873 255
QuickSort, incremental array Compares: 219 964, Switches: 8 426, Time: 241 551
Bubble Advanced, incremental array Compares: 179 740, Switches: 24 981, Time: 126 364
Java sort, incremental array Compares: 0, Switches: 0, Time: 150 581
Учитывая, что штатный сортировщик, скорее всего оптимизирован с учетом работы java-машины, весьма неплохой результат обогнать его на декрементальном массиве с пятью случайными числами велосипедом, слепленным за пару дней новичком.
Если интересно, можно скопировать реализацию штатного сортировщика, добавить в него счетчики метрик, чтобы еще больше выровнять условия. Тем не менее, я осознаю что статья полезнее для новичков, чем для про, и количество добавлений в избранное меня радует.
весьма неплохой результат обогнать его на декрементальном массиве с пятью случайными числами велосипедом
Вы обогнали стандартную сортировку в очень-очень специфичном случае и при простом типе ключа для сравнения, причем разница минимальна, а во всех остальных тестах с треском провалились — мне кажется, что вы сильно переоцениваете результат.
Как я писал в самом начале — цель была не создать супер-пупер алгоритм.
Понятно же, что пузырьковая сортировка, остается квадратичной, и не способна обогнать тот же quicksort в принципе, а я хотел оставаться в рамках именно пузырьковой сортировки, но оптимизировать процесс.
Меня просто удивило, что в определенном случае, даже такой вариант обогнал штатную оптимизированную сортировку, о чем я и написал вывод, что в узкоспециализированном случае, велосипед может помочь.
Разница минимальна — вы не правы. Если убрать счетчики метрик, разница будет почти в два раза, и как я приводил пример, разница остается такой же на бОльшем массиве, то есть в случае практически отсортированного массива, алгоритм ведет себя не как квадратичный, а как O(n).
И еще раз — я совершенно не переоцениваю результат. Результатом является реализация простейших алгоритмов сортировки на java и туториал для новичков, о чем говорят метки и хабы, поэтому, пожалуйста принимайте это во внимание. Я всегда готов прислушаться к советам.
Понятно же, что пузырьковая сортировка, остается квадратичной, и не способна обогнать тот же quicksort в принципе, а я хотел оставаться в рамках именно пузырьковой сортировки, но оптимизировать процесс.
Меня просто удивило, что в определенном случае, даже такой вариант обогнал штатную оптимизированную сортировку, о чем я и написал вывод, что в узкоспециализированном случае, велосипед может помочь.
Разница минимальна — вы не правы. Если убрать счетчики метрик, разница будет почти в два раза, и как я приводил пример, разница остается такой же на бОльшем массиве, то есть в случае практически отсортированного массива, алгоритм ведет себя не как квадратичный, а как O(n).
И еще раз — я совершенно не переоцениваю результат. Результатом является реализация простейших алгоритмов сортировки на java и туториал для новичков, о чем говорят метки и хабы, поэтому, пожалуйста принимайте это во внимание. Я всегда готов прислушаться к советам.
Как я писал в самом начале — цель была не создать супер-пупер алгоритм.
Я ничего не говорил про алгоритм, я говорил про ваш вывод о «весьма неплохом результате».
Меня просто удивило, что в определенном случае, даже такой вариант обогнал штатную оптимизированную сортировку, о чем я и написал вывод, что в узкоспециализированном случае, велосипед может помочь.
Ваш случай уж слишком специализированный: 5 элементов в середине массива случайны — что-то уж слишком специфичное. Если бы вы хотя бы подвигали эти элементы по массиву, или меняли бы их число, было бы хотя бы примерно видно где «границы применимости», и тогда уже можно было бы удивляться каким-то результатам.
Если убрать счетчики метрик, разница будет почти в два раза,
Получается, что счетчики отнимают 40% времени вашего Advanced Buble Sort-а? Вот это уже интересный результат… Заглянул в ваш код, вы запускаете каждую сортировку один раз, это выглядит не очень честным сравнением для JVM. Я полагаю, что JVM для нахождения и оптимизации Hot Path-ов нужно какое-то время, т. е. более честно будет если вы сначала «прогреете» алгоритмы — на количество сравнений и перестановок это не повлияет, но может повлиять на на окружающий код (это только предположение, я не знаю наверняка). Кроме того можно получить и среднее время и разброс результатов.
И еще раз — я совершенно не переоцениваю результат.
весьма неплохой результат обогнать его на декрементальном массиве с пятью случайными числами велосипедом
Ну ок, я не буду настаивать.
> Получается, что счетчики отнимают 40% времени вашего Advanced Buble Sort-а? Вот это уже интересный результат…
Не совсем так.
Я сравнил время, которое затратил тот quicksort, который я нашел в инете и штатный javasort, после чего убрал счетчики из quicksort. Он ускорился почти в полтора раза. Следовательно счетчики, особенно в quicksort едят много. Вызов рекурсии я при этом не считал.
Что же по поводу случайных элементов в середине массива — в статье я же писал, что 10 элементов уже практически без выигрыша, что интуитивно понятно — алгоритм за один проход может раскидать три элемента. Значит 10 элементов это уже примерно 3-4 прохода. А где именно они находятся — не важно, все равно выполняется полный проход по всему массиву.
Не совсем так.
Я сравнил время, которое затратил тот quicksort, который я нашел в инете и штатный javasort, после чего убрал счетчики из quicksort. Он ускорился почти в полтора раза. Следовательно счетчики, особенно в quicksort едят много. Вызов рекурсии я при этом не считал.
Что же по поводу случайных элементов в середине массива — в статье я же писал, что 10 элементов уже практически без выигрыша, что интуитивно понятно — алгоритм за один проход может раскидать три элемента. Значит 10 элементов это уже примерно 3-4 прохода. А где именно они находятся — не важно, все равно выполняется полный проход по всему массиву.
Пожалуйста, не пишите бенчмарки с помощью System.nanoTime(), потому что они скорее всего будут неправильными, лучше возьмите JMH.
System.nanoTime() не неправильный, он не идеально точный, и если не помнить про кеширование и оптимизацию java машины, можно ошибиться. Но на простых вещах, например циклы и долгие рассчеты, когда разница в 10-20 милисекунд не играет разницы — он вполне приемлим, ибо встроить его в уже рабочий проект — легко.
JMH неудобен тем, что его сложно просто так взять и вставить в уже готовый проект.
Проще создать с нуля новый maven проект на JMH и специально под него переписать все, что нужно потестить, что я и сделал за несколько вечеров, пока ковырялся с JMH (кстати, официальная документация — не очень).
Добавил в исходники на гитхабе рабочий вариант с сортировкой рандомного массива, с десятью warm-up и 10 итерациями для замера.
Но результаты не отличаются от тех, что я получил раньше.
Тут замеры только для случайного массива — остальные не писал, было интересно вообще понять, будет ли с JMH другой результат, но нет — как и ранее, на рандомном массиве данных bubbleAdvanced примерно в два раза быстрее bubbleClassic, QuickSort и штатный JavaQuickSort практически мгновенны.
Кстати, штатный сортировщик в Java (Java 8) — это два метода. Сперва определяется размер массива, затем маленьких массивов используется quicksort, для больших mergesort.
JMH неудобен тем, что его сложно просто так взять и вставить в уже готовый проект.
Проще создать с нуля новый maven проект на JMH и специально под него переписать все, что нужно потестить, что я и сделал за несколько вечеров, пока ковырялся с JMH (кстати, официальная документация — не очень).
Добавил в исходники на гитхабе рабочий вариант с сортировкой рандомного массива, с десятью warm-up и 10 итерациями для замера.
Но результаты не отличаются от тех, что я получил раньше.
Benchmark Mode Cnt Score Error Units
MyBenchmark.emptySortProcedure avgt 10 0,464 ? 0,005 ms/op
MyBenchmark.sortBubbleAdvanced avgt 10 49,661 ? 0,395 ms/op
MyBenchmark.sortBubbleClassic avgt 10 96,772 ? 1,483 ms/op
MyBenchmark.sortJavaQuickSort avgt 10 0,689 ? 0,009 ms/op
MyBenchmark.sortQuickSort avgt 10 1,292 ? 0,014 ms/op
Тут замеры только для случайного массива — остальные не писал, было интересно вообще понять, будет ли с JMH другой результат, но нет — как и ранее, на рандомном массиве данных bubbleAdvanced примерно в два раза быстрее bubbleClassic, QuickSort и штатный JavaQuickSort практически мгновенны.
Кстати, штатный сортировщик в Java (Java 8) — это два метода. Сперва определяется размер массива, затем маленьких массивов используется quicksort, для больших mergesort.
Целый литературный рассказ. Похвально. Однако, я считаю, что кроме формального описания, описания на конкретном языке программирования, литературного, есть еще иной способ описания алгоритмов — как некоего набора шагов, которые способен понять даже ребёнок. Это можно сделать словами, графически, с помощью анимации и т.д. Я не знаю Java, но с ходу мне не понять особенностей реализации.
Википедия говорит, что для улучшения алгоритма пузырьковой сортировки достаточно добавить досрочный выход из внешнего цикла. Вдобавок эту задачу можно повесить на переменную, которая участвует в процесс обмена.
Пример: http://ru.vingrad.com/Sortirovka-puzyrkom-uluchshennaya-id56971ea2ae20150a56f985e1
Википедия говорит, что для улучшения алгоритма пузырьковой сортировки достаточно добавить досрочный выход из внешнего цикла. Вдобавок эту задачу можно повесить на переменную, которая участвует в процесс обмена.
Пример: http://ru.vingrad.com/Sortirovka-puzyrkom-uluchshennaya-id56971ea2ae20150a56f985e1
Так собственно досрочный выход я добавил чуть ли не первым делом.
Думаю, основное ускорение дало возможность идти сразу с двух сторон — сокращать недосортированную часть массива не только справа, но и слева за один проход.
Анимацию думаю еще добавить, и это могла бы быть отдельная статья. Но минусующие без комментариев меня демотивируют.
Думаю, основное ускорение дало возможность идти сразу с двух сторон — сокращать недосортированную часть массива не только справа, но и слева за один проход.
Анимацию думаю еще добавить, и это могла бы быть отдельная статья. Но минусующие без комментариев меня демотивируют.
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Еще один разбор пузырьковой сортировки