Brzo sortiranje

[cunac]

bizz kaže:
Ponovio sam test na Dev-C++ (za identican input):
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)?

Si siguran da je ovaj tvoj rezultat tocan,

10ms (bizz) vs 7911ms(qsort) -> 800x razlika

[bizz]

cunac kaže:
Si siguran da je ovaj tvoj rezultat tocan,

10ms (bizz) vs 7911ms(qsort) -> 800x razlika

Tako kaze test koji je pripremio TomK. Mozda je problem u Dev-C++?

[cunac]

bizz kaže:
Tako kaze test koji je pripremio TomK. Mozda je problem u Dev-C++?

recimo da radis 40000 operacija (samo jedna operacija za svaki podatak) , to ti je 4MHz , ako svaka operacija uzima samo 1 clock cycle sto nije slucaj niti u teoriji
Mozda imas jako brzi comp , hocu onda i ja jedan takav

[cunac]

cunac kaže:
recimo da radis 40000 operacija (samo jedna operacija za svaki podatak) , to ti je 4MHz , ako svaka operacija uzima samo 1 clock cycle sto nije slucaj niti u teoriji
Mozda imas jako brzi comp , hocu onda i ja jedan takav

me sucks kada je u pitanju matematika

[bizz]

Novi test. Izbacio sam qsort od Shadowmana jer se rusi (core) i ubacio std::qsort

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

In user mode :
Seconds : 0
Milliseconds : 941

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

In user mode :
Seconds : 13
Milliseconds : 138

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

In user mode :
Seconds : 7
Milliseconds : 671



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

In user mode :
Seconds : 1
Milliseconds : 922

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

In user mode :
Seconds : 27
Milliseconds : 48

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

In user mode :
Seconds : 16
Milliseconds : 353

[Shadowman]

Pogledaću kod ponovo kasnije da vidim zašto se ruši. Kod mene se nije rušio.

[bizz]

A ovo je kad su svi elementi = 0


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

In user mode :
Seconds : 0
Milliseconds : 270

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

In user mode :
Seconds : 1
Milliseconds : 231

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

In user mode :
Seconds : 11
Milliseconds : 516

[bizz]

Shadowman kaže:
Pogledaću kod ponovo kasnije da vidim zašto se ruši. Kod mene se nije rušio.

Ma nije vazno. QuickSort je generalno najbrzi algoritam. Nego Cunac, kako bi provjeravao da li je potrebno sortirati blok, odnosno da li je on vec sortiran?

[TomK]

Hm.......

Mislim da sam test (dakle pokretanje threadova, mjerenje vremena i njegov ispis) nebi trebali praviti probleme. Uostalom, program je toliko jednostavan da doista ne mogu vidjeti nesto da ne valja (mozda netko drugi moze?). Meni program nije krasirao nikada dok sam testirao algoritme. Ipak ne zelim iskljuciti mogucnos da tu nesto ne stima, ali gotovo sam 100 % uvjeren da je taj dio O.K.

Dali ima nekih problema sa samim algoritmima za sortiranje, to doista ne znam. Mozda je problem ipak tu?

Lijepi pozdravi,

[bizz]

Ako imas vremena TomK, pokusaj rezervirati polje velicine 50000 i sve elemente postavi na 0. Ako ti se Shadowmanov qsort ne srusi, onda je definitvno problem Dev-C++.

[TomK]

Evo ponovo kompletni program koji testira shadowman-ov algoritam. Program nije krasirao niti jednom u 10-ak testova koje sam napravio.

#include "windows.h"
#include "process.h"
#include "stdio.h"

#define SIZE_ 50000

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


unsigned __stdcall GenerateArrayThreadFunc(void* pArguments);
unsigned __stdcall SortArrayThreadFunc(void* pArguments);
void  PrintTimes(FILETIME *, FILETIME *);

void main()
{
	HANDLE hThread;
	UINT *pIntArray = 0;
	FILETIME creationTime, exitTime, kernelTime, userTime; 

	pIntArray = new UINT[SIZE_];

	hThread = (HANDLE) _beginthreadex(NULL, 0, &GenerateArrayThreadFunc, (void *) pIntArray, 0, NULL);
	WaitForSingleObject(hThread, INFINITE);
	GetThreadTimes(hThread,&creationTime, &exitTime, &kernelTime, &userTime);
	printf("Generate array times\n");
	printf("--------------------\n");
	PrintTimes(&kernelTime, &userTime);	

	hThread = (HANDLE) _beginthreadex(NULL, 0, &SortArrayThreadFunc, (void *) pIntArray, 0, NULL);
	WaitForSingleObject(hThread, INFINITE);
	GetThreadTimes(hThread,&creationTime, &exitTime, &kernelTime, &userTime);
	printf("Sort array times\n");
	printf("----------------\n");
	PrintTimes(&kernelTime, &userTime);

	delete [] pIntArray;
}

void  PrintTimes(FILETIME *kernelTime, FILETIME *userTime)
{
	SYSTEMTIME systemTime;
	FileTimeToSystemTime(kernelTime, &systemTime);
	printf("In kernel mode:\n");
	printf("Seconds       : %d\n", systemTime.wSecond);
	printf("Milliseconds  : %d\n\n", systemTime.wMilliseconds);

	FileTimeToSystemTime(userTime, &systemTime);
	printf("In user mode  :\n");
	printf("Seconds       : %d\n", systemTime.wSecond);
	printf("Milliseconds  : %d\n\n", systemTime.wMilliseconds);
}

