Спред-сортировка
 | В этой статье есть несколько проблем. Пожалуйста, помогите улучшить его или обсудите эти проблемы на странице обсуждения . ( Узнайте, как и когда удалять эти шаблонные сообщения )
|
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 input)
{
unsigned char cResult = 0;
// The && is necessary on some compilers to avoid infinite loops; it doesn't
// significantly impair performance
if (input >= 0)
while ((input >> cResult) && (cResult < DATA_SIZE)) cResult++;
else
while (((input >> cResult) < -1) && (cResult < DATA_SIZE)) cResult++;
return cResult;
}
SIZETYPE
GetMaxCount(unsigned logRange, unsigned uCount)
{
unsigned logSize = RoughLog2Size(uCount);
unsigned uRelativeWidth = (LOG_CONST * logRange)/((logSize > MAX_SPLITS) ? MAX_SPLITS : logSize);
// Don't try to bitshift more than the size of an element
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 = Array[0];
for (u = 1; u < uCount; ++u) {
if (Array[u] > piMax)
piMax = Array[u];
else if (Array[u] < piMin)
piMin = Array[u];
}
}
//---------------------SpreadSort Source-----------------
Bin *
SpreadSortCore(DATATYPE *Array, SIZETYPE uCount, SIZETYPE & uBinCount, DATATYPE &iMax, DATATYPE &iMin)
{
// This step is roughly 10% of runtime but it helps avoid worst-case
// behavior and improves behavior with real data. If you know the
// maximum and minimum ahead of time, you can pass those values in
// and skip this step for the first iteration
FindExtremes((DATATYPE *) Array, uCount, iMax, iMin);
if (iMax == iMin)
return NULL;
DATATYPE divMin,divMax;
SIZETYPE u;
int LogDivisor;
Bin * BinArray;
Bin* CurrentBin;
unsigned logRange;
logRange = RoughLog2Size((SIZETYPE)iMax-iMin);
if ((LogDivisor = logRange - RoughLog2Size(uCount) + LOG_MEAN_BIN_SIZE) < 0)
LogDivisor = 0;
// The below if statement is only necessary on systems with high memory
// latency relative to processor speed (most modern processors)
if ((logRange - LogDivisor) > MAX_SPLITS)
LogDivisor = logRange - MAX_SPLITS;
divMin = iMin >> LogDivisor;
divMax = iMax >> LogDivisor;
uBinCount = divMax - divMin + 1;
// Allocate the bins and determine their sizes
BinArray = calloc(uBinCount, sizeof(Bin));
// Memory allocation failure check and clean return with sorted results
if (!BinArray) {
printf("Using std::sort because of memory allocation failure\n");
std::sort(Array, Array + uCount);
return NULL;
}
// Calculating the size of each bin; this takes roughly 10% of runtime
for (u = 0; u < uCount; ++u)
BinArray[(Array[u] >> LogDivisor) - divMin].uCount++;
// Assign the bin positions
BinArray[0].CurrentPosition = (DATATYPE *)Array;
for (u = 0; u < uBinCount - 1; u++) {
BinArray[u + 1].CurrentPosition = BinArray[u].CurrentPosition + BinArray[u].uCount;
BinArray[u].uCount = BinArray[u].CurrentPosition - Array;
}
BinArray[u].uCount = BinArray[u].CurrentPosition - Array;
// Swap into place. This dominates runtime, especially in the swap;
// std::sort calls are the other main time-user.
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++);
// Now that we've found the item belonging in this position,
// increment the bucket count
if (CurrentBin->CurrentPosition == Array + u)
++(CurrentBin->CurrentPosition);
}
// If we've bucketsorted, the array is sorted and we should skip recursion
if (!LogDivisor) {
free(BinArray);
return NULL;
}
return 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;
// Don't sort unless there are at least two items to compare
if (count < 2)
continue;
if (count < uMaxCount)
std::sort(Array + BinArray[u].uCount, BinArray[u].CurrentPosition);
else
SpreadSortRec(Array + BinArray[u].uCount, count);
}
free(BinArray);
}
void
SpreadSortRec(DATATYPE *Array, SIZETYPE uCount)
{
if (uCount < 2)
return;
DATATYPE iMax, iMin;
SIZETYPE uBinCount;
Bin * BinArray = SpreadSortCore(Array, uCount, uBinCount, iMax, iMin);
if (!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 .