Спредсорт

Овај чланак је започет или проширен кроз пројекат семинарских радова. Потребно је проверити превод, правопис и вики-синтаксу.
Када завршите са провером, допишете да након |проверено=.

Спредсорт је алгоритам сортирања који комбинује концепте разврставања, попут оних у сортирању вишеструким разврставањем или сегментом сортирању, са елементима партиционисања из алгоритама попут квиксорт и сортирања спајањем. Алгоритам је измислио Стивен Ј. Рос и објавио 2002. године у раду "Спредсорт: Општи алгоритам сортирања високих перформанси".^[1] У пракси се покалазало да је алгоритам врло ефикасан, али с друге стране доста компликованији за имплементацију, од осталих сличних алгоритама.

Алгоритам уреди

Квиксорт користи пивот како би поделио листу на два дела, један у коме су вредности елемената мањи од пивота и други у коме су оне веће. Ова идеја се генерализује у спредсорту. У спредсорту се листа партиционише на н/ц дела у сваком кораку, где је н укупан број елемената у листи а ц мала константа. У пракси константа узима вредности од 4 до 8, за случејеве када су низови дугачки, док за краће низове може имати веће вредности. Разврставање се постиже на сличан начин као и у осталим сортирањима, прво се пронађу најмања и највећа вредност у низу, а затим се опсег вредности између њих раздели на н/ц корпе једнаке величине. У случају када је број корпи једнак броју елемената, спредсорт се дегенерише у сегментно сортирање и алгоритам стаје. Иначе, свака корпа се сортира рекурзивно, при чему се уз помоћ хеуристика за сваку корпу тестира да ли је ефикасније ту корпу сортирати спредсортом или неким другим класичним алгоритмом.

Када је кеширање проблем, број корпи по итерацији разврставања се може ограничити. Последица оваквог ограничавања је већи број итерација самог процеса разврставања. С друге стране смањује се број грешака при кеширању што доводи до бржег рада алгоритма у општем случају.

Као и код других сортирања разврставањем, спреадсорт при имплементацији захтева да програмер осмисли на који начин ће своје елементе претворити у нумеричке вредности тј. кључева на основу којих ће алгоритам одредити којој корпи кој елемент припада.

Перформансе уреди

Како свака корпа може бити сортирана другим алгоритмом сортирања, временска сложеност у најгорем случају управо зависи од најгорих временских сложености у корпама. У случају сортирања корпе спајањем то је О(н лог н), док уколико је коришћен квиксорт О(н²). У случајевима када је просечна величина кључа у битовима пута два, мања од квадрата логаритма величине низа (2к < лог(н)², где је к - број битова кључа, н - дужина низа), спредсорт има боље перформансе у најгорем случају и то О(н·(к - лог(н))^.5) у огриналној верзији, и О(н·((к/ц) + ц)) за унапређену верзију која води рачуна о проблемима с кеширањем.

Оптимизованија верзија алгоритма је поређена са високо-оптимизованим C++ std::sort, који је имплементиран интросортом. У низовима целоброних вредности, као и оних са децималама, спредсорт сортира два до седам пута брже на разним оперативним системима.^[1]

Што се тиче просторне сложености, спредсорт је гори од већине стандардних алгоритама. У најосновнијем облику спредсорт користи О(н) додатног меморијског простора. У експериментима се показало да основни спредсорт користи и до 20% више меморије од најпопуларнијег квиксорта, када константа ц има вредности од 4 до 8. Оптимизована верзија која смањује грешке у кеширању користи мање меморије због чињенице да се у њој поставља горња граница коришћења меморије, ограничавањем максималног броја корпи по итерацији. Иако користи асимптотски више простора од квиксорта О(лог н) или хипсорта О(1), спредсорт користи значајно мање простора од основних облика сортирања спајањем који користе онлико додатног простора колики је низ. Спредсорт ради врло ефикасно када је неопходно сортирати огромне низове елемената коју су превелики да стану у меморију, те захтевају и додатни простор на диску.

Имплементација уреди

unsigned 
RoughLog2(DATATYPE input) 
{
	unsigned char cResult = 0;
	// && je neophodno da bi se izbegle beskonačne petlje
	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);
	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)
{
        // Ovaj korak traje 10% ukupnog vremena izvršavanja ali pomaže 
        // za izbegavanje najgoreg slučaja. Ukoliko se unapred znaju min i max
        // ovaj korak može da se preskoči u prvoj iteraciji.
	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;
        // Donja if naredba je neophodna kod sistema u kojima je memorija
	// znatno sporija od procesora.
	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("Using std::sort because of memory allocation failure\n");
		std::sort(Array, Array + uCount);
		return NULL;
	}
		
	// Proračunavanje veličina za svaku korpu. 10% vremena izvršavanja.
	for(u = 0; u < uCount; ++u)
		BinArray[(Array[u] >> LogDivisor) - divMin].uCount++;
	// Dodeljivanje pozicija korpama.
	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;
	
	// Razmenjivanje vrednosti. Ovo oduzima većinu vremena izvršavanja.
	// std::sort pozivi takođe.
	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);
	}
	
	// Preskače se rekurzija ako je sortirano segmentim sortiranjem
	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;
		// Ne sortira se ukoliko ima manje od 2 korpe.
		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));
}

Побољшање и применљивост уреди

Један од резултата тестирања спредсорта јесте да он може постати сложености О(н) уколико су улазни подаци вредности непрекидне интеграбилне функције.^[2] Ова сложеност се постиже тако што се модификује алгоритам да увек изврши две итерације, уколико је после првог пролаза прављења корпи број корпи већи од одређене константне вредности. Уколико је познато да улазне вредности задовољавају горе споменути критеријум оваква модификација доводи до знатног побољшања рада. Овако модификован спредсорт има и боље перформансе у најгорем случају. Једини проблем код ове верзије алгоритма представља чињеница да се не може гарантовати испуњење услова, као и то да ова измена успорава сортирање баш када услов није испуњен.

Референце уреди

^ ^а ^б Стевен Ј. Росс. Тхе Спреадсорт Хигх-перформанце Генерал-цасе Сортинг Алгоритхм. Параллел анд Дистрибутед Процессинг Тецхниqуес анд Апплицатионс, Волуме 3. стр. 1100-1106. Лас Вегас Невада. 2002.
^ Маркку Тамминен: Тwо Левелс аре ас Гоод ас Анy. Ј. Алгоритхмс. 6 (1): 138—144. 1985. Недостаје или је празан параметар |титле= (помоћ)

[automatski_generisano1-1] а ^б Стевен Ј. Росс. Тхе Спреадсорт Хигх-перформанце Генерал-цасе Сортинг Алгоритхм. Параллел анд Дистрибутед Процессинг Тецхниqуес анд Апплицатионс, Волуме 3. стр. 1100-1106. Лас Вегас Невада. 2002.

[2] Маркку Тамминен: Тwо Левелс аре ас Гоод ас Анy. Ј. Алгоритхмс. 6 (1): 138—144. 1985. Недостаје или је празан параметар |титле= (помоћ)

[1]

[2]