Brzo sortiranje

[bizz]

TomK kaže:
Evo , bizz je sada svima uputio izazov. Moze li netko moze istu stvar napraviti da radi efikasnije? Ili nesto unaprijediti u bizz-ovom algoritmu?

Moze. Slijedece linije

if( head )
	sort( data, head, flag );

if( len-tail )
	sort( data+head, len-tail, flag );

treba zamjeniti sa

if( head > 1 )
	sort( data, head, flag );

if( (len-tail) > 1 )
	sort( data+head, len-tail, flag );

jer je nepotrebno sortirati blokove koji imaju svega jedan element. Time malo narusavamo linearnost algoritma, ali zato dobivamo na brzini.

[TomK]

Generate array times
--------------------
In kernel mode:
Seconds : 0
Milliseconds : 0

In user mode :
Seconds : 0
Milliseconds : 200

Sort array times
----------------
In kernel mode:
Seconds : 0
Milliseconds : 0

In user mode :
Seconds : 1
Milliseconds : 402

Bravo bizz!!!

Nisam testirao dali algoritam jos uvijek ispravno radi (u sto zapravo ne sumnjam), ali algoritam radi vise nego duplo brze!!!

[TomK]

Evo ovako:
Testirao sam i ovaj shadowman-ov code za linear sort.

void linear_sort(int * a, int size, int max)
{
	int * count=new int[max];
	for(int i=0; i<max; count[i++]=0);
	for(int i=0; i<size; count[a[i++]]++);
	for(int i=0, current=0; i<max; i++)
		for(; count[i]--; a[current++]=i);
}

funkciju koja generira brojeve sam neznatno prilagodio da ne generira broj koji je veci od nekog maximalnog.

pIntArray[i] = (rand() * rand()) % MAX_SIZE_;

Nadalje, predhodni testovi su bili izvrsavani u debug modu (moja greska), ali rezultate koji cu sada prezentirati su na temelju testa koji je izvrsio program kompajliran u release modu (optimiziran za maximalnu brzinu izvrsavanja).

SIZE i MAX_SIZE su 8.000.000

Evo rezultata za shadowmanov algoritam:

Generate array times
--------------------
In kernel mode:
Seconds : 0
Milliseconds : 0

In user mode :
Seconds : 1
Milliseconds : 842

Sort array times
----------------
In kernel mode:
Seconds : 0
Milliseconds : 10

In user mode :
Seconds : 2
Milliseconds : 62

A ovako se ponasa bizz-ov algoritam:

Generate array times
--------------------
In kernel mode:
Seconds : 0
Milliseconds : 10

In user mode :
Seconds : 1
Milliseconds : 862

Sort array times
----------------
In kernel mode:
Seconds : 0
Milliseconds : 0

In user mode :
Seconds : 6
Milliseconds : 970

Dakle, iako su ovo rezultati samo po jednog eksperimenta, odstupanja u rezultatima nisu znacajna, i ovi rezultati se mogu smatrati reprezentativnim.

Drugo, cini se da je shadowmanov algoritam daleko superiorniji, i izvrsava se gotovo 3 puta brze. Masina na kojemu je test izvrsen je ista.

Evo, shadowman za sada vodi. Tko god postavi svoj code, testirat cu ga i usporediti sa ostalima (sto uostalom mozete i sami napraviti ako zelite)

Lijepi pozdravi

[Shadowman]

Da, samo sortiranje je zapravo brže 15 puta, ali kod mene ima restrikcija da postoji točno određen range.

[Shadowman]

Još jedna stvar je zanimljiva. Jesi li siguran bizz da je to baš linearno. Jer log(8000000)=13, što je vrlo blizu 15, pa izgleda da je to kao n log n, a ne linearno. Da napomenem da je linearno sortiranje nemoguće bez poznavanja range-a.

[cunac]

Shadowman kaže:
Još jedna stvar je zanimljiva. Jesi li siguran bizz da je to baš linearno. Jer log(8000000)=13, što je vrlo blizu 15, pa izgleda da je to kao n log n, a ne linearno. Da napomenem da je linearno sortiranje nemoguće bez poznavanja range-a.

meni to izgleda kao blago modificirani quicksort , samo sto koristi bitove da bi grupirao umjesto vrijednosti

[Shadowman]

