Алгоритмы сортировки вставкой и слиянием - аномальные результаты по времени

Я пытаюсь получить время выполнения для двух алгоритмов сортировки в Java, сортировки вставки и слияния. Программа выполняет обе сортировки по несортированному списку ArrayList из 433 слов несколько раз и сохраняет время, затраченное на сортировку 100, 200, 300, 400 и 433 слов (весь массив), а затем выводит среднее время, затраченное на каждую из эти.

Я считаю, что мой код в порядке. Однако я сталкиваюсь со странной аномалией, и мне интересно, может ли кто-нибудь помочь мне понять.

Вот результаты, когда обе сортировки выполняются один раз: 1

Вот результаты, когда обе сортировки выполняются 10 000 раз: 2

Я считаю, что при запуске после того, как результаты ожидаются, сортировка вставкой выполняется быстрее для меньшего количества отсортированных элементов, но сортировка слиянием быстрее для большего количества и всего массива.

Однако при запуске 10 000 раз средние значения времени сильно отличаются, сортировка вставкой выполняется значительно быстрее для любого количества отсортированных элементов.

Как будто сортировка вставкой ускоряется с каждой итерацией, как это возможно?

Код для алгоритмов сортировки и метода, используемого для выполнения нескольких итераций указанных алгоритмов сортировки - в комментарии ниже

Спасибо за любую помощь, которую вы можете предоставить.


java algorithm mergesort insertion-sort
person J.Davies    schedule 24.04.2019    source источник
comment
Разве это не из-за спекулятивного исполнения?   -  person Abrikot    schedule 24.04.2019
comment
Вы должны включить важные части кода: методы сортировки и то, как вы сбрасываете или инициализируете массив после каждой сортировки. Обратите внимание, что, когда массив уже отсортирован, сортировка вставкой может быть очень простой.   -  person tucuxi    schedule 24.04.2019
comment
@tucuxi Вот pastebin двух алгоритмов и метода, используемого для выполнения нескольких итераций алгоритмов pastebin.com/6bdHBTAk В каждой итерации используется один и тот же массив без сортировки. Как видите, методы сортировки возвращают новый отсортированный массив, а не сортируют уже существующий массив.   -  person J.Davies    schedule 24.04.2019
comment
Сортировка вставкой - O (n ^ 2), а сортировка слиянием - O (nlog (n)). Сортировка слиянием использует n дополнительной памяти, для сортировки вставкой требуется только 1 дополнительная переменная. Сортировка слиянием обычно рекурсивная. Размер и скорость кэша также играют важную роль, как и скорость памяти. Разрешение часов составляет в лучшем случае 1 микросекунду с 10 микросекундами, типичными для ноутбуков. Методы Java для измерения времени в наносекундах не могут быть лучше, чем тактовая частота. Ваши массивы довольно малы, что способствует сортировке вставкой. Вам действительно нужно быть уверенным, что данные действительно случайны.   -  person Marichyasana    schedule 24.04.2019
comment
@Marichyasana Может ли это объяснить, почему результаты для одного выполнения обоих алгоритмов сортировки такие, как ожидалось, но не для многих? Несортированный массив идентичен для каждой итерации в обоих сортах, конечно, если результаты будут такими, как ожидалось для 1 итерации обоих сортов, результаты будут такими, как ожидалось, для 10 000 итераций, где тайминги просто суммируются и делятся на 10 000, чтобы найти среднее? Или вы верите, что я получу более точные результаты с большим массивом?   -  person J.Davies    schedule 24.04.2019
comment
Компилятор JIT компилирует части исходного кода Java по мере их появления. Вы можете узнать об этом в хорошей книге по алгоритмам, такой как «Алгоритмы 4-го издания» Роберта Седжвика из Принстона. Копия доступна на их веб-сайте.   -  person Marichyasana    schedule 24.04.2019
comment
Где код, который генерирует или считывает строки arrayylist? Ссылка на лучший пример сортировки слиянием сверху вниз. Вам нужно будет преобразовать это в java и строки (измените сравнения, чтобы использовать compareto).   -  person rcgldr    schedule 25.04.2019

Ответы (1)


arrow_upward
2
arrow_downward

Временная сложность этих алгоритмов хорошо известна: O (N 2) для сортировки вставкой и O (N.log (N)) для Сортировка слиянием.

Вот возможные причины вашего неожиданного наблюдения:

  • Набор данных из 400 строк не очень велик, качество реализации может быть важнее, чем сама сложность алгоритмов.

  • ваша реализация сортировки вставкой не очень эффективна, но, по крайней мере, она работает на месте, следовательно, с эффективной временной сложностью O (N 2). Тем не менее, вам следует удалить измерительный код, который выполняет каждые 100 элементов с нетривиальной сложностью.

  • ваша реализация сортировки слиянием довольно неэффективна: вы выделяете несколько динамических массивов по одному элементу за раз для каждой фазы разделения и слияния. Это занимает очень много времени и приводит к тому, что большое количество объектов выделяется и остается висящим почти сразу, чтобы сборщик мусора мог восстановить их с большими затратами.

  • Один вызов сортировки слиянием может работать лучше, чем сортировка вставкой, если время вообще имеет значение, но многие вызовы могут запускать сборщик мусора со значительными накладными расходами, хотя ваши тайминги не показывают доказательств этого, возможно, потому что 10000 итераций недостаточно.

  • Реальное объяснение на самом деле простое: поскольку ваша реализация сортировки вставкой сортирует набор данных на месте, он уже отсортирован для каждого последующего вызова, что является оптимальным случаем для сортировки вставкой с линейной сложностью.

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

person chqrlie    schedule 24.04.2019