Добавлен: 18.06.2023
Просмотров: 41
Скачиваний: 2
Таблица 2
Экспериментальное среднее время сортировки
Время Tc работы алгоритма C хорошо аппроксимируется выражением kcn log2n, где kc — коэффициент, зависящий от типа компьютера. Обозначим через g отношение Tp/Tc, где Tp — время пирамидальной сортировки. Значение g возрастает приблизительно от 1,6 до 4,5 для n = 108. Это свидетельствует о том, что время Tp растет быстрее, чем число операций, которое согласно теории определяется выражением kpn log2n, где kp — коэффициент, т.е. сказывается увеличение удельного времени доступа к данным. Значение g и темп его изменения зависят от размера записи R и типа компьютера, точнее, от параметров иерархической структуры его памяти. В любом случае существует область больших значений n, где время Tp в несколько раз больше Tc. Это утверждение справедливо для всех разновидностей пирамидальной сортировки.
Чтобы сравнить метод слияния и метод QuickSort, рассмотрим последние результаты их оптимизации. Под оптимизацией сортировки [4] обычно понимается приближение среднего числа сравнений ключей к теоретико-информационному пределу log2(n!). В [7] для сортировки был выведен нижний предел n + Hn – 2 среднего числа транспозиций записей — перемещений записей или обмена их местами (Hn — гармоническое число). Сокращение числа транспозиций также будем называть оптимизацией. Под всесторонней оптимизацией будем понимать уменьшение среднего числа как основных действий, так и массовых вспомогательных действий, для которых может быть известен теоретический минимум.
Метод QuickSort реализует разделение массива на внешне упорядоченные части (ВУЧ). Каждая запись может изменять положение лишь в рамках ВУЧ. Разделение можно изобразить деревом ВУЧ, узлы которого представляют ВУЧ, так как весь массив и каждая ВУЧ, содержащая более одной записи, разделяются на меньшие ВУЧ. В итоге, когда каждая ВУЧ содержит единственную запись, массив становится упорядоченным.
Исследованию и усовершенствованию метода QuickSort посвящено немало работ, остановимся на последних [2; 8; 12; 13]. В них по-разному реализуются две главные идеи:
а) отказ от разделения многочисленных малых ВУЧ (ведет к сильному сокращению множества вспомогательных действий);
б) улучшение формы дерева ВУЧ, выражающееся в уменьшении средней глубины листьев дерева.
Упорядочение малых ВУЧ выполняют алгоритмом вставки или иным алгоритмом. Длина внешнего пути [12] дерева ВУЧ определяет число сравнений ключей. В алгоритме, описанном в [12] и названном нами алгоритмом B, ВУЧ, как правило, разделяется на пять частей, дерево ВУЧ имеет меньшую длину внешнего пути, чем в алгоритме A, однако действия в алгоритме B сложнее, так как при разделении ВУЧ используются два опорных элемента. Средний выигрыш в числе сравнений приблизительно равен
2n ln n – (1,9n ln n – 2,46n) = 0,1n ln n + 2,46n
(для алгоритма A среднее число сравнений ключей равно 2n lnn). В [13] было показано, как этот выигрыш увеличить до значения 0,2n ln n (приблизительно). В алгоритме B среднее число транспозиций, примерно равное 0,6n ln n, существенно больше, чем в алгоритме A. Поэтому оптимизацию нельзя считать сбалансированной: уменьшение среднего числа сравнений ключей сопровождается ростом числа транспозиций сортируемых записей.
Алгоритм C предложен в МЭИ [2]. В нем упорядочение малых ВУЧ проводится специальными алгоритмами, названными решетками, а форма дерева ВУЧ улучшается благодаря равномерному разделению ВУЧ, что достигается использованием в качестве опорного значения медианы пяти записей, взятых из разделяемой ВУЧ. Идея не нова, медиана трех элементов используется в известных реализациях QuickSort. Получение медианы — это дополнительные издержки времени, лишние операции. Важно их сократить и хотя бы частично совместить с операциями по разделению ВУЧ. Это было достигнуто при построении алгоритма C применительно к медианам пяти элементов ВУЧ. Согласно [2] в алгоритме C среднее число K сравнений ключей с ростом n приближается к значению 1,62n ln n – 1,35n, т.е. по сравнению с алгоритмом A выигрыш составляет примерно 0,38n ln n + 1,35n. Среднее число транспозиций составляет не более 0,5n ln n, и реализованы они как перемещения записей, тогда как в алгоритме B используются более сложные операции — обмены записей местами. Поэтому время сортировки алгоритмом C при n = 106 существенно меньше времени алгоритма B (рис. 5).
Рис.5. Сравнение времени сортировки алгоритмов В и С
Итак, по характеристикам алгоритм C лучше алгоритмов A и B. Однако достигнутые результаты оптимизации метода QuickSort далеки от идеала: значение K заметно больше значения log2(n!) ≈ 1,44n (ln n – 1). Среднее число транспозиций записей относительно мало, но существенно больше нижнего предела n + Hn – 2. Дальнейшее сокращение числа основных действий метода QuickSort, по-видимому, не имеет хорошей перспективы. Найдем альтернативу лучшим реализациям метода QuickSort.
Метод слияния обычно используется для сортировки файлов записей и редко применяется для сортировки массивов, так как требует значительной дополнительной памяти и выполняет больше транспозиций, чем метод QuickSort. Сильными сторонами слияния являются стабильность времени сортировки и близость среднего числа сравнений к теоретическому минимуму. Так называемое t-арное слияние выполняет слияния t упорядоченных частей массива вплоть до получения единой части, т.е. упорядоченного массива. На рис. 6 для t = 3 показана схема слияния 30 упорядоченных частей (ими могут быть отдельные записи). На каждой фазе слияния (они обозначены штриховыми линиями) все сортируемые записи перемещаются в памяти. Число перемещений отдельно взятой записи равно числу фаз L = ┌logt(n/m)┐, где m — максимальное число записей в одной исходной части. При t = ┌n/m┐ каждая запись перемещается однажды. Итак, возможно рекордно малое число P перемещений записей. В дальнейшем будем исследовать процесс t-арного слияния при больших значениях t.
Сокращая числа перемещений записей P, важно сохранить указанные выше преимущества слияния. Массовая операция, во время которой сравниваются ключи, — это выбор очередной наименьшей записи из остающихся записей. Простой перебор при сравнении записей неприемлем, он сильно снижает производительность метода при больших t. Найдем лучший вариант.
Обозначим X вычислительную сложность одной фазы слияния и выясним, каким должна быть X, чтобы получить приемлемую оценку сложности O(n log2n) всего процесса слияния.
Выбирая эту оценку как ориентир, учитываем указанный выше теоретико-информационный предел и тот факт, что сравнения ключей являются самой массовой операцией при сортировке.
Возьмем m = 1 и запишем равенство X ┌logt n┐ = O(n log2 n). Из него следует X = O(n log2n/logtn) = O(n log2t), а сложность выбора одной записи, включая ее пересылку, получает оценку O(log2t). Такую оценку имеет выбор среди t ключей экстремального ключа, реализуемый в простой пирамиде [4]. Асимптотическая оценка O(log2t) скрывает коэффициент при величине log2t, но если он будет велик, нельзя ожидать преимущества метода слияния по сравнению с методом QuickSort.
Рис.6. Реализация метода многопутевого слияния
Авторами был выполнен анализ использования (в качестве схемы выбора) простой и слабой [9] бинарных пирамид, 3-арной, 4-арной и 5-арной пирамид. Прежде всего определялся коэффициент k в формуле klog2t числа сравнений при выборе записи. Наименьшее значение k
имеет слабая пирамида, для нее k ~ 1. Поскольку в ней выполняются и пересылки, и многочисленные вспомогательные операции, в целях сравнения проверялись улучшенные реализации прочих пирамид. По затратам времени выбора лучшими оказались слабая пирамида и простая бинарная пирамида, в которой для уменьшения числа сравнений использована идея Р. Флойда [10].
Время тратится и на построение пирамид, выполняемое примерно столько же раз, сколько узлов в схеме слияния (рис. 6), исключая листья дерева. Время построения 4-арной и 5-арной пирамид наименьшее, но эти пирамиды проигрывают бинарным пирамидам по общим затратам времени.
Таким образом, продолжена оптимизация t-арного слияния, начало которой было положено в [3]. В новых реализациях t-арного слияния помимо слабой пирамиды впервые используется схема выбора записей по принципу турнира.
Следующий шаг оптимизации — это выбор размера m исходных упорядоченных частей и способа их получения. Рассмотрим вариант, когда, неупорядоченный массив большой: пусть n = 107, m=1. Если t = 100, то потребуется упорядочить на 1-й фазе слияния 107/100 = 105 частей и для этого 105 раз построить схему выбора — пирамиду или турнирную схему, затратив больше времени. Для исключения такого рода фазы слияния описываемым ниже способом упорядочим части массива размером t (в последней части записей может быть меньше чем t). Для каждой части, сравнивая ключи, будем сортировать номера записей. Используя полученную последовательность номеров, переместим каждую запись (всего n пересылок записей, как и на исключенной фазе).
Были исследованы восемь способов упорядочения исходных частей. Алгоритмы естественного и простого бинарного слияния [4] оказались наилучшими по времени сортировки исходных частей. Для сокращения числа машинных операций была проведена оптимизация их программ. Для R = 48 среднее время сортировки одной части в условных единицах приведено в табл. 2. Оно зависит от размера записи R, но остается меньшим у алгоритмов слияния в рабочей области значений t. Например, для t = 1000 затрачивается примерно в 1,35 раза меньше времени, если взамен первой фазы применяется простое бинарное слияние.
Заключение
Как можно было убедиться, практическая польза от описанных алгоритмов есть, со своей задачей они с переменным успехом справляются. Абсолютным лидером стал Timsort — дающий заметное ускорение при увеличении степени упорядоченности данных и работающий на уровне Quicksort в обычных случах. Не зря он признан и встроен в Python, OpenJDK и Android JDK.
Про Smoothsort в сети довольно немного информации (по сравнению с остальными алгоритмами) и не спроста: из-за сложности идеи и спорной производительности он скорее является алгоритмическим изыском, нежели применимым методом. Я нашел всего лишь одно реальное применение этого алгоритма — в библиотеке sofia-sip, предназначенной для построения IM- и VoIP-приложений.
Появление Shellsort в данном тесте является довольно спорным моментом, потому что его асимптотическая сложность несколько больше, чем у остальных двух алгоритмов. Но у него есть два больших преимущества: простота идеи и алгоритма, которая позволяет почти всегда обходить Smoothsort по скорости работы и простота реализации — работающий код занимает всего пару десятков строк, в то время как хорошие реализации Timsort и Smoothsort требуют более сотни строк.
Список использованных источников
- Зубов В.С., Шевченко И.В. Об ускорении «быстрой сортировки» // Труды XXI международной НТК «Информационные средства и технологии». Т. 3. М.: Издательский дом МЭИ, 2013. С. 122—129.
- Зубов В.С., Шевченко И.В. Новый алгоритм сортировки по методу многопутевого слияния // Вестник МЭИ. 2014. № 6. С. 49—56.
- Кнут Д.Э. Искусство программирования. Т. 1. Основные алгоритмы: пер. с англ.; 3-е изд. — М.: Издательский дом «Вильямс», 2014. С. 449—451.
- Кнут Д.Э. Искусство программирования. Т. 3. Сортировка и поиск: пер. с англ.; 2-е изд. — М.: Издательский дом «Вильямс», 2014. – 832 с.
- Томас Х. Кормен, Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн. Алгоритмы: построение и анализ— 2-е изд. — М.: Вильямс, 2016. — С. 1296
- Седжвик Р. Фундаментальные алгоритмы на C. Анализ/Структуры данных/Сортировка/Поиск— СПб.: ДиаСофтЮП, 2003. — С. 672.
- Шевченко И.В. Композиции быстрых алгоритмов сортировки. Электронный журнал «Вычислительные сети. Теория и практика» / Network-Journal. Theory and practice BC/NW. 2005. № 1 (6). http://network-journal.mpei.ac.ru/cgi-bit/main.pl?l=ru&n=6&pa=3&ar=4
- Aumüller M., Dietzfelbinger M. Optimal Partitioning for Dual Pivot Quicksort. Automata, Languages and Programming // Lecture Notes in Computer Science. 2013. Vol. 7965. P. 33—44.
- Dutton R.D. Weak-heap Sort // BIT. 2013. Vol. 33. P. 372—381.
- Floyd R.W. Algorithm 245: treesort 3 // Comm. ACM. Vol. 7. No 12. P. 701.
- Magnus Lie Hetland. Python Algorithms: Mastering Basic Algorithms in the Python Language. — Apress, 2015. — 336 с.
- Yaroslavskiy V. Dual pivot quicksort. 2014. http://iaroslavski.narod.ru/quicksort/DualPivotQuicksort.pdf
- Wild S., Nebel M.E. Average case analisys of Java 7’s dual pivot quicksort. Algorithms — ESA 2012 // Lecture Notes in Computer Science. 2012. Vol. 7501. P. 825—836.