Previše su mi nedeskriptivne varijable da bih se dugo koncentrisao na kod, pa da skužim kako radi. Trebao je malo pojasniti. Jedna činjenica stoji. Sortiranje poređenjem, kako god da ga postigneš, ne može biti brže od n log n, a to mogu i dokazati. Linearno može, ako se poznaje range, što je u tom slučaju lako. Ako ne, onda ni to ne može.

[bizz]

Sortiranje je linearno stoga sto je potrebno proci 32 puta (za svaki bit posebno) kroz svaki od elemenata niza.

Sortiranje je nelinearno ako uracunamo rekurzivne pozive funkcije zbog razlicitog broja blokova koje treba sortirati. Niti je jednak broj blokova za svaki niz kojeg treba sortirati, niti je jednak broj elemenata za svaki od tih blokova. Ali ono sto je jednako je ukupan broj elemenata zadanog niza koje treba obraditi (svaki element 32 puta ako izuzmemo optimizaciju koju sam predlozio TomK).

Ono sto sam htio pokazati ovim algoritmom je da je moguce sortirati niz gotovo linearno bez poznavanja podrucja u kojem su ulazni podaci. Ukoliko je podrucje poznato, onda je rijesenje koje je predlozio Shadowman uvijek najbolje (cini mi se da se algoritam u originalu zove Bucket) ako tu ne racunamo i dodatnu memoriju koju Bucket zahtijeva.

Moj algoritam radi tako da svaki pocetni blok (u pocetku cijeli niz) rastavlja na dva manja bloka, u prvom su to brojevi kojima je MSB = 0, a u drugom bloku su to brojevi kojima je MSB = 1, i tako redom 32 puta od MSB do LSB.

[Shadowman]

bizz kaže:
Moj algoritam radi tako da svaki pocetni blok (u pocetku cijeli niz) rastavlja na dva manja bloka, u prvom su to brojevi kojima je MSB = 0, a u drugom bloku su to brojevi kojima je MSB = 1, i tako redom 32 puta od MSB do LSB.

