Алгоритм сортировки Java.util.ArrayList.sort()

Я смотрел исходный код метода sort() java.util.ArrayList на grepcode. Они, похоже, используют сортировку вставки на небольших массивах (размером < 7) и сортируют по объему на больших массивах. Мне просто интересно было ли это иметь большое значение, учитывая, что они используют сортировку вставки только для массивов размера < 7. Разница в рабочем времени вряд ли будет заметна на современных машинах.

Я прочитал это в Кормене:

Хотя сортировка слиянием выполняется в O (n * logn) в худшем случае, а сортировка вставки выполняется в наихудшем случае O (n * n), постоянные факторы в сортировке вставки могут сделать это быстрее на практике при небольших размерах проблем на многих машинах. Таким образом, имеет смысл оборвать листья рекурсии, используя сортировку вставки при сортировке слияния, когда подзадачи становятся достаточно маленькими.

Если бы я разработал алгоритм сортировки для некоторого компонента, который мне нужен, то я бы рассмотрел использование вставки-сортировки для больших размеров (возможно, до размера < 100) до того, как разница в времени выполнения по сравнению с сортировкой слияния станет очевидно.

Мой вопрос заключается в том, что представляет собой анализ, стоящий за размером < 7?

Ответ 1

Разница в рабочем времени вряд ли будет заметна на современных машинах.

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

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

P.S. Стоит отметить, что Java7 использует Timsort по умолчанию.

Ответ 2

http://en.wikipedia.org/wiki/Timsort

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

О номере 7:

"... Также видно, что галопирование выгодно только тогда, когда исходный элемент не является одним из первых семи элементов другого прогона. Это также приводит к тому, что MIN_GALLOP устанавливается на 7. Чтобы избежать недостатков галопирования mode, функции слияния регулируют значение min-gallop. Если элемент находится из рассматриваемого массива (то есть массив, который возвращал элементы последовательно на некоторое время), значение min-gallop уменьшается на 1. В противном случае значение увеличивается на единицу, что препятствует возврату в режим галопирования. Когда это делается, в случае случайных данных значение min-gallop становится настолько большим, что запись обратно в режим галопирования никогда не берет место.

В случае, когда используется merge-hi (то есть слияние выполняется справа налево), сканирование должно начинаться с правого конца данных, то есть последнего элемента. Галопинг с самого начала также дает требуемые результаты, но делает больше сравнений, чем требуется. Таким образом, алгоритм галопирования включает в себя использование переменной, которая дает индекс, при котором начинается галопирование. Таким образом, алгоритм может вводить галопирующий режим при любом индексе и продолжать его, как упоминалось выше, так как он проверяет следующий индекс, который смещается на 1, 3, 7,...., (2k - 1).. и так и от текущего индекса. В случае merge-hi смещения к индексу будут -1, -3, -7,.... "

Ответ 3

Я публикую это для людей, которые посещают эту тему в будущем и документируют мои собственные исследования. Я наткнулся на эту прекрасную ссылку в своих поисках, чтобы найти ответ на тайну выбора 7:

Тим Петерс описывает алгоритм

Вы должны прочитать раздел "Вычисление minrun".

Чтобы дать gist, minrun - это размер отсечки массива, ниже которого алгоритм должен начинать использовать сортировку вставки. Следовательно, мы всегда будем иметь отсортированные массивы размером "minrun" , на которых нам нужно будет запустить операцию слияния для сортировки всего массива.

В java.util.ArrayList.sort(), "minrun" выбрано равным 7, но, насколько я понимаю вышеприведенный документ, он распаковывает этот миф и показывает, что он должен быть близок к силам 2 и менее 256 и более 8. Котировка из документа:

В 256 стоимость передачи данных в двоичной вставке сортировки явно повреждена, а при 8 увеличивается количество вызовов функций явно. Здесь важна выбор мощности 2, так что слияния в конечном итоге прекрасно сбалансированы (см. Следующий раздел).

То, что я делаю, заключается в том, что "minrun" может быть любой мощностью 2 (или около мощности 2) менее 64, не мешая работе TimSort.