#java #algorithm #mergesort #insertion-sort
#java #алгоритм #сортировка слиянием #вставка-сортировка
Вопрос:
Я пытаюсь получить время выполнения для двух алгоритмов сортировки в Java, вставки и сортировки слиянием. Программа многократно выполняет обе сортировки в несортированном массиве из 433 слов и сохраняет время, затраченное на сортировку 100, 200, 300, 400 и 433 слов (всего массива), затем выводит среднее время, затраченное на каждое из них.
Я полагаю, что мой код в порядке. Тем не менее, я сталкиваюсь со странной аномалией, которую мне было интересно, может ли кто-нибудь помочь мне понять.
Вот результаты, когда обе сортировки выполняются один раз: 
Вот результаты, когда обе сортировки выполняются 10000 раз: 
При запуске один раз результаты, я полагаю, соответствуют ожиданиям, то есть сортировка вставки выполняется быстрее для меньшего количества отсортированных элементов, но сортировка слиянием выполняется быстрее для больших объемов и всего массива.
Однако, при запуске 10000 раз, средние временные интервалы сильно отклоняются, сортировка вставки выполняется значительно быстрее для всех отсортированных элементов.
Как будто сортировка вставки ускоряется с каждой итерацией, как это может быть возможно?
Код для обоих алгоритмов сортировки и метода, используемого для запуска нескольких итераций указанных алгоритмов сортировки — в комментарии ниже
Спасибо за любую помощь, которую вы можете предоставить.
Комментарии:
1. Не из-за спекулятивного выполнения ?
2. Вы должны включить важные фрагменты кода: методы сортировки и то, как вы сбрасываете или инициализируете массив после каждой сортировки. Обратите внимание, что, когда массив уже отсортирован, сортировка вставки может быть очень простой.
3. @tucuxi Вот пример двух алгоритмов и метода, используемого для запуска нескольких итераций алгоритмов pastebin.com/6bdHBTAk Массив, используемый на каждой итерации, является одним и тем же несортированным массивом. Как вы можете видеть, методы сортировки возвращают новый отсортированный массив, а не сортируют уже существующий массив.
4. Сортировка вставкой равна O (n ^ 2), а сортировка слиянием равна O(nlog (n)). Сортировка слиянием использует n дополнительной памяти, для сортировки вставкой требуется только 1 дополнительная переменная. Сортировка слиянием обычно рекурсивна. Размер и скорость кэша также играют важную роль, как и скорость памяти. Тактовое разрешение составляет в лучшем случае 1 микросекунду при 10 микросекундах, типичных для ноутбуков. Методы Java для синхронизации в наносекундах не могут работать лучше, чем тактовая частота. Ваши массивы довольно малы, что благоприятствует сортировке вставки. Вам действительно нужно быть уверенным, что данные действительно случайны.
5. @Marichyasana Объясняет ли это, почему результаты для одного выполнения обоих алгоритмов сортировки соответствуют ожиданиям, но не для многих? Несортированный массив идентичен для каждой итерации в обоих видах, конечно, если результаты соответствуют ожидаемым для 1 итерации обоих видов, результаты будут такими, как ожидалось для 10 000 итераций, где тайминги просто суммируются и делятся на 10 000, чтобы найти среднее значение? Или вы верите, что я получу более точные результаты с большим массивом?
Ответ №1:
Временная сложность этих алгоритмов хорошо известна: O (N2) для сортировки вставкой и O (N.log (N)) для сортировки слиянием.
Вот возможные причины вашего неожиданного наблюдения:
-
Набор данных из 400 строк не очень большой, качество реализации может быть важнее, чем сама сложность алгоритмов.
-
ваша реализация сортировки вставкой не очень эффективна, но, по крайней мере, она работает на месте, следовательно, с эффективной временной сложностью O (N2). Тем не менее, вы должны удалить код измерения, который выполняет каждые 100 элементов с нетривиальной сложностью.
-
ваша реализация сортировки слиянием довольно неэффективна: вы выделяете несколько динамических массивов по одному элементу за раз для каждой фазы разделения и слияния. Это отнимает много времени и приводит к выделению большого количества объектов, которые почти сразу же остаются зависшими, чтобы сборщик мусора мог их восстановить с большими затратами.
-
Один вызов для сортировки слиянием может работать лучше, чем сортировка вставкой, если время вообще имеет смысл, но многие вызовы могут запускать сборщик мусора со значительными накладными расходами, хотя ваши тайминги не показывают доказательств этого, возможно, потому, что 10000 итераций недостаточно.
-
Реальное объяснение на самом деле простое: поскольку ваша реализация сортировки вставки сортирует набор данных на месте, он уже отсортирован для каждого последующего вызова, что является оптимальным случаем для сортировки вставки с линейной сложностью.
Вы должны отсортировать копии исходного набора данных для более значимого теста. А также ищите лучшую реализацию сортировки слиянием, которая использует один временный массив и сортирует элементы на месте и избегает динамических массивов, когда размер известен заранее.