Является ли Java 7 с помощью Tim Sort для массива методов. Сорт?

Ответ 1

Java 7 использует Double-Pivot Quicksort для примитивов и TimSort для объектов.

В соответствии с Java 7 API doc для примитивов:

Замечание по реализации: сортировка Алгоритм представляет собой двухпоточный ускоритель Владимир Ярославский, Джон Бентли, и Джошуа Блох. Этот алгоритм предлагает O (n log (n)) производительность на многих наборы данных, которые вызывают другие быстрые сортировки деградировать до квадратичной производительности, и, как правило, быстрее, чем традиционный (однопоточный) Quicksort реализации.

В соответствии с Java API API для объектов:

Реализация была адаптирована из Tim Peters сортирует список для Python ( TimSort). Он использует технику из Питера Макилрой "Оптимистическая сортировка и Информационная теоретическая сложность", в Материалы четвертой ежегодной Симпозиум ACM-SIAM по дискретному Алгоритмы, стр. 467-474, январь 1993 г.

Не уверен, что это сильно отличается от того, что было в Java 6:

настроенная быстродействующая сортировка, адаптированная из Jon L. Бентли и М. Дуглас Макилрой "Инжиниринг функции сортировки", Программное обеспечение-практика и опыт, Vol. 23 (11) P. 1249-1265 (ноябрь 1993 года)

Ответ 2

Да, Java 7 будет использовать Timsort для Arrays.sort. Вот фиксация: http://hg.openjdk.java.net/jdk7/jdk7/jdk/rev/bfd7abda8f79

Ответ 3

Да!... и также нет.

Резюме

В текущих реализациях Open JDK ⁰ Tim Sort обычно используется для сортировки массивов объектов (т.е. Arrays.sort(Object[]) и друзей), но для примитивных массивов (остальная часть методов Arrays.sort) используются различные методы, включая, но не ограничиваясь ими, Tim Sort. В этом случае эвристика используется для выбора метода сортировки для использования.

Для примитивов эвристики выбирают из множества методов сортировки в зависимости от сортируемых данных. Большинство из этих решений просто составлены на основе типа и размера отсортированного массива, но для элементов int и long это решение фактически адаптируется на основе измеренной сортировки массива. Таким образом, во многих случаях у вас есть адаптация/интроспекция (эвристика для выбора алгоритма) поверх адаптации/интроспекции (TimSort)!

Подробнее

Tim Sort используется для большинства видов объектов, таких как Arrays.sort(Object[] a), если только пользователь не запросил унаследованное поведение, установив системное свойство java.util.Arrays.useLegacyMergeSort в true.

Для примитивов ситуация более сложная. Начиная с JDK 8 (версия 1.8.0_111) в зависимости от размера отсортированных массивов, примитивного типа и измеренной "сортировки" массива используются различные эвристики. Вот обзор:

• Для всех примитивных типов, отличных от байтов ¹ массивы из менее чем 47 элементов просто сортируются с помощью сортировки вставки (см. DualPivotQuicksort.INSERTION_SORT_THRESHOLD). Этот порог также используется при сортировке подматриц, возникающих при использовании слияния или быстрой сортировки, и размер подмашины падает ниже порогового значения. Таким образом, некоторая форма сортировки вставки будет использоваться во всех родах, а для небольших массивов - единственный используемый алгоритм.
• Для примитивных типов byte, short и char для больших массивов используется счетная сортировка. Это простой вид, который занимает время O(n + range), где range - общее количество байтов (256) или коротких /char (65536) значений. Сорт включает выделение базового массива значений range, поэтому он используется только тогда, когда количество сортируемых элементов является значительной частью всего диапазона. В частности, он используется для байт-массивов более 29 элементов (т.е. ~ 11% от диапазона) и коротких /char массивов более 3200 элементов (~ 5% от диапазона).
• Для массивов байтов всегда используется один из двух подходов.
• Для массивов int и long выше порога сортировки вставки и для массивов short/char, как выше порога сортировки вставки, так и ниже порога сортировки подсчета, может использоваться один из двух алгоритмов: двойная ось сортировка quicksort или merge. Какой из них используется, зависит от меры сортировки массива: вход разделяется на прогоны восходящих или нисходящих элементов. Если число таких прогонов больше 66, то массив считается в основном несортированным и сортируется с помощью быстрой сортировки с двойным шарниром. В противном случае массив считается в основном отсортированным, и используется mergesort (используя уже перечисленные прогоны в качестве отправной точки).

Идея поиска прогонов, а затем использования mergesort для их сортировки на самом деле очень похожа на timsort, хотя есть некоторые отличия. Таким образом, по крайней мере для некоторых параметров JDK использует объединенный с запуском процесс объединения, но для многих других комбинаций параметров он использует другой алгоритм, и по крайней мере 4 различных алгоритма используются в общей сложности!

Обоснование

Обоснование разного поведения типа Object[] по сравнению с примитивным возможно, по крайней мере, в два раза:

1) Сорта Object[] должна быть стабильной: объекты, которые сортируются одинаково, будут отображаться в том же порядке, что и вход. Для примитивных массивов такого понятия не существует: примитивы полностью определяются их значением, поэтому нет различия между устойчивым и неустойчивым видом. Это позволяет примитивным сортам отказаться от необходимости стабильных алгоритмов в пользу скорости.

2) Сорта Object[] должна включать метод Object.compare(), который может быть сколь угодно сложным и дорогостоящим. Даже если метод compare() прост, обычно будет накладной вызов метода, если весь метод сортировки не может быть встроен ². Таким образом, типы Object[] будут, как правило, смещены в сторону минимизации общих сравнений, даже ценой некоторой дополнительной алгоритмической сложности.

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

⁰ По крайней мере, для версий между Java 7 и Java 9, и, конечно же, это также включает Oracle JDK, поскольку он основан на Open JDK. Вполне вероятно, что в других реализациях используется аналогичный подход, но я не проверял.

¹ Для байт-массивов порог сортировки вставки составляет 29 элементов, так как нижняя обрезка, над которой используется сортировка подсчета.

² Это кажется маловероятным, так как оно довольно велико.