Spreadsort - Spreadsort

Spreadsort это алгоритм сортировки изобретен Стивеном Дж. Россом в 2002 году.^[1] Он сочетает в себе концепции сортировок на основе распределения, таких как радиальная сортировка и ведро сортировка, с концепциями разделения из видов сравнения, таких как быстрая сортировка и Сортировка слиянием. В экспериментальных результатах было показано, что он очень эффективен, часто превосходя традиционные алгоритмы, такие как быстрая сортировка, особенно в распределениях, демонстрирующих структуру и сортировку строк. Есть реализация с открытым исходным кодом с анализом производительности и тестами^[2]и HTML-документация^[3].

Quicksort определяет поворотный элемент в списке, а затем разбивает список на два подсписка: эти элементы меньше, чем сводная, а те, что больше, чем сводная. Spreadsort обобщает эту идею, разбивая список на п/c перегородки на каждом шаге, где п это общее количество элементов в списке и c - небольшая константа (на практике обычно между 4 и 8, когда сравнения медленные, или намного больше в ситуациях, когда они быстрые). Для этого используются методы, основанные на распределении: сначала определяется минимальное и максимальное значение в списке, а затем область между ними разделяется на п/c Если кэширование является проблемой, может помочь максимальное количество ячеек на каждом шаге рекурсивного деления, заставляя этот процесс деления выполнять несколько шагов. Хотя это вызывает больше итераций, это снижает количество промахов в кэше и может ускорить работу алгоритма в целом.

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

Как и другие сортировки, основанные на распределении, Spreadsort имеет слабость, заключающуюся в том, что программист должен предоставить средства преобразования каждого элемента в числовой ключ с целью определения того, в какую корзину он попадает. Хотя это можно сделать для произвольных- элементы длины, такие как строки, считая, что за каждым элементом следует бесконечное количество минимальных значений, и действительно для любого типа данных, имеющего общий заказ, это может быть труднее реализовать правильно, чем простая функция сравнения, особенно на сложных структурах. Плохая реализация этого ценить может привести к кластеризации, которая вредит относительной производительности алгоритма.

Спектакль

Наихудшая производительность сортировки спредов - O (п бревно п) для небольших наборов данных, поскольку он использует интросорт как запасной вариант. В случае дистрибутивов, где размер ключа в битах k умноженное на 2 - это примерно квадрат журнала размера списка п или меньше (2k <(журнал п)²), в худшем случае он работает лучше, достигая O (п √k - бревно п) наихудшее время для первоначально опубликованной версии и O (п·((k/s) + s)) для версии с поддержкой кеширования. Для многих реальных задач сортировки с более чем 1000 элементами, включая сортировку строк, этот наихудший случай асимптотики лучше, чем O (п бревно п).

Были проведены эксперименты по сравнению оптимизированной версии spreadsort с высоко оптимизированным C ++. std :: sort, реализованный с помощью интросорта. В списках целых чисел и чисел с плавающей запятой spreadsort показывает примерно 2–7-кратное улучшение времени выполнения для случайных данных в различных операционных системах.[1]

С точки зрения производительности в пространстве сортировка по спредам хуже, чем большинство локальных алгоритмов: в простейшей форме это не локальный алгоритм, использующий O (п) дополнительное место; в экспериментах примерно на 20% больше, чем при быстрой сортировке с использованием c, равного 4–8. В форме с поддержкой кеширования (включенной в Boost.Sort) используется меньше памяти, и существует верхняя граница использования памяти: максимальное количество бункеров, умноженное на максимальное количество рекурсий, что в конечном итоге составляет несколько килобайт, умноженных на размер. ключа в байтах. Хотя он использует асимптотически больше места, чем O (log п) накладные расходы на быструю сортировку или накладные расходы O (1) на динамическую сортировку, она использует значительно меньше места, чем базовая форма сортировки слиянием, которая использует вспомогательное пространство, равное пространству, занимаемому списком.

Выполнение

