Spredsort

S Vikipedije, slobodne enciklopedije

Spredsort je algoritam sortiranja koji kombinuje koncepte razvrstavanja, poput onih u sortiranju višestrukim razvrstavanjem ili segmentom sortiranju, sa elementima particionisanja iz algoritama poput kviksort i sortiranja spajanjem. Algoritam je izmislio Stiven J. Ros i objavio 2002. godine u radu "Spredsort: Opšti algoritam sortiranja visokih performansi".[1] U praksi se pokalazalo da je algoritam vrlo efikasan, ali s druge strane dosta komplikovaniji za implementaciju, od ostalih sličnih algoritama.

Algoritam[uredi | uredi izvor]

Kviksort koristi pivot kako bi podelio listu na dva dela, jedan u kome su vrednosti elemenata manji od pivota i drugi u kome su one veće. Ova ideja se generalizuje u spredsortu. U spredsortu se lista particioniše na n/c dela u svakom koraku, gde je n ukupan broj elemenata u listi a c mala konstanta. U praksi konstanta uzima vrednosti od 4 do 8, za slučejeve kada su nizovi dugački, dok za kraće nizove može imati veće vrednosti. Razvrstavanje se postiže na sličan način kao i u ostalim sortiranjima, prvo se pronađu najmanja i najveća vrednost u nizu, a zatim se opseg vrednosti između njih razdeli na n/c korpe jednake veličine. U slučaju kada je broj korpi jednak broju elemenata, spredsort se degeneriše u segmentno sortiranje i algoritam staje. Inače, svaka korpa se sortira rekurzivno, pri čemu se uz pomoć heuristika za svaku korpu testira da li je efikasnije tu korpu sortirati spredsortom ili nekim drugim klasičnim algoritmom.

Kada je keširanje problem, broj korpi po iteraciji razvrstavanja se može ograničiti. Posledica ovakvog ograničavanja je veći broj iteracija samog procesa razvrstavanja. S druge strane smanjuje se broj grešaka pri keširanju što dovodi do bržeg rada algoritma u opštem slučaju.

Kao i kod drugih sortiranja razvrstavanjem, spreadsort pri implementaciji zahteva da programer osmisli na koji način će svoje elemente pretvoriti u numeričke vrednosti tj. ključeva na osnovu kojih će algoritam odrediti kojoj korpi koj element pripada.

Performanse[uredi | uredi izvor]

Kako svaka korpa može biti sortirana drugim algoritmom sortiranja, vremenska složenost u najgorem slučaju upravo zavisi od najgorih vremenskih složenosti u korpama. U slučaju sortiranja korpe spajanjem to je O(n log n), dok ukoliko je korišćen kviksort O(n2). U slučajevima kada je prosečna veličina ključa u bitovima puta dva, manja od kvadrata logaritma veličine niza (2k < log(n)2, gde je k - broj bitova ključa, n - dužina niza), spredsort ima bolje performanse u najgorem slučaju i to O(n·(k - log(n)).5) u ogrinalnoj verziji, i O(n·((k/c) + c)) za unapređenu verziju koja vodi računa o problemima s keširanjem.

Optimizovanija verzija algoritma je poređena sa visoko-optimizovanim C++ std::sort, koji je implementiran introsortom. U nizovima celobronih vrednosti, kao i onih sa decimalama, spredsort sortira dva do sedam puta brže na raznim operativnim sistemima.[1]

Što se tiče prostorne složenosti, spredsort je gori od većine standardnih algoritama. U najosnovnijem obliku spredsort koristi O(n) dodatnog memorijskog prostora. U eksperimentima se pokazalo da osnovni spredsort koristi i do 20% više memorije od najpopularnijeg kviksorta, kada konstanta c ima vrednosti od 4 do 8. Optimizovana verzija koja smanjuje greške u keširanju koristi manje memorije zbog činjenice da se u njoj postavlja gornja granica korišćenja memorije, ograničavanjem maksimalnog broja korpi po iteraciji. Iako koristi asimptotski više prostora od kviksorta O(log n) ili hipsorta O(1), spredsort koristi značajno manje prostora od osnovnih oblika sortiranja spajanjem koji koriste onliko dodatnog prostora koliki je niz. Spredsort radi vrlo efikasno kada je neophodno sortirati ogromne nizove elemenata koju su preveliki da stanu u memoriju, te zahtevaju i dodatni prostor na disku.


Implementacija[uredi | uredi izvor]

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));
}

Poboljšanje i primenljivost[uredi | uredi izvor]

Jedan od rezultata testiranja spredsorta jeste da on može postati složenosti O(n) ukoliko su ulazni podaci vrednosti neprekidne integrabilne funkcije.[2] Ova složenost se postiže tako što se modifikuje algoritam da uvek izvrši dve iteracije, ukoliko je posle prvog prolaza pravljenja korpi broj korpi veći od određene konstantne vrednosti. Ukoliko je poznato da ulazne vrednosti zadovoljavaju gore spomenuti kriterijum ovakva modifikacija dovodi do znatnog poboljšanja rada. Ovako modifikovan spredsort ima i bolje performanse u najgorem slučaju. Jedini problem kod ove verzije algoritma predstavlja činjenica da se ne može garantovati ispunjenje uslova, kao i to da ova izmena usporava sortiranje baš kada uslov nije ispunjen.

Reference[uredi | uredi izvor]

  1. ^ а б Steven J. Ross. The Spreadsort High-performance General-case Sorting Algorithm. Parallel and Distributed Processing Techniques and Applications, Volume 3. стр. 1100-1106. Las Vegas Nevada. 2002.
  2. ^ Markku Tamminen: Two Levels are as Good as Any. J. Algorithms. 6 (1): 138—144. 1985.  Недостаје или је празан параметар |title= (помоћ)
Preuzeto iz „https://sr.wikipedia.org/w/index.php?title=Spredsort&oldid=26786034”