unsigned __stdcall GenerateArrayThreadFunc(void* pArguments)
{
	UINT *pIntArray = (UINT *) pArguments;

	// ovdje code koji generira vrijednosti u array-u (pIntArray)

	for(int i = 0; i < SIZE_; i++ )
	{
		pIntArray[i] = 0;
	}

	return 0;
}

unsigned __stdcall SortArrayThreadFunc(void* pArguments)
{
	UINT *pIntArray = (UINT *) pArguments;

	// ovdje code koji sortiara array (pIntArray)
	
	quicksort(pIntArray, SIZE_);

	return 0;
}

A ovo su rezultati:

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

In user mode :
Seconds : 0
Milliseconds : 0

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

In user mode :
Seconds : 15
Milliseconds : 472

Nego bizz, imas li neki prcizniji opis greske kada se program srusi? I jesli li kompajlirao sa multithread C/C++ run-time library? Nadalje, koliko vidim, algoritam upotrebljava rekurzivne pozive. Mozda je problem u velicini stacka?

Lijepi pozdravi,

[bizz]

Definitvno je stack jer se qsort rusi na liniji

UINT low=1, high=n3;

Ocito je Dev-C++ kriv (mingw runtime library). Veceras cu probati sa VS6.

[Shadowman]

Ako hoćeš, možeš skinuti GCC za Windows odavde.

http://www.algoritam.net/mcs360/files/DJGPP.zip

[Shadowman]

TomK, a možeš li usporediti bizzov sort s mojim quicksortom na istoj nizu (ili bar iste veličine)? Ako može i na specijalnim slučajevima, kao već sortiran, sortiran naopako...

[cunac]

bizz kaže:
Ma nije vazno. QuickSort je generalno najbrzi algoritam. Nego Cunac, kako bi provjeravao da li je potrebno sortirati blok, odnosno da li je on vec sortiran?

Hm, mislio sam da se moze no izgleda da nije jednostavno.
Evo jedne male optimizacije
ovaj dio

for( UINT i=0; i<len; i++ )
		{
			if( data[head] & flag )
			{
				swap = data[--tail];

				data[tail] = data[head];

				data[head] = swap;
			}
			else
				head ++;
		}

zamjeni ovime

while( tail >= 0 ) {
			if( data[head] & flag )
			{
				swap = data[--tail];

				data[tail] = data[head];

				data[head] = swap;
			}
			else
				head ++;
		}

[bizz]

cunac kaže:
Hm, mislio sam da se moze no izgleda da nije jednostavno.
Evo jedne male optimizacije
ovaj dio

for( UINT i=0; i<len; i++ )
		{
			if( data[head] & flag )
			{
				swap = data[--tail];

				data[tail] = data[head];

				data[head] = swap;
			}
			else
				head ++;
		}

zamjeni ovime

while( tail >= 0 ) {
			if( data[head] & flag )
			{
				swap = data[--tail];

				data[tail] = data[head];

				data[head] = swap;
			}
			else
				head ++;
		}

Ne kuzim. Tail je uvijek >= 0. Ako blok nije sortiran (svi bitovi su 0), onda je tail == len na kraju provjere bloka. Kao i na pocetku. Ako je cijeli blok sortiran (svi bitovi su na 1) onda je tail == 0 u konacnici.

[TomK]

Evo usporedni test:

TEST 1: Unsorted array - Velicina array-a 4.000.000

Sort array times - SHADOWMAN
----------------
Seconds : 2
Milliseconds : 383

Sort array times - BIZZ
----------------
Seconds : 3
Milliseconds : 154


TEST 2: Sorted array - Velicina array-a 4.000.000

Sort array times - SHADOWMAN
----------------
Seconds : 0
Milliseconds : 961

Sort array times - BIZZ
----------------
Seconds : 2
Milliseconds : 383

TEST 3: Zero array - Velicina array-a 30.000

Sort array times - SHADOWMAN
----------------
Seconds : 15
Milliseconds : 812

Sort array times - BIZZ
----------------
Seconds : 0
Milliseconds : 40

Dakle, cini se da se shadowmanov algoritam ponasa bolje, osim u slucaju kad su svi elementi u array-u nulle, gdje je bizz-ov algoritam daleko superiorniji.

[cunac]

bizz kaže:
Ne kuzim. Tail je uvijek >= 0. Ako blok nije sortiran (svi bitovi su 0), onda je tail == len na kraju provjere bloka. Kao i na pocetku. Ako je cijeli blok sortiran (svi bitovi su na 1) onda je tail == 0 u konacnici.

sorry treba

while ( head < tail ) { 
etc 
}

izbjegavas jedan increment i skracujes petlju na len/2 , umjesto na len , barem mi se tako cini

[bizz]

cunac kaže:
sorry treba

while ( head < tail ) { 
etc 
}

izbjegavas jedan increment i skracujes petlju na len/2 , umjesto na len , barem mi se tako cini

Da, osim toga tail je unsigned int, ne moze biti < 0

Probam jos veceras. Rezultat cemo vidjeti sutra. Pozdrav.

[cunac]

bizz kaže:
Da, osim toga tail je unsigned int, ne moze biti < 0

Probam jos veceras. Rezultat cemo vidjeti sutra. Pozdrav.

osim toga ne bi li trebalo biti

if( data[head] & flag )
{
	swap = data[--tail];
        if ( !(swap & flag ) ){ 
		data[tail] = data[head];
		data[head++] = swap;
	}
}

Mislim da je to logicki OK, nisam siguran za ubrzanje no mislim da je brze