беззнаковый RoughLog2(ТИП ДАННЫХ Вход) {	беззнаковый char cResult = 0;	// && необходимо в некоторых компиляторах, чтобы избежать бесконечных циклов; это не	// значительно ухудшить производительность	если (Вход >= 0)		пока ((Вход >> cResult) && (cResult < DATA_SIZE)) cResult++;	еще		пока (((Вход >> cResult) < -1) && (cResult < DATA_SIZE)) cResult++;	возвращаться cResult;}РАЗМЕРGetMaxCount(беззнаковый logRange, беззнаковый uCount){	беззнаковый logSize = RoughLog2Size(uCount);	беззнаковый uRelativeWidth = (LOG_CONST * logRange)/((logSize > MAX_SPLITS) ? MAX_SPLITS : logSize);	// Не пытайтесь сдвинуть бит больше, чем размер элемента	если (DATA_SIZE <= uRelativeWidth)		uRelativeWidth = DATA_SIZE - 1;	возвращаться 1 << ((uRelativeWidth < (LOG_MEAN_BIN_SIZE + LOG_MIN_SPLIT_COUNT)) ? 		(LOG_MEAN_BIN_SIZE + LOG_MIN_SPLIT_COUNT) :  uRelativeWidth);}пустота FindExtremes(ТИП ДАННЫХ *Множество, РАЗМЕР uCount, ТИП ДАННЫХ & piMax, ТИП ДАННЫХ & piMin){	РАЗМЕР ты;	piMin = piMax = Множество[0];	за (ты = 1; ты < uCount; ++ты) {		если (Множество[ты] > piMax)			piMax = Множество[ты];		еще если (Множество[ты] < piMin)			piMin = Множество[ты];	}}	// --------------------- Источник SpreadSort -----------------Корзина *SpreadSortCore(ТИП ДАННЫХ *Множество, РАЗМЕР uCount, РАЗМЕР & uBinCount, ТИП ДАННЫХ &iMax, ТИП ДАННЫХ &iMin){	// Этот шаг занимает примерно 10% времени выполнения, но помогает избежать худшего случая	// поведение и улучшает поведение с реальными данными. Если вы знаете	// максимум и минимум заранее, вы можете передать эти значения в	// и пропустим этот шаг для первой итерации	FindExtremes((ТИП ДАННЫХ *) Множество, uCount, iMax, iMin);	если (iMax == iMin)		возвращаться НОЛЬ;	ТИП ДАННЫХ divMin,divMax;	РАЗМЕР ты;	int LogDivisor;	Корзина * BinArray;	Корзина* CurrentBin;	беззнаковый logRange;	logRange = RoughLog2Size((РАЗМЕР)iMax-iMin);	если ((LogDivisor = logRange - RoughLog2Size(uCount) + LOG_MEAN_BIN_SIZE) < 0)		LogDivisor = 0;	// Приведенный ниже оператор if необходим только в системах с большим объемом памяти	// задержка относительно скорости процессора (большинство современных процессоров)	если ((logRange - LogDivisor) > MAX_SPLITS)		LogDivisor = logRange - MAX_SPLITS;	divMin = iMin >> LogDivisor;	divMax = iMax >> LogDivisor;	uBinCount = divMax - divMin + 1;		// Располагаем бункеры и определяем их размеры	BinArray = каллок(uBinCount, размер(Корзина));	// Проверка сбоя выделения памяти и чистый возврат с отсортированными результатами	если (!BinArray) {		printf("Использование std :: sort из-за сбоя выделения памяти п");		стандартное::Сортировать(Множество, Множество + uCount);		возвращаться НОЛЬ;	}			// Расчет размера каждой корзины; это занимает примерно 10% времени выполнения	за (ты = 0; ты < uCount; ++ты)		BinArray[(Множество[ты] >> LogDivisor) - divMin].uCount++;	// Назначаем позиции бункера	BinArray[0].Текущая позиция = (ТИП ДАННЫХ *)Множество;	за (ты = 0; ты < uBinCount - 1; ты++) {		BinArray[ты + 1].Текущая позиция = BinArray[ты].Текущая позиция + BinArray[ты].uCount;		BinArray[ты].uCount = BinArray[ты].Текущая позиция - Множество;	}	BinArray[ты].uCount = BinArray[ты].Текущая позиция - Множество;		// Поменяем на место. Это доминирует во время выполнения, особенно в свопе;	// вызовы std :: sort - еще один основной пользователь времени.	за (ты = 0; ты < uCount; ++ты) {		за (CurrentBin = BinArray + ((Множество[ты] >> LogDivisor) - divMin);  (CurrentBin->uCount > ты); 			CurrentBin = BinArray + ((Множество[ты] >> LogDivisor) - divMin))				ЗАМЕНА(Множество + ты, CurrentBin->Текущая позиция++);		// Теперь, когда мы нашли элемент, принадлежащий этой позиции,		// увеличиваем счетчик ведра		если (CurrentBin->Текущая позиция == Множество + ты)			++(CurrentBin->Текущая позиция);	}		// Если мы отсортировали сегменты, массив будет отсортирован, и мы должны пропустить рекурсию	если (!LogDivisor) {		свободный(BinArray);		возвращаться НОЛЬ;	}	возвращаться BinArray;}пустотаSpreadSortBins(ТИП ДАННЫХ *Множество, РАЗМЕР uCount, РАЗМЕР uBinCount, const ТИП ДАННЫХ &iMax				, const ТИП ДАННЫХ &iMin, Корзина * BinArray, РАЗМЕР uMaxCount){	РАЗМЕР ты;	за (ты = 0; ты < uBinCount; ты++) {		РАЗМЕР считать = (BinArray[ты].Текущая позиция - Множество) - BinArray[ты].uCount;		// Не сортировать, если есть хотя бы два элемента для сравнения		если (считать < 2)			Продолжить;		если (считать < uMaxCount)			стандартное::Сортировать(Множество + BinArray[ты].uCount, BinArray[ты].Текущая позиция);		еще			SpreadSortRec(Множество + BinArray[ты].uCount, считать);	}	свободный(BinArray);}пустота SpreadSortRec(ТИП ДАННЫХ *Множество, РАЗМЕР uCount){	если (uCount < 2)		возвращаться;			ТИП ДАННЫХ iMax, iMin;	РАЗМЕР uBinCount;	Корзина * BinArray = SpreadSortCore(Множество, uCount, uBinCount, iMax, iMin);	если (!BinArray)		возвращаться;	SpreadSortBins(Множество, uCount, uBinCount, iMax, iMin, BinArray,	               GetMaxCount(RoughLog2Size((РАЗМЕР)iMax-iMin), uCount));}

Два уровня так же хороши, как и все

Интересный результат для алгоритмов этого общего типа (разбиение по основанию системы счисления, затем сортировка на основе сравнения) состоит в том, что они равны O (п) для любых ограниченных и интегрируемых функция плотности вероятности.^[4] Этот результат можно получить, заставив Spreadsort всегда выполнять итерацию еще раз, если размер ячейки после первой итерации превышает некоторое постоянное значение. Если известно, что функция плотности клавиш Интегрируемый по Риману и ограниченная, эта модификация Spreadsort может достичь некоторого улучшения производительности по сравнению с базовым алгоритмом и будет иметь лучшую производительность в худшем случае. Если на это ограничение обычно нельзя положиться, это изменение добавит немного дополнительных накладных расходов времени выполнения к алгоритму и мало выиграет. Другие похожие алгоритмы Flashsort (что проще) и Adaptive Left Radix.^[5] Adaptive Left Radix, по-видимому, очень похож, основное отличие заключается в рекурсивном поведении с проверкой Spreadsort для наихудших ситуаций и использованием std :: sort, чтобы избежать проблем с производительностью, где это необходимо, и Adaptive Left Radix, рекурсивно рекурсивно непрерывно до тех пор, пока не будет выполнено или данные не будут достаточно маленькими использовать сортировку вставкой.

Рекомендации

1. Стивен Дж. Росс. Высокопроизводительный алгоритм сортировки общего случая Spreadsort. Методы и приложения параллельной и распределенной обработкиТом 3. С. 1100–1106. Лас-Вегас, Невада. 2002 г.
2. "Репозиторий Boost.Sort на github". boostorg / sort.
3. «Документация по HTML Spreadsort». Получено 30 августа 2017.
4. Тамминен, Маркку (март 1985 г.). «Два уровня ничуть не хуже всех». J. Алгоритмы. 6 (1): 138–144. Дои:10.1016/0196-6774(85)90024-0.
5. Маус, Арне (2002). ARL, более быстрый и удобный алгоритм сортировки на месте (PDF) (Технический отчет). CiteSeerX  10.1.1.399.8357.