Спред-сортировка
 | В этой статье есть несколько проблем. Пожалуйста, помогите улучшить его или обсудите эти проблемы на странице обсуждения . ( Узнайте, как и когда удалять эти шаблонные сообщения )
|
Spreadsort — это алгоритм сортировки, изобретенный Стивеном Дж. Россом в 2002 году. [1] Он сочетает в себе концепции сортировки на основе распределения, такие как поразрядная сортировка и сортировка сегментами , с концепциями секционирования из сравнительных сортировок, таких как быстрая сортировка и сортировка слиянием . Результаты экспериментов показали, что он очень эффективен, часто превосходя традиционные алгоритмы, такие как быстрая сортировка, особенно в распределениях, демонстрирующих структуру и сортировку строк. Существует реализация с открытым исходным кодом с анализом производительности и тестами, [2] и HTML-документация. [3]
Быстрая сортировка идентифицирует опорный элемент в списке, а затем разделяет список на два подсписка: элементы меньше опорного и элементы выше опорного. Распространенная сортировка обобщает эту идею, разбивая список на разделы n / c на каждом этапе, где n — общее количество элементов в списке, а c — небольшая константа (на практике обычно от 4 до 8, когда сравнения медленные, или намного больше). в ситуациях, когда они быстры). Для этого он использует методы, основанные на распределении: сначала находит минимальное и максимальное значение в списке, а затем разделяет область между ними на n / c интервалы одинакового размера.Там, где кэширование является проблемой, может помочь наличие максимального количества ячеек на каждом этапе рекурсивного деления, в результате чего этот процесс разделения будет выполняться в несколько шагов. Хотя это приводит к увеличению количества итераций, это уменьшает количество промахов в кэше и может ускорить работу алгоритма в целом.
В случае, когда количество ячеек не меньше количества элементов, расширенная сортировка перерождается в сортировку по сегментам, и сортировка завершается. В противном случае каждая ячейка сортируется рекурсивно. Алгоритм использует эвристические тесты, чтобы определить, будет ли каждая ячейка сортироваться более эффективно с помощью расширенной сортировки или какого-либо другого классического алгоритма сортировки, а затем рекурсивно сортирует ячейку.
Как и другие виды сортировки, основанные на распределении, у расширенной сортировки есть тот недостаток, что программисту необходимо предоставить средства преобразования каждого элемента в числовой ключ с целью определения, в какую ячейку он попадает. Хотя это можно сделать и в произвольном порядке. элементы длины, такие как строки, учитывая, что за каждым элементом следует бесконечное количество минимальных значений, и действительно для любого типа данных, обладающего общим порядком , это может быть сложнее реализовать правильно, чем простую функцию сравнения, особенно в сложных структурах. Плохая реализация этой функции значения может привести к кластеризации, которая ухудшит относительную производительность алгоритма.
Производительность
[ редактировать ]Наихудшая производительность расширенной сортировки составляет O( n log n используется интросорт ) для небольших наборов данных, поскольку в качестве резервного варианта . В случае распределений, где размер ключа в битах k, умноженный на 2, примерно равен квадрату журнала размера списка n или меньше (2 k < (log n ) 2 ), в худшем случае он работает лучше, достигая времени O( n √ k - log n ) наихудшего случая для первоначально опубликованной версии и O( n ·(( k / s ) + s)) для версии с поддержкой кэша. . Для многих реальных задач сортировки с более чем 1000 элементами, включая сортировку строк, этот асимптотический худший случай лучше, чем O( n log n ).
Были проведены эксперименты по сравнению оптимизированной версии расширенной сортировки с высокооптимизированной версией C++. std::sort, реализованный с помощью интросорта. В списках целых чисел и чисел с плавающей точкой расширенная сортировка показывает улучшение времени выполнения случайных данных примерно в 2–7 раз в различных операционных системах. [1]
По производительности в пространстве расширенная сортировка хуже, чем большинство алгоритмов на месте: в своей простейшей форме это не алгоритм на месте, использующий O( n ) дополнительного пространства; в экспериментах примерно на 20% больше, чем при быстрой сортировке с использованием переменного тока 4–8. При использовании формы с поддержкой кэша (как включено в Boost.Sort) используется меньше памяти, и существует верхняя граница использования памяти, равная максимальному количеству ячеек, умноженному на максимальное количество рекурсий, что в конечном итоге оказывается на несколько килобайт, умноженных на размер. ключа в байтах. Хотя он использует асимптотически больше места, чем издержки O(log n ) быстрой сортировки или издержки O(1) пирамидальной сортировки, он использует значительно меньше места, чем базовая форма сортировки слиянием, которая использует вспомогательное пространство, равное пространству, занимаемому списком. .
Выполнение
[ редактировать ]unsigned RoughLog2 ( DATATYPE вход ) { unsigned char cResult = 0 ; // && необходим в некоторых компиляторах, чтобы избежать бесконечных циклов; это // существенно не ухудшает производительность if ( input >= 0 ) while (( input >> cResult ) && ( cResult < DATA_SIZE )) cResult ++ ; else while ((( input >> cResult ) < -1 ) && ( cResult < DATA_SIZE )) cResult ++ ; вернуть cResult ; } SIZETYPE GetMaxCount ( беззнаковый logRange , беззнаковый uCount ) { беззнаковый logSize = RoughLog2Size ( uCount ); unsigned uRelativeWidth = ( LOG_CONST * logRange ) / (( logSize > MAX_SPLITS ) ? MAX_SPLITS : logSize ); // Не пытайтесь сдвинуть бит больше, чем размер элемента if ( DATA_SIZE <= uRelativeWidth ) uRelativeWidth = DATA_SIZE - 1 ; return 1 << (( uRelativeWidth < ( LOG_MEAN_BIN_SIZE + LOG_MIN_SPLIT_COUNT )) ? ( LOG_MEAN_BIN_SIZE + LOG_MIN_SPLIT_COUNT ) : uRelativeWidth ); } void FindExtremes ( DATATYPE * Array , SIZETYPE uCount , DATATYPE & piMax , DATATYPE & piMin ) { SIZETYPE u ; piMin = piMax = Массив [ 0 ]; for ( u = 1 ; u < uCount ; ++ u ) { if ( Array [ u ] > piMax ) piMax = Array [ u ]; иначе, если ( Массив [ u ] < piMin ) piMin = Массив [ u ]; } } //---------------------SpreadSort Source----------------- Bin * SpreadSortCore ( DATATYPE * Array , SIZETYPE uCount , SIZETYPE & uBinCount , DATATYPE & iMax , DATATYPE & iMin ) { // Этот шаг занимает примерно 10% времени выполнения, но помогает избежать худшего // поведения и улучшает поведение при работе с реальными данными. Если вы заранее знаете // максимум и минимум, вы можете передать эти значения // и пропустить этот шаг для первой итерации FindExtremes (( DATATYPE * ) Array , uCount , iMax , iMin ); если ( iMax == iMin ) вернуть NULL ; ТИП ДАННЫХ divMin , divMax ; РАЗМЕР ТИП u ; int ЛогДивизор ; Бин * БинАррай ; Бин * ТекущийБин ; беззнаковый logRange ; logRange = RoughLog2Size (( SIZETYPE ) iMax - iMin ); если (( LogDivisor = logRange - RoughLog2Size ( uCount ) + LOG_MEAN_BIN_SIZE ) < 0 ) LogDivisor = 0 ; // Приведенный ниже оператор if необходим только в системах с большим объемом памяти // задержка относительно скорости процессора (большинство современных процессоров) if (( logRange - LogDivisor ) > MAX_SPLITS ) LogDivisor = logRange - MAX_SPLITS ; divMin = iMin >> LogDivisor ; divMax = iMax >> LogDivisor ; uBinCount = divMax - divMin + 1 ; // Выделяем контейнеры и определяем их размеры BinArray = calloc ( uBinCount , sizeof ( Bin )); // Проверка ошибки выделения памяти и чистый возврат с отсортированными результатами if ( ! BinArray ) { printf ( «Использование std::sort из-за ошибки выделения памяти \n » ); std :: sort ( Array , Array + uCount ); вернуть НУЛЬ ; } // Вычисление размера каждого контейнера; это занимает примерно 10% времени выполнения для ( u = 0 ; u < uCount ; ++ u ) BinArray [( Array [ u ] >> LogDivisor ) - divMin ]. uCount ++ ; // Назначаем позиции бинов BinArray [ 0 ]. CurrentPosition = ( ТИП ДАННЫХ * ) Массив ; для ( ты знак равно 0 ; ты < uBinCount - 1 ; ты ++ ) { BinArray [ ты + 1 ]. CurrentPosition = BinArray [ u ]. CurrentPosition + BinArray [ u ]. uCount ; Бинарный массив [ u ]. uCount = BinArray [ u ]. ТекущаяПозиция — Массив ; } BinArray [ u ]. uCount = BinArray [ u ]. ТекущаяПозиция — Массив ; // Перестановка на место. Это доминирует во время выполнения, особенно в подкачке; // Вызовы std::sort являются еще одним основным пользователем времени. for ( u = 0 ; u < uCount ; ++ u ) { for ( CurrentBin = BinArray + (( Array [ u ] >> LogDivisor ) - divMin ); ( CurrentBin -> uCount > u ); CurrentBin = BinArray + (( Array [ u ] >> LogDivisor ) — divMin )) SWAP ( Array + u , CurrentBin -> CurrentPosition ++ ); // Теперь, когда мы нашли элемент, принадлежащий этой позиции, // увеличиваем счетчик сегментов if ( CurrentBin -> CurrentPosition == Array + u ) ++ ( CurrentBin -> ТекущаяПозиция ); } // Если мы отсортировали сегменты, массив отсортирован, и нам следует пропустить рекурсию if ( ! LogDivisor ) { free ( BinArray ); вернуть НУЛЬ ; } Вернуть BinArray ; } void SpreadSortBins ( DATATYPE * Array , SIZETYPE uCount , SIZETYPE uBinCount , const DATATYPE & iMax , const DATATYPE & iMin , Bin * BinArray , SIZETYPE uMaxCount ) { SIZETYPE u ; for ( u = 0 ; u < uBinCount ; u ++ ) { SIZETYPE count = ( BinArray [ u ]. CurrentPosition - Array ) - BinArray [ u ]. uCount ; // Не выполнять сортировку, если нет хотя бы двух элементов для сравнения if ( count < 2 ) continue ; if ( count < uMaxCount ) std :: sort ( Array + BinArray [ u ]. uCount , BinArray [ u ]. CurrentPosition ); еще SpreadSortRec ( Array + BinArray [ u ]. uCount , count ); } бесплатно ( BinArray ); } void SpreadSortRec ( DATATYPE * Array , SIZETYPE uCount ) { if ( uCount < 2 ) return ; ТИП ДАННЫХ iMax , iMin ; РАЗМЕР ТИП uBinCount ; Bin * BinArray = SpreadSortCore ( Array , uCount , uBinCount , iMax , iMin ); если ( ! BinArray ) return ; SpreadSortBins ( Array , uCount , uBinCount , iMax , iMin , BinArray , GetMaxCount ( RoughLog2Size (( SIZETYPE ) iMax - iMin ), uCount )); } Два уровня так же хороши, как и любой другой
[ редактировать ]Интересный результат для алгоритмов этого общего типа (разделение по основанию, затем сортировка на основе сравнения) состоит в том, что они имеют O( n ) для любой ограниченной и интегрируемой функции плотности вероятности . [4] Этот результат можно получить, заставив Spreadsort всегда выполнять еще одну итерацию, если размер ячейки после первой итерации превышает некоторое постоянное значение. Если известно, что функция плотности ключей интегрируема и ограничена по Риману, эта модификация Spreadsort может обеспечить некоторое улучшение производительности по сравнению с базовым алгоритмом и будет иметь лучшую производительность в наихудшем случае. Если на это ограничение обычно нельзя положиться, это изменение добавит к алгоритму небольшие дополнительные накладные расходы во время выполнения и мало что принесет. Другими похожими алгоритмами являются Flashsort (который проще) и Adaptive Left Radix. [5] Адаптивное левое счисление, очевидно, очень похоже, основное отличие заключается в рекурсивном поведении: Spreadsort проверяет наихудшие ситуации и использует std::sort, чтобы избежать проблем с производительностью там, где это необходимо, а адаптивное левое счисление непрерывно рекурсивно до тех пор, пока не будет выполнено или пока данные не станут достаточно маленькими. использовать сортировку вставками.
Ссылки
[ редактировать ]- ^ Стивен Дж. Росс. Spreadsort Высокопроизводительный алгоритм сортировки общего случая. Методы и приложения параллельной и распределенной обработки , том 3, стр. 1100–1106. Лас-Вегас Невада. 2002.
- ^ «Репозиторий Boost.Sort на GitHub» . бустерг/сортировка .
- ^ «Документация по расширенной сортировке HTML» . Проверено 30 августа 2017 г.
- ^ Тамминен, Маркку (март 1985 г.). «Два уровня лучше любого». Дж. Алгоритмы . 6 (1): 138–144. дои : 10.1016/0196-6774(85)90024-0 .
- ^ Маус, Арне (2002). ARL, более быстрый алгоритм сортировки на месте, дружественный к кэшу (PDF) (технический отчет). CiteSeerX 10.1.1.399.8357 .