Сравнение двух методов сортировок

Решен

Решил сравнить эффективность двух методов (код по ссылке https://ideone.com/P1pnei а результат ниже). Увидев, что первый метод сортирует массив (в данном случае) за 37 перестановок, а второй за 108, то подумал, что все очевидно, но решил еще посмотреть сколько времени занимает сортировка каждого. И тут все было уже совсем наоборот... Отсюда и мой вопрос: Это оператор сравнения так влияет на результат или весь алгоритм?

Результат:
-6 -19 -18 1 -17 -18 -13 -8 -15 -7 -12 -17 12 3 9 -11 -11 16 -2 15 -11 -7 -19 -6 -9
-19 -19 -18 -18 -17 -17 -15 -13 -12 -11 -11 -11 -9 -8 -7 -7 -6 -6 -2 1 3 9 12 15 16
count = 37
First sort was running: 20700 milliseconds

-6 -19 -18 1 -17 -18 -13 -8 -15 -7 -12 -17 12 3 9 -11 -11 16 -2 15 -11 -7 -19 -6 -9
-19 -19 -18 -18 -17 -17 -15 -13 -12 -11 -11 -11 -9 -8 -7 -7 -6 -6 -2 1 3 9 12 15 16
count = 108
Second sort was running: 8600 milliseconds

Возможно это неправильное сравнение и все нужно делать как то по другому, но пока как умею

Комментарии (4)

популярные
новые
старые

Для того, чтобы оставить комментарий Вы должны авторизоваться

Justinian Judge в Mega City One

Master

31 декабря 2019, 04:43

У меня код по ссылке отработал за идентичное время с небольшой погрешностью меньше 1%. При разборе алгоритмов сортировки ты должен смотреть прежде всего на количество итераций, которые необходимы для достижения результата - отсортированной последовательности. Во вторую очередь на количество операций, но ты должен понимать что операции отличаются по ресурсоемкости. Замерять время..если кратко, и не давать ссылку на доклад Шипилева на 90 страницах, вспомни первые уровни джава раш и что там говорилось про JVM. JVM это такая шайтан машина, которая под капотом проделывает огромнейшую работу по изменению кода, оптимизации, производительности и тд. Ты не можешь просто так оценивать скорость работы через вот такие таймеры. Приведу пример, твой код я запускал много раз на разных значениях, в подавляющем большинстве случаев были идентичные результаты с погрешностью менее 1%. А в одном случае, код выдал двукратную разницу! То есть я задал число элементов. И запустил код три раза. Дважды получил одинаковый результат, а на третий раз получил результат, который отличался в два раза. И что об этом говорить? Чтобы говорить о скорости алгоритмов путем замера времени ты должен хорошо разбираться в процессорах, кешах, регистрах, операционных системах, и естественно хорошо понимать модель памяти Джава, устройство JVM, алгоритмы которые там используются, и чем одна jvm машина отличается от другой. Ну сам посуди, в приведенном тобой коде, есть ошибочка. В 1_000_000 раз искажается результат. В миллион раз. О чем можно говорить? Наносекунды с миллисекундами перепутаны.. Подобные замеры, это все-равно что замер твердости материала делать. Какая кукла Маша или кукла Наташа крепче. Для этого мы берем эту куклу, помещаем в гаубицу и артиллерийским снарядом стреляем. И в замедленной съемке смотрим, а какая же кукла раньше уничтожится. В твоем случае, кукла это небольшой массив. Гаубица это мощный процессор с миллионами транзисторов работающий со скоростью света.

Justinian Judge в Mega City One

Master

31 декабря 2019, 04:46

Скорость для себя и для фана замерить так можешь конечно, но с пониманием того что это не даст тебе много, если ты не знаешь как это все устроено внутри. Но если и проверять то только на больших числах, чтобы хоть не куклу в гаубицу бросать (массивы небольшие), а что-то покрупнее и потверже (массивы размерностью 5000, 10000, 50000 элементов). Там JVM все-равно оптимизацию будет делать, но хоть что-то может быть похоже на реальнсть. При изучении алгоритмов сортировки изучай количество переборов, итераций, перестановок, да и есть книги по алгоритмам и статьи, там все рассказано. А там джаву подучишь, сможешь уже использовать профессиональные подходы к определению производительности и скорости работы с алгоритмами.

Badger

Уровень 22

Expert

31 декабря 2019, 09:10

Спасибо за объяснение. На моей машине 2 метода отрабатывали все запуски с почти всегда 2х кратной разницей во времен (иногда чуть меньше, иногда чуть больше), но с такой маленькой разницей замеров небыло, по этому и был создан пост. Но скорее это было для фана, потому, что пока я не знаю как это правильно делать. А по поводу миллисекунд и наносекунд - забыл исправить просто. Я сначала пытался использовать System.currentTimeMillis(), который показал ноль, после этого прикрутил nanoTime(), оставив миллисекунды в описании.

Justinian Judge в Mega City One

Master

31 декабря 2019, 09:14

На 20 уровне будет задача числа армстронга. Вот там ты и оторвешься, там будет и замер времени исполнения алгоритма, и будет ощущаться каждое нерациональное использование алгоритма :) А пока концентрируйся на других вещах. При разборе алгоритмов сортировки обращай внимание на суть, ну и можешь разобрать тему сложность алгоритмов. На собеседовании почти наверняка будут спрашивать.