To je onda u principu isto kao quicksort. Podijeliš ih na manje i veće. To je n log n. Samo ti izgleda kao linearno (32*n), jer je log(MAX_INT)=32. Ovo iskorištava činjenicu da su integeri limitirani veličinom MAX_INT, tj. s 32 bita. Kako bi povećavali broj bitova, tako bi se povećavao i 32 (kao log(MAX_INT). Stoga je ovo n log n. Nedostatak je što će algoritam ići 32 nivoa, čak i kad manje treba. Ako koristiš obični quicksort, uvijek ćeš proći kroz manje nivoa. Plus, podjela može biti vrlo neujednačena.

[bizz]

Shadowman kaže:
To je onda u principu isto kao quicksort. Podijeliš ih na manje i veće. To je n log n. Samo ti izgleda kao linearno (32*n), jer je log(MAX_INT)=32. Ovo iskorištava činjenicu da su integeri limitirani veličinom MAX_INT, tj. s 32 bita. Kako bi povećavali broj bitova, tako bi se povećavao i 32 (kao log(MAX_INT). Stoga je ovo n log n. Nedostatak je što će algoritam ići 32 nivoa, čak i kad manje treba. Ako koristiš obični quicksort, uvijek ćeš proći kroz manje nivoa. Plus, podjela može biti vrlo neujednačena.

Kod QuickSorta ces proci kroz manji broj nivoa samo ako je ulazni niz dovoljno malen. No sa povecanjem niza, povecava se i broj nivoa. Pokusaj usporediti broj prolaza po blokovima kod niza koji ima samo 3 elementa i niza koji ima 1.000.000 elemenata.

Nadalje, QuickSort koristi pivot element. Ako je to prvi element niza, a svi ostali elementi su recimo veci (nema manjih) onda taj blok ostane potpuno neiskoristen, odnosno nije podijeljen na manje i vece vrijednosti, stoga ga treba ponovo obraditi.

Kod mog algoritma, ako je blok neobradjen (svi bitovi su 0 ili 1), isti blok se nastavlja obradjivati ali za jedan bit nize sve do LSB. Na kraju, svaki element je obradjen 32 puta.

U principu, algoritam je los kod manje kolicine podatka, ali sa povecanjem broja podataka se popravlja.

Najbolje je napraviti test i vidjeti kako se ponasa u odnosu na QuickSort. Zivo me zanima.

[bizz]

Evo prvi test na topicu math_baby (uz izbacivanje duplikata):

time(bizz) = 15.558.023
time(qsort) = 64.212.873

[Shadowman]

U principu, trebao bi imati bar preko 1 GB da bi quicksort išao preko 32 nivoa. Evo standardni quicksort pa nek TomK usporedi.

void quicksort(int * a, int n)
{
	if(n>3)
	{
		if((a[0]<a[n/2] && a[n/2]<=a[n-1]) || (a[0]>a[n/2] && a[n/2]>=a[n-1]))
		{
			int temp=a[0];
			a[0]=a[n/2];
			a[n/2]=temp;
		}
		else
		if((a[0]<a[n-1] && a[n-1]<a[n/2]) || (a[0]>a[n-1] && a[n-1]>a[n/2]))
		{
			int temp=a[0];
			a[0]=a[n-1];
			a[n-1]=temp;
		}
		int low=1, high=n-1;
		while(true)
		{
			for(;a[low]<a[0];low++);
			for(;high && a[high]>=a[0];high--);
			if(low>high)
				break;
			int temp=a[low];
			a[low]=a[high];
			a[high]=temp;
		}
		int temp=a[0];
		a[0]=a[high];
		a[high]=temp;
		quicksort(a, high);
		quicksort(a+high+1, n-high-1);
	}
	else
	if(n==3)
	{
		if(a[0]>a[1])
		{
			int temp=a[0];
			a[0]=a[1];
			a[1]=temp;
		}
		if(a[1]>a[2])
		{
			int temp=a[2];
			a[2]=a[1];
			a[1]=temp;
		}
		if(a[0]>a[1])
		{
			int temp=a[0];
			a[0]=a[1];
			a[1]=temp;
		}
	}
	else
	if(n==2 && a[0]>a[1])
	{
		int temp=a[0];
		a[0]=a[1];
		a[1]=temp;
	}
}

[Shadowman]

Pardon, bar preko 4 GB.

[bizz]

Ponovljen test:

--Started at: Mon Apr 12 23:57:16 2004
SPACE = 4194304
time(qsort) = 57562054
time(bizz) = 18298197

--Ended at: Mon Apr 12 23:57:38 2004

[cunac]

bizz kaže:
Ponovljen test:

--Started at: Mon Apr 12 23:57:16 2004
SPACE = 4194304
time(qsort) = 57562054
time(bizz) = 18298197

--Ended at: Mon Apr 12 23:57:38 2004

hajde probaj qsort iz liba koji dolazi sa VC-om , bas me zanima kako je taj napisan.
Inace tvoj algoritam ce i sortirani niz sortirati zar ne ? Mozes ubaciti kontrolu da li je potrebno soritrati odredjeni blok pa bi to dodano ubrzalo. No ostajem pri tome da je to modificirani quicksort sto se tice logike , no specijaliziran za brojeve. Svejedno interesantna ideja.

[cunac]

Shadowman kaže:
U principu, trebao bi imati bar preko 1 GB da bi quicksort išao preko 32 nivoa. Evo standardni quicksort pa nek TomK usporedi.

void quicksort(int * a, int n)
{
	if(n>3)
	{
		if((a[0]<a[n/2] && a[n/2]<=a[n-1]) || (a[0]>a[n/2] && a[n/2]>=a[n-1]))
		{
			int temp=a[0];
			a[0]=a[n/2];
			a[n/2]=temp;
		}
		else
		if((a[0]<a[n-1] && a[n-1]<a[n/2]) || (a[0]>a[n-1] && a[n-1]>a[n/2]))

itd..

Hajde izvuci na pocetak da je
n2 = n/2; i onda napravi substituciju svugdje gdje se pojavljuje n/2 sa n2. Imas oko 8 puta vise operacija samo u tome sto moze biti znacajno na velikome broju operacija.
Hajde bizz probaj i to
sto za n-1

[Shadowman]

OK

void quicksort(int * a, int n)
{
	if(n>3)
	{
		int n2=n/2;
		int n3=n-1;
		if((a[0]<a[n2] && a[n2]<=a[n3]) || (a[0]>a[n2] && a[n2]>=a[n3]))
		{
			int temp=a[0];
			a[0]=a[n2];
			a[n2]=temp;
		}
		else
		if((a[0]<a[n3] && a[n3]<a[n2]) || (a[0]>a[n3] && a[n3]>a[n2]))
		{
			int temp=a[0];
			a[0]=a[n3];
			a[n3]=temp;
		}
		int low=1, high=n3;
		while(true)
		{
			for(;a[low]<a[0];low++);
			for(;high && a[high]>=a[0];high--);
			if(low>high)
				break;
			int temp=a[low];
			a[low]=a[high];
			a[high]=temp;
		}
		int temp=a[0];
		a[0]=a[high];
		a[high]=temp;
		quicksort(a, high);
		quicksort(a+high+1, n-high-1);
	}
	else
	if(n==3)
	{
		if(a[0]>a[1])
		{
			int temp=a[0];
			a[0]=a[1];
			a[1]=temp;
		}
		if(a[1]>a[2])
		{
			int temp=a[2];
			a[2]=a[1];
			a[1]=temp;
		}
		if(a[0]>a[1])
		{
			int temp=a[0];
			a[0]=a[1];
			a[1]=temp;
		}
	}
	else
	if(n==2 && a[0]>a[1])
	{
		int temp=a[0];
		a[0]=a[1];
		a[1]=temp;
	}
}

[bizz]

cunac kaže:
hajde probaj qsort iz liba koji dolazi sa VC-om , bas me zanima kako je taj napisan.
Inace tvoj algoritam ce i sortirani niz sortirati zar ne ? Mozes ubaciti kontrolu da li je potrebno soritrati odredjeni blok pa bi to dodano ubrzalo. No ostajem pri tome da je to modificirani quicksort sto se tice logike , no specijaliziran za brojeve. Svejedno interesantna ideja.

Da, imas pravo, algoritam je u neku ruku modificirani qsort, ima neke prednosti (i nedostatke naravno) u odnosu na qsort.

Testirati ne mogu do veceras zbog posla. Pozdrav.

[TomK]

Evo kako se shadowman-ov quicksort ponasa:

Generate array times
--------------------
In kernel mode:
Seconds : 0
Milliseconds : 0

In user mode :
Seconds : 1
Milliseconds : 842

Sort array times
----------------
In kernel mode:
Seconds : 0
Milliseconds : 0

In user mode :
Seconds : 5
Milliseconds : 157

Lijepi pozdravi

[bizz]

Ponovio sam test na Dev-C++ (za identican input):

Generate array[8000000] times
--------------------
In kernel mode:
Seconds : 0
Milliseconds : 20

In user mode :
Seconds : 0
Milliseconds : 921

Sort array times (qsort)
----------------
In kernel mode:
Seconds : 0
Milliseconds : 0

In user mode :
Seconds : 6
Milliseconds : 279

Sort array times (bizz)
----------------
In kernel mode:
Seconds : 0
Milliseconds : 0

In user mode :
Seconds : 7
Milliseconds : 691



Generate array[16000000] times
--------------------
In kernel mode:
Seconds : 0
Milliseconds : 50

In user mode :
Seconds : 1
Milliseconds : 932

Sort array times (qsort)
----------------
In kernel mode:
Seconds : 0
Milliseconds : 0

In user mode :
Seconds : 13
Milliseconds : 449

Sort array times (bizz)
----------------
In kernel mode:
Seconds : 0
Milliseconds : 0

In user mode :
Seconds : 16
Milliseconds : 243


Dakle qsort je brzi. Cunac, kazes da je moguce ubaciti kontrolu da li je neki blok potrebno sortirati. Ako rezerviram polje koje sadrzava samo nule, rezultat je:

Generate array[40000] times
--------------------
In kernel mode:
Seconds : 0
Milliseconds : 0

In user mode :
Seconds : 0
Milliseconds : 0

Sort array times (qsort)
----------------
In kernel mode:
Seconds : 0
Milliseconds : 20

In user mode :
Seconds : 7
Milliseconds : 911

Sort array times (bizz)
----------------
In kernel mode:
Seconds : 0
Milliseconds : 0

In user mode :
Seconds : 0
Milliseconds : 10

qsort ovdje ubjedljivo gubi. Ako povecam velicinu polja na 50000, qsort se rusi (Segmentation fault)?