PDA

View Full Version : Brzo sortiranje


Shadowman
10.04.2004., 17:01
Evo jedno interesantno pitanje. Recimo da trebate sortirati integere, poznato je točno u kojem rasponu integeri mogu biti. Na primjer imamo 1000 brojeva, a znamo da su svi u rasponu od 1 do 2000. Kako je najbrže sortirati ih?

TomK
10.04.2004., 17:09
Treba li napisati program koji ce testirati algoritam, pokusati dati neki rezultat koji bi se mogao usporediti sa drugim rezultatima, ili ocekujes da se topic svede na cisto teoritiziranje?

Shadowman
10.04.2004., 17:55
Kako bilo. A kad se skuži kako i program bi bio vrlo kratak. Vjerovatno bi se brže napisao program nego napisalo objašnjenje. Mada ne bi bilo loše usporediti s quicksortom.

TomK
10.04.2004., 18:41
Postoje neke Win32 API funkcije koje mogu mjeriti vrijeme za svaki thread. Dakle, ako bi array bio dovoljno dugacak (dakle, da zaposlimo PC dovoljno dugo), mogli bi lijepo izmjeriti tocno vrijeme (10 ms rezolucija) koliko je nekom algoritmu trebalo da obavi posao. Taj cu program ja napisati, pa svatko tko napise algoritam, mozemo testirati (naravno, na jednoj masini, jer ce brza masina obaviti posao brze).

Lijepi pozdravi,

cunac
10.04.2004., 18:42
Shadowman kaže:
Kako bilo. A kad se skuži kako i program bi bio vrlo kratak. Vjerovatno bi se brže napisao program nego napisalo objašnjenje. Mada ne bi bilo loše usporediti s quicksortom.

ako znas raspon onda je trivijalno. Potreban ti je samo jedan prolaz kroz listu brojeva.
Samo prebrojavas koliko ima kojih, znaci imas polje od 2000 diskretnih vrijednosti i sve sto radis je

diskretnoPolje[ vrijednosti[i] ]++;

ispis je takodjer trivijalan

Shadowman
10.04.2004., 18:52
Baš tako. Sortiranje u linearnom vremenu je lako, ako se zna raspon. A zašto je moguće ići ispod n log n? Zato što se izbjegne uspoređivanje. Ovako možemo jednostavno brojati koliko se puta svaki integer pojavio i onda samo ispisati svaki onoliko puta koliko se puta pojavio počevši od najmanjeg.

TomK
10.04.2004., 21:12
Hajde ipak da stvari napravimo za nijansu zanimljivijim: Prosirimo zadatak tako da:

1) kreirate integer array odredjene velicine, i generirate njegove vrijednosti od kojih je svaka vrijednost razlicita od druge (dakle dvije vrijednosti se ne ponavljaju).

2) sortirajte array sto brze (algoritam sami izaberite).

Da bi ipak mogli testirati koliko su oba algoritma (generiranje i sortiranje) efektivni, evo mali program koji moze mjeriti vrijeme (10 ms rezolucija):


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

#define ARRAY_SIZE 4000000

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

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

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)
{
int *pIntArray = (int *) pArguments;
pIntArray = new int[ARRAY_SIZE];

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

return 0;
}

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

// ovdje code koji sortiara array (pIntArray)

return 0;
}


Dakle, array je velicine 4 MB, tako da pokriva gotovo sve integer vrijednosti. Ukoliko se to cini previse, moze se velicina i smanjiti, no mislim da ce se efikasnost algoritma bolje pokazati na vecim velicinama. Drugo, kao sto vidite, postoje dvije thread funkcije: Jedna za generiranje arraya (GenerateArrayThreadFunc) i jedna za sortiranje arraya (SortArrayThreadFunc). Tu treba doci vas code (u main funkkciji ne trebate dodavati nikakav code).
pIntArray predstavlja adresu arraya, i ne trebate niti alocirati niti brisati memoriju, jer ce to program uciniti za vas. Dakle u GenerateArrayThreadFunc je vec alocirana memorija, vase je da generirate vrijednosti i popunite array. Taj isti array ce te dobiti u SortArrayThreadFunc, i odmah mozete pristupiti sortiranju, Prrogram ce na kraju ispisati vrijeme koji je svaki od ova dva threda potrosio kako u kernel, tako i u user modu.
Program kompajlirajte sa multithreaded library.
Ukoliko nemate odgovarajuci kompajler, ostavite code na forumu, a onda cu ja to testirati i izvjestiti o rezultatima.
Nadam se da ce biti zanimljivo.

Shadowman
10.04.2004., 21:27
Za sve integer vrijednosti treba ti 8 GB.

TomK
10.04.2004., 22:01
Za sve integer vrijednosti treba ti 8 GB.
:confused: :confused: :confused:
Ako je integer velicine 32 bita (sto jeste), onda treba 4 GB

Tocno je da 4 MB (kako sam napisao u programu) ne pokriva sve integere (greska u koracima), ali to nije niti bitno: ideja koju sam zeli prezentirati je sasvim druga, i vjerujem kako nije potrebno da je ponovo objasnjavam.

Lijepi pozdravi,

bizz
10.04.2004., 22:03
/************************************************
** Copyright (C) 2004 bizz@anonymous.to. All rights reserved. :D
**
** This file may be distributed and/or modified under the terms of the
** GNU General Public License version 2 as published by the Free Software
** Foundation and appearing in the file LICENSE.GPL
**
** This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE
** WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE.
**
** See http://www.opensource.org/licenses/gpl-license.php for GPL licensing information.
*/

#include <stdlib.h>
#include <string.h>
#include <iostream.h>

typedef unsigned long int ULINT;

template<typename T>
class LinearSort
{
ULINT order[sizeof(T)][256];

public:
void sort(T* data, ULINT len )
{
int h = 0, t = 0;

memset( order, 0, sizeof(order) );

for( ULINT i=0; i<len; i++ )
{
T num = data[i];

if( num < 0 ) t++;

for(int j=0; j<sizeof(T); j++)
{
order[j][num&0xFF] ++;

num >>= 8;
}
}

int elem[sizeof(T)] = { 0 };

for( i=0; i<len; i++ )
{
T num = 0;

for(int j=sizeof(T)-1; j>=0; j--)
{
num <<= 8;

while(! order[j][elem[j]] )
{
elem[j] ++;
}

order[j][elem[j]] --;

num |= elem[j];
}

num < 0 ? data[h++] = num : data[t++] = num;
}
}
};

int main()
{
const int size = 8;

int data[size] = { 12435438, -233456, 343456, -1324234, 0 ,5436435 ,-324522 ,-4};

LinearSort<int> linear;

linear.sort( data, size );

for( int i=0; i<size; i++ )
cout << data[i] << endl;

return 0;
}
:

Shadowman
10.04.2004., 22:08
Jedan integer=2^2 bytes
Broj integera= 2^32
Memorija za sve intgere= 2^2 * 2^32 = 2^34 = 16 GB

I ja sam bio pogrešio. Treba zapravo 16 GB. :D

bizz
10.04.2004., 22:12
Shadowman kaže:
Baš tako. Sortiranje u linearnom vremenu je lako, ako se zna raspon.

Ne trebas znati raspon da bi linearno sortirao cijele brojeve. Pogledaj moj primjer.

Shadowman
10.04.2004., 22:25
Šta ti znači sizeof(order) u ovome dolje?

memset( order, 0, sizeof(order) );

Ne možeš linearno sortirati ukoliko ne možeš rezervirati dovoljno memorije da bi mogao brojati svaku vrijednost, koja se može pojaviti. To je dobro poznata stvar i može se dokazati. Ustvari ja ti mogu dokazati, ako znaš nešto matematike. Ako možeš rezervisati dovoljno memorije za svaki element, onda se može lako. Zašto posežeš za template-om, kad ovo možeš primijeniti samo na integerima (ili nekom drugom skupu za koji postoji bijekcija s tog elementa na integere, tj. za svaki element možeš izračunati unique integer u range-u koji se može pohraniti u memoriju).

bizz
10.04.2004., 22:29
Shadowman kaže:
Šta ti znači sizeof(order) u ovome dolje?

memset( order, 0, sizeof(order) );

Postavlja sve elemente polja order na nulu.

Ne možeš linearno sortirati ukoliko ne možeš rezervirati dovoljno memorije da bi mogao brojati svaku vrijednost, koja se može pojaviti. To je dobro poznata stvar i može se dokazati. Ustvari ja ti mogu dokazati, ako znaš nešto matematike. Ako možeš rezervisati dovoljno memorije za svaki element, onda se može lako. Zašto posežeš za template-om, kad ovo možeš primijeniti samo na integerima (ili nekom drugom skupu za koji postoji bijekcija s tog elementa na integere, tj. za svaki element možeš izračunati unique integer u range-u koji se može pohraniti u memoriju).

Pogledaj jos jedanput, odnosno probaj sa razlicitim ulaznim podacima u rasponu koji integer podrzava i uvjerit ces se da NIJE potrebno poznavati raspon ulaznih podataka da bi ih se moglo linearno sortirati.

Shadowman
10.04.2004., 22:34
sizeof() radi na tipovima, a ne na instancama. sizeof(ULINT) je najčešće 4. 4*256=1024. Znači ovako možeš brojati samo ponavljanje 1024 broja, bez da analiziram dalje.

Shadowman
10.04.2004., 22:38
Uh, pardon, može sizeof.

bizz
10.04.2004., 22:38
Shadowman kaže:
sizeof() radi na tipovima, a ne na instancama. sizeof(ULINT) je najčešće 4. 4*256=1024. Znači ovako možeš brojati samo ponavljanje 1024 broja, bez da analiziram dalje.

sizeof(order) kod mene vraca 4096. A kod tebe?

bizz
10.04.2004., 22:39
Template je koristen kako bi ulazni podaci mogli bi signed ili unsigned int ili char, kao i short i long varijante.

bizz
10.04.2004., 22:41
Sortiranje je linearno, odnosno brzina sortiranja ovisi samo o kolicini ulaznih podataka, ali ne i njihovom sadrzaju.

Shadowman
10.04.2004., 22:44
Znači da ti je veći unsigned long int. Ali, nema veze. Ipak ostaje da je to jedan broj, koji nema veze s veličinom niza, koji se sortira. Da bi sortirao linearno moraš brojati svaki od brojeva koji se može pojaviti. Znači, ako imaš više od 4096 RAZLIČITIH brojeva za sortirati, nema teoretske šanse da to napraviš

bizz
10.04.2004., 22:49
Shadowman kaže:
Znači da ti je veći unsigned long int. Ali, nema veze. Ipak ostaje da je to jedan broj, koji nema veze s veličinom niza, koji se sortira. Da bi sortirao linearno moraš brojati svaki od brojeva koji se može pojaviti. Znači, ako imaš više od 4096 RAZLIČITIH brojeva za sortirati, nema teoretske šanse da to napraviš

Pa stos je u tome da ovaj sort broji svaki od brojeva koji se moze pojaviti, ali na jedan specifican nacin.

Nacin na koji to vi zamisljate je problematican jer je potrebno alocirati veliko polje, 2 na 32-u ili dva na 64-u, a to je prakticki nemoguce. Pogledaj jos jedanput, odnosno probaj rezerviratil polje od recimo 1.000.000 random brojeva u rasponu koji to int ili unsigned int dozvoljava i uvjeri se da sort radi.

Shadowman
10.04.2004., 23:10
Pošto insistiraš na tome da radi, probao sam. I nije čak izbacio ni iste brojeve, a kamoli da ih je sortirao. Na primjer izbacio je 77 nula, dvije jedinice, a najmanji broj u inputu bio je 1000048663. U principu, malo je vjerovatno da se ikoji broj ponovio u inputu, a u tvom outputu svaki broj se ponavlja puno puta. probao sam tražiti specifične brojeve iz inputa u tvom outputu i nema ih.

bizz
10.04.2004., 23:27
Imas pravo. Ideja je bila dobra, ali matematika je ipak neumoljiva. Bye.

Shadowman
10.04.2004., 23:48
bizz kaže:
Ideja je bila dobra, ali matematika je ipak neumoljiva.

Eto vidiš kako je život matematičara težak. :D

bizz
10.04.2004., 23:50
Shadowman kaže:
Eto vidiš kako je život matematičara težak. :D

Uopce ti ne zavidim :D

Shadowman
11.04.2004., 01:36
Evo funkcija za linearno sortiranje. size je veličina niza, a elementi niza su ograničeni na nenegativne integere manje od max.


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

TomK
11.04.2004., 12:31
U svome rjesenju koristis 4 for petlje, koje sa stanovista performansi i nisu bas najoptimalnije sredstvo za rjesavanje problema, a narocito ukoliko je broj elemenata u array-u ogroman.

Pitanje je dali se isti algoritam (ili neki drugi) moze napisati da radi optimalnije?

To je upravo bila ideja iza programa koji ce mjeriti koliko je vremena potrosio neki algoritam na obavljanje posla. Za takvo sto je dakako potreban prikladan array ciji su elementi slucajno rasporedjeni i razliciti. Taj algoritam je u sebi vec izazov napisati.

No, zbog nekog razloga, svaka stvar na ovome forumu koja je izvan nekog trivijalnog ili teorijskog (matematickog) nivoa, ne moze pobuditi interes kod forumasa. Sto je razlog tomu ne znam, ali znam da sam dobro na putu da prestanem biti aktivan sudionik ovdje.

Lijepi pozdravi,

Shadowman
11.04.2004., 13:00
Četiri petlje znače četiri puta n. A to je linearno. Drugo je ako su nested. Jedna je, ali ako malo bolje pogledaš, vidjećeš da se za svaki element, unutrašnja petlja izvrši jednom, a to znači da je linearno. Nije ono tvoje prošlo nezapaženo. Napisaću i ja svoju verziju, ali daj malo vremena. Imam zadaću za sutra. Ustvari, morao bih sad ići pisati, a ja gubim vrijeme na forumu. :D Jesi li mislio na bilo kakve integere ili u odreženom rasponu, kao što je prvobitno bilo zamišljeno. Zašto insistiraš da su svi različiti? Kao dodatni dio zadatka?

TomK
11.04.2004., 13:12
Zapravo, ono sto sam zelio je da ovoj diskusiji o sortiranju dam jednu novu dimenziju, a ta je da doista, na egzaktan nacin testiramo razlicite tehnike sortiranja, ali i njihove implementacije. Nedavno nam je predavanje drzao jedan programer koji pise sah programe zadnjih dvadesetak godina, i on je nekoliko puta naglasio kako su for petlje zadnje sto jedan sah program treba koristiti (profesionalni sah programi ih gotovo i ne koriste), upravo zbog svojih performansi, i da postoje drugi nacini kako se odredjeni problemi mogu rijesiti bez for petlji (on je for petlje nazvao "rjesenje za ljencine" jer ih je tako jednostavno koristiti).
Dakle dali cemo testirati array koji ima sve vrijednosti razlicite, dali cemo koristiti ovaj ili onaj algoritam, mislim da uopce nije toliko ni vazno, jer ono sto je bitno je da zajedno vidimo kako je neki algoritam najbolje implementirati. Koje je jezicne konstrukcije nabolje koristiti? Gdje su mjesta koja su najveci konzumenti vremena? Mogu li se ta "uska grla" rijesiti? Jedini razlog zasto bi array trebao biti ogroman i po mogucnsti tezak za sortiranje je taj sto je vremenska rezolucija koju mozemo mjeriti 10 ms. Dakle, trebali bi doista zaposliti masinu kako bi vidjeli razlike u performansama.

Mislim da bi to doista bilo zanimljivo vidjeti. A zapravo, sve je tu. Jedino nedostaju algoritmi o kojima se toliko raspravljalo na forumu zadnjih dana.

cunac
11.04.2004., 15:12
TomK kaže:
Zapravo, ono sto sam zelio je da ovoj diskusiji o sortiranju dam jednu novu dimenziju, a ta je da doista, na egzaktan nacin testiramo razlicite tehnike sortiranja, ali i njihove implementacije. Nedavno nam je predavanje drzao jedan programer koji pise sah programe zadnjih dvadesetak godina, i on je nekoliko puta naglasio kako su for petlje zadnje sto jedan sah program treba koristiti (profesionalni sah programi ih gotovo i ne koriste), upravo zbog svojih performansi, i da postoje drugi nacini kako se odredjeni problemi mogu rijesiti bez for petlji (on je for petlje nazvao "rjesenje za ljencine" jer ih je tako jednostavno koristiti).


unroll petlji je opce poznata stvar no primjenjljiv je na petljama koje imaju mali i relativno predvidiv broj iteracija, pogotovo maksimum. Za petlje kojima je maksimum neka funkcija sa "nepredvidivim" rezultatima to nije primjenljvo.
Unroll vecinom radis u igrama kada se prolazi kroz dinamicke liste itd..

Sto se tice testiranja performansi, propusti program kroz profiler i onda gledaj gdje su mjesta koja trose najvise vremena. Samo mjerenje vremena izvrsavanja ti nece dati hint gdje su moguce optimizacije.

math_baby
11.04.2004., 15:51
TomK kaže:
Zapravo, ono sto sam zelio je da ovoj diskusiji o sortiranju dam jednu novu dimenziju, a ta je da doista, na egzaktan nacin testiramo razlicite tehnike sortiranja, ali i njihove implementacije. Nedavno nam je predavanje drzao jedan programer koji pise sah programe zadnjih dvadesetak godina, i on je nekoliko puta naglasio kako su for petlje zadnje sto jedan sah program treba koristiti (profesionalni sah programi ih gotovo i ne koriste), upravo zbog svojih performansi, i da postoje drugi nacini kako se odredjeni problemi mogu rijesiti bez for petlji (on je for petlje nazvao "rjesenje za ljencine" jer ih je tako jednostavno koristiti).
Dakle dali cemo testirati array koji ima sve vrijednosti razlicite, dali cemo koristiti ovaj ili onaj algoritam, mislim da uopce nije toliko ni vazno, jer ono sto je bitno je da zajedno vidimo kako je neki algoritam najbolje implementirati. Koje je jezicne konstrukcije nabolje koristiti? Gdje su mjesta koja su najveci konzumenti vremena? Mogu li se ta "uska grla" rijesiti? Jedini razlog zasto bi array trebao biti ogroman i po mogucnsti tezak za sortiranje je taj sto je vremenska rezolucija koju mozemo mjeriti 10 ms. Dakle, trebali bi doista zaposliti masinu kako bi vidjeli razlike u performansama.

Mislim da bi to doista bilo zanimljivo vidjeti. A zapravo, sve je tu. Jedino nedostaju algoritmi o kojima se toliko raspravljalo na forumu zadnjih dana.

Prestani pricati gluposti! Performanse algoritma se ne mjere tako da se uzme "stoperica" i onda izmjeri vrijeme trajanja izvrsavanja. Jer, time dobivamo samo brzinu izvrsavanja tog algoritma na toj i toj konkretnoj platformi, za te i te konkretne ulazne parametre.
Postoji cijela teorija koja iza toga stoji (i koju ti vjerojatno prezires zato sto je "teorija") koja govori kako se to radi. Brzina algoritma ne daje se ni u kakvim vremenskim jedinicama (jer se one mijenjaju kako se procesori i njihove brzine usavrsavaju). Umjesto toga, mjeri se broj elementarnih operacija koje algoritam mora izvrsiti. I pri tome se gleda asimptotsko ponasanje funkcije koja na osnovi velicine ulaznih podataka daje broj potrebnih elementarnih operacija.

Sve preporuke tipa "nemojte koristiti petlje", nemojte ovo, nemojte ono nemaju veze s mozgom. Procitaj neku knjigu koja se bavi analizom algoritama i shvati jedno: bez jako dobrog znanja matematike i statistike tu se nema sto traziti!

Najbolja literatura koju bih mogla preporuciti svakome koga problematika izracunavanja slozenosti algoritama zanima je ova knjiga Herberta Wilfa (http://www.cis.upenn.edu/%7Ewilf/AlgComp2.html) (koju mozete besplatno skinuti na ovom linku), kao i Knuthova trilogija "The art of computer programming" ili, recimo ova, vrlo popularna knjiga (http://www.amazon.com/exec/obidos/tg/detail/-/0262032937/102-9735743-1448915?v=glance).

Izbijte sebi iz glave ideju da je moguce sastavljati kvalitetne algoritme (ili procjenjivati vrijeme izvrsavanja vec postojecih) bez teoretskog znanja (uglavnom matematickog) koje je opisano u gore navedenim knjigama!

Dizajn aplikacija je jedno, analiza algoritama nesto sasvim drugo!

math_baby:rolleyes:

lijencina
11.04.2004., 16:10
TomK kaže:
Hajde ipak da stvari napravimo za nijansu zanimljivijim: Prosirimo zadatak tako da:

1) kreirate integer array odredjene velicine, i generirate njegove vrijednosti od kojih je svaka vrijednost razlicita od druge (dakle dvije vrijednosti se ne ponavljaju).

2) sortirajte array sto brze (algoritam sami izaberite).

Da bi ipak mogli testirati koliko su oba algoritma (generiranje i sortiranje) efektivni, evo mali program koji moze mjeriti vrijeme (10 ms rezolucija):


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

#define ARRAY_SIZE 4000000

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

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

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)
{
int *pIntArray = (int *) pArguments;
pIntArray = new int[ARRAY_SIZE];

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

return 0;
}

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

// ovdje code koji sortiara array (pIntArray)

return 0;
}


Dakle, array je velicine 4 MB, tako da pokriva gotovo sve integer vrijednosti. Ukoliko se to cini previse, moze se velicina i smanjiti, no mislim da ce se efikasnost algoritma bolje pokazati na vecim velicinama. Drugo, kao sto vidite, postoje dvije thread funkcije: Jedna za generiranje arraya (GenerateArrayThreadFunc) i jedna za sortiranje arraya (SortArrayThreadFunc). Tu treba doci vas code (u main funkkciji ne trebate dodavati nikakav code).
pIntArray predstavlja adresu arraya, i ne trebate niti alocirati niti brisati memoriju, jer ce to program uciniti za vas. Dakle u GenerateArrayThreadFunc je vec alocirana memorija, vase je da generirate vrijednosti i popunite array. Taj isti array ce te dobiti u SortArrayThreadFunc, i odmah mozete pristupiti sortiranju, Prrogram ce na kraju ispisati vrijeme koji je svaki od ova dva threda potrosio kako u kernel, tako i u user modu.
Program kompajlirajte sa multithreaded library.
Ukoliko nemate odgovarajuci kompajler, ostavite code na forumu, a onda cu ja to testirati i izvjestiti o rezultatima.
Nadam se da ce biti zanimljivo.

Imam prijedlog. A da povecas prioritet procesa i threada na real time critical sa SetPriorityClass() i SetThreadPriority() dok vrsis mjerenje inace ti drugi procesi mogu utjecati na rezultat. Naprimjer drugi proces prekine tvoj proces i izbrise ti razne nivoe cache-a u procesoru. Ne mora se dogoditi ali nije garantirano. Ovako bi to bilo manje vjerojatno.

Slican primjer za Java, mjerenje i thread priority:
http://java.ittoolbox.com/groups/groups.asp?v=java-l&i=369350

lijencina
11.04.2004., 16:16
Osim toga, ako koristite C++ uvijek mozete koristiti STL za razna sortiranja. Na taj nacin se sortiranje cesto svede na jednu liniju nesto kao:

MojePolje.sort();

MojePolje moze biti bilo sto sto ima definiran operator <= (ili jedan od tih, ne mogu se tocno sjetiti). na taj nacin je izuzetno lako sortirati int, char, long, float, double. A ako definiras operator sam, onda mozes sortirati bilo sta ukljuculuci strukture.

Cesto puno jednostavnije.

cunac
11.04.2004., 16:23
math_baby kaže:
Prestani pricati gluposti! Performanse algoritma se ne mjere tako da se uzme "stoperica" i onda izmjeri vrijeme trajanja izvrsavanja. Jer, time dobivamo samo brzinu izvrsavanja tog algoritma na toj i toj konkretnoj platformi, za te i te konkretne ulazne parametre.
Postoji cijela teorija koja iza toga stoji (i koju ti vjerojatno prezires zato sto je "teorija") koja govori kako se to radi. Brzina algoritma ne daje se ni u kakvim vremenskim jedinicama (jer se one mijenjaju kako se procesori i njihove brzine usavrsavaju). Umjesto toga, mjeri se broj elementarnih operacija koje algoritam mora izvrsiti. I pri tome se gleda asimptotsko ponasanje funkcije koja na osnovi velicine ulaznih podataka daje broj potrebnih elementarnih operacija.

Sve preporuke tipa "nemojte koristiti petlje", nemojte ovo, nemojte ono nemaju veze s mozgom. Procitaj neku knjigu koja se bavi analizom algoritama i shvati jedno: bez jako dobrog znanja matematike i statistike tu se nema sto traziti!

Najbolja literatura koju bih mogla preporuciti svakome koga problematika izracunavanja slozenosti algoritama zanima je ova knjiga Herberta Wilfa (http://www.cis.upenn.edu/%7Ewilf/AlgComp2.html) (koju mozete besplatno skinuti na ovom linku), kao i Knuthova trilogija "The art of computer programming" ili, recimo ova, vrlo popularna knjiga (http://www.amazon.com/exec/obidos/tg/detail/-/0262032937/102-9735743-1448915?v=glance).

Izbijte sebi iz glave ideju da je moguce sastavljati kvalitetne algoritme (ili procjenjivati vrijeme izvrsavanja vec postojecih) bez teoretskog znanja (uglavnom matematickog) koje je opisano u gore navedenim knjigama!

Dizajn aplikacija je jedno, analiza algoritama nesto sasvim drugo!

math_baby:rolleyes:

Nazalost vecina ljudi misli da je bitna optimizacija implementacije za postici brzinu (to su oni tipa ja pisem u ASM i to je super brzo, naravno nema veze sto je algoritam traljav :D ) ,a kljucno je izabrati/smisliti adekvatan algoritam za dati problem., optimizacija implementacije je za red velicine laksa za postizanje

TomK
11.04.2004., 23:52
Pa gledajte, cunac, i math_baby,

ja sam dao prijedlog kako bi mogli testirati performanse algoritma, koji, slozit cu se , nije idealan, ali jest nekakav, i sto je vrlo bitno, konkretan program koji bi to mogao i demonstrirati!!!

To sto ste vi dali kao odgovor na to je cista teorija od koje nitko nema nikakve koristi.

Dakle, ako ste vec toliko pametni da date negativnu ocjenu za moju ideju i konkretni program, onda izvolite, dajte vi konktretni program koji ce svatko moci copy-paste i testirati alogoritam na vas "puno bolji" nacin.

Sve dok to ne postavite na ovaj forum, sorry, ipak je sve sto pisete mlacenje prazne slame.

Lijepi pozdravi (u teoriji :) )

TomK
11.04.2004., 23:59
Imam prijedlog. A da povecas prioritet procesa i threada na real time critical sa SetPriorityClass() i SetThreadPriority() dok vrsis mjerenje inace ti drugi procesi mogu utjecati na rezultat. Naprimjer drugi proces prekine tvoj proces i izbrise ti razne nivoe cache-a u procesoru. Ne mora se dogoditi ali nije garantirano. Ovako bi to bilo manje vjerojatno.

Potpuno se slazem sa ovim sto si napisao. Radio sam neke testove vezane za cashe, i to je podrucje doista "granicno", dakle, veoma je upitno koliko mi kao programeri imamo utjecaj kako ce procesor tretirati cache memoriju.

Dakle, slazem se da bi test dao puno vjerodostojnije rezultate ukoliko bi se povecali prioriteti procesa i thread-ova.

Lijepi pozdravi,

cunac
12.04.2004., 03:37
TomK kaže:
Pa gledajte, cunac, i math_baby,

ja sam dao prijedlog kako bi mogli testirati performanse algoritma, koji, slozit cu se , nije idealan, ali jest nekakav, i sto je vrlo bitno, konkretan program koji bi to mogao i demonstrirati!!!

To sto ste vi dali kao odgovor na to je cista teorija od koje nitko nema nikakve koristi.


bas naprotiv, to je cista praksa. Da li si ikada isao optimizirati neki program koji ima 100K+ linija. Reci mi kako to radis, ja koristim profilere za frst cut i onda optimizaciju algoritma tj. po mogucnosti optimalne algoritme


Dakle, ako ste vec toliko pametni da date negativnu ocjenu za moju ideju i konkretni program, onda izvolite, dajte vi konktretni program koji ce svatko moci copy-paste i testirati alogoritam na vas "puno bolji" nacin.

Sve dok to ne postavite na ovaj forum, sorry, ipak je sve sto pisete mlacenje prazne slame.

Lijepi pozdravi (u teoriji :) )

Mozda da naucis prihvatiti kritiku kao nesto neosobno, to bi dosta pomoglo u raspravi. :)
Math ti je rekla kako se testira slozenost algoritma, koji dio nije bio jasan ?

TomK
12.04.2004., 09:29
Ma ti bi cunac ovako mogao jos 16 godina...

Kako ne shvacas da ovaj forum nije nikakva firma (pusti te price o 100k+ linija), nego mjesto gdje se razmjenjuje iskustva medju nama koji volimo programiranje, kao i code iz kojega se nesto moze nauciti.

Ja sam sa svojim malim primjerom, ako nista drugo, pokazao kako se moze mjeriti vrijeme koje thread koristi na windows platformi, i mislim da to nije glupo koristiti kao jedan od metoda za mjerenje efikasnosti koda, sto ne iskljucuje i neke naprednije tehnike optimatizacije, ali o tome ovdje nema niti mjesta niti publike za takvo sto.

Tvoji postovi, za razliku od mojih, su uvijek pokusaj negiranja tudjuh postova, bez ikakve prakticne vrijednosti, dakle, sa izuzetkom jednog ili dva posta, tvoji, a dobrim dijelom i math-ovi postovi nemaju nikakvu prakticnu i uporabnu vrijednost i vjerujem da ih nitko ne cita vise od jedan jedini puta, za razliku od nekih postova koji sadrze konkretan code, te kao takvi postaju zanimljivi svakom programeru koji se i sam dotice sa odredjenom problematikom.

Zato su tvoji postovi, ukljucujuci i ovaj zadnji, doista mlacenje prazne slame, koji ce biti zaboravljen jednakom brzinom kao sto je i procitan.

A te tvoje price o velikim projektima, mislim da bi konacno morao shvatiti da to uopce nije relevantno na ovakvom jednom forumu, i moderatori bi po mome misljenju trebali izbaciti vecinu tvojih postova jer nemaju nikave veze sa topicom, niti kakvu uporabnu vrijednost.

Lijepi pozdravi (u teoriji ):D

bizz
12.04.2004., 11:14
TomK kaže:
Kako ne shvacas da ovaj forum nije nikakva firma (pusti te price o 100k+ linija), nego mjesto gdje se razmjenjuje iskustva medju nama koji volimo programiranje, kao i code iz kojega se nesto moze nauciti.

U tu svrhu, prebacujem klasu LinearSort sa topica math_baby ovamo.

Shadowman, ova klase dokazuje da je moguce linearno sortirati podatke bez poznavanja podrucja u kojem su ulazni podaci.


#include <iostream.h>
#include <stdlib.h>
#include <time.h>

typedef unsigned int UINT;

class LinearSort
{
void sort( UINT* data, UINT len, UINT flag )
{
UINT head = 0, tail = len, swap;

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

data[tail] = data[head];

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

flag >>= 1;

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

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

public:

void normal( UINT* data, UINT len )
{
sort( data, len, 0x80000000 );
}

UINT unique( UINT* data, UINT len )
{
sort( data, len, 0x80000000 );

UINT ret = 1;

for( UINT i=1; i<len; i++ )
{
if( data[i] != data[ret-1] )
{
data[ret++] = data[i];
}
}

return ret;
}
};

int main()
{
const UINT size = 1000000;

UINT* data = new UINT[size];

srand( time(NULL) );

for( UINT i=0; i<size; i++ )
{
data[i] = rand()*rand();
}

LinearSort sort;

sort.normal( data, size );

for( i=0; i<size; i++ )
{
cout << data[i] << endl;
}

delete data;

return 0;
}

TomK
12.04.2004., 14:24
Evo bizz-ov code integriran sa test programom. Masina na koju sam testirao je Celeron 500 Mhz, 192 MB Ram. Velicina arraya je 1.000.000


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

#define SIZE 1000000

class LinearSort
{
void sort( UINT* data, UINT len, UINT flag )
{
UINT head = 0, tail = len, swap;

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

data[tail] = data[head];

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

flag >>= 1;

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

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

public:

void normal( UINT* data, UINT len )
{
sort( data, len, 0x80000000 );
}

UINT unique( UINT* data, UINT len )
{
sort( data, len, 0x80000000 );

UINT ret = 1;

for( UINT i=1; i<len; i++ )
{
if( data[i] != data[ret-1] )
{
data[ret++] = data[i];
}
}

return ret;
}
};

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)

srand(time(NULL));

for(int i = 0; i < SIZE; i++ )
{
pIntArray[i] = rand() * rand();
}

return 0;
}

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

// ovdje code koji sortiara array (pIntArray)

LinearSort sort;
sort.normal(pIntArray, SIZE);

return 0;
}

A ovo je rezultat:

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 : 3
Milliseconds : 364

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

Lijepi pozdravi

P.S. Testirao sam algoritam na malim velicinama (SIZE = 200) i ispisivao rezultat, i algoritam radi bez greske.

bizz
12.04.2004., 14:32
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
12.04.2004., 14:36
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
12.04.2004., 20:15
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
12.04.2004., 20:17
Da, samo sortiranje je zapravo brže 15 puta, ali kod mene ima restrikcija da postoji točno određen range.

Shadowman
12.04.2004., 20:23
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
12.04.2004., 20:25
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
12.04.2004., 20:30
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
12.04.2004., 21:09
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
12.04.2004., 21:23
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
12.04.2004., 21:39
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
12.04.2004., 22:02
Evo prvi test na topicu math_baby (uz izbacivanje duplikata):

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

Shadowman
12.04.2004., 22:35
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
12.04.2004., 22:37
Pardon, bar preko 4 GB.

bizz
12.04.2004., 22:51
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
12.04.2004., 23:55
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
13.04.2004., 00:01
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
13.04.2004., 00:11
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
13.04.2004., 10:10
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
13.04.2004., 10:35
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
13.04.2004., 13:23
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)?

cunac
13.04.2004., 13:41
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
13.04.2004., 13:53
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
13.04.2004., 14:18
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 :D
Mozda imas jako brzi comp :) , hocu onda i ja jedan takav :W

cunac
13.04.2004., 14:23
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 :D
Mozda imas jako brzi comp :) , hocu onda i ja jedan takav :W

me sucks kada je u pitanju matematika
:bljak:

bizz
13.04.2004., 15:18
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
13.04.2004., 15:20
Pogledaću kod ponovo kasnije da vidim zašto se ruši. Kod mene se nije rušio.

bizz
13.04.2004., 15:21
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
13.04.2004., 15:24
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
13.04.2004., 15:25
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
13.04.2004., 15:28
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
13.04.2004., 16:10
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
13.04.2004., 16:17
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
13.04.2004., 16:21
Ako hoćeš, možeš skinuti GCC za Windows odavde.

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

Shadowman
13.04.2004., 16:53
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
13.04.2004., 17:14
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
13.04.2004., 17:21
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
13.04.2004., 18:05
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
13.04.2004., 18:16
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 :D

bizz
13.04.2004., 18:31
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 :D

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

Probam jos veceras. Rezultat cemo vidjeti sutra. Pozdrav.

cunac
13.04.2004., 18:49
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

Shadowman
14.04.2004., 00:09
TomK kaže:
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.

Ovo je sasvim logično, jer kod ovakvog inputa sam quicksort algoritam pravi najgori mogući split, dijeli niz na prazan, pivot i sve ostalo.

bizz, zašto ne bi napravio jedan pass kroz array i našao najveći broj. Onda možeš preskočiti sve bits do najvišeg bita najvećeg broja. Na primjer, najveći broj u nizu je 2^20. Odmah možeš početi s dvadesetim bitom, a sve ostale preskočiš.

bizz
14.04.2004., 12:18
Novi BizzSort je tu. Ispravljene su greske u algoritmu i algoritam je optimiziran (Cunac). Evo rezultata uz istovjetan input i ispisivanje prvih 10 i zadnjih 10 elemenata sortiranog niza:


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

In user mode :
Seconds : 0
Milliseconds : 971

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

In user mode :
Seconds : 6
Milliseconds : 349

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

In user mode :
Seconds : 5
Milliseconds : 858

31
455
520
799
1446
1535
1538
1643
1801
1836
----------------------
2147449880
2147450164
2147450298
2147450418
2147450517
2147450575
2147450681
2147450724
2147450739
2147450814



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

In user mode :
Seconds : 0
Milliseconds : 941

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

In user mode :
Seconds : 6
Milliseconds : 419

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

In user mode :
Seconds : 5
Milliseconds : 838

223
287
548
740
783
1048
1268
1679
1771
1844
----------------------
2147449636
2147449810
2147449897
2147449905
2147449980
2147450039
2147450136
2147450174
2147450190
2147450466


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

In user mode :
Seconds : 0
Milliseconds : 981

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

In user mode :
Seconds : 6
Milliseconds : 379

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

In user mode :
Seconds : 5
Milliseconds : 848

471
642
868
1003
1009
1151
1530
1545
1558
1641
----------------------
2147449876
2147449907
2147449941
2147450102
2147450137
2147450142
2147450230
2147450789
2147450835
2147450850



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

In user mode :
Seconds : 1
Milliseconds : 932

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

In user mode :
Seconds : 13
Milliseconds : 539

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

In user mode :
Seconds : 12
Milliseconds : 337

49
103
191
228
259
282
442
464
606
745
----------------------
2147450049
2147450150
2147450287
2147450362
2147450444
2147450559
2147450611
2147450621
2147450728
2147450752


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

In user mode :
Seconds : 1
Milliseconds : 952

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

In user mode :
Seconds : 13
Milliseconds : 349

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

In user mode :
Seconds : 12
Milliseconds : 287

35
44
92
99
208
237
315
487
524
662
----------------------
2147450153
2147450233
2147450256
2147450321
2147450373
2147450507
2147450556
2147450740
2147450758
2147450876


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

In user mode :
Seconds : 1
Milliseconds : 942

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

In user mode :
Seconds : 13
Milliseconds : 479

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

In user mode :
Seconds : 12
Milliseconds : 367

134
171
245
405
443
475
476
494
510
625
----------------------
2147449788
2147449848
2147449899
2147449918
2147449972
2147450321
2147450577
2147450579
2147450673
2147450853

bizz
14.04.2004., 12:24
Kod za testiranje:


#include <iostream>
#include <stdlib.h>
using namespace std;

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

#define SIZE 8000000

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


class BizzSort
{
void sort( UINT* data, UINT len, UINT flag )
{
UINT head = 0, tail = len, swap;

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

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

data[head++] = swap;

break;
}
}
}
else
head++;
}

if( flag >>= 1 )
{
if( head > 3 )
{
sort( data, head, flag );
}
else switch( head )
{
case 3:

swap = data[0];

if( swap > data[1] )
{
data[0] = data[1];

data[1] = swap;
}
else
swap = data[1];

if( swap > data[2] )
{
data[1] = data[2];

data[2] = swap;
}
else
break;

case 2:

swap = data[0];

if( swap > data[1] )
{
data[0] = data[1];

data[1] = swap;
}
}

if( (len-tail) > 3 )
{
sort( data+head, len-tail, flag );
}
else switch( (len-tail) )
{
case 3:

swap = data[head];

if( swap > data[head+1] )
{
data[head] = data[head+1];

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

if( swap > data[head+2] )
{
data[head+1] = data[head+2];

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

case 2:

swap = data[head];

if( swap > data[head+1] )
{
data[head] = data[head+1];

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

public:

void normal( UINT* data, UINT len )
{
sort( data, len, 0x80000000 );
}

UINT unique( UINT* data, UINT len )
{
sort( data, len, 0x80000000 );

UINT ret = 1;

for( UINT i=1; i<len; i++ )
{
if( data[i] != data[ret-1] )
{
data[ret++] = data[SIZE-i-1];
}
}

return ret;
}
};

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

BizzSort bizz;

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

pIntArray = new UINT[SIZE];
pIntArray2 = 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[%d] times\n", SIZE);
printf("--------------------\n");
PrintTimes(&kernelTime, &userTime);

memcpy( pIntArray2, pIntArray, SIZE*sizeof(UINT) );

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

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

for( int i=0; i<10; i++ )
{
cout << pIntArray2[i] << endl;
}

cout << "----------------------" << endl;

for( int i=SIZE-10; i<SIZE; i++ )
{
cout << pIntArray2[i] << endl;
}

delete [] pIntArray2;
delete [] pIntArray;

return 0;
}

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)

srand(time(NULL));

for(int i = 0; i < SIZE; i++ )
{
pIntArray[i] = (rand()<<16) + rand();
}

return 0;
}

int cmp_u32(const void* e1, const void* e2)
{
const UINT* p1 = (const UINT*)e1;
const UINT* p2 = (const UINT*)e2;
if(*p1 == *p2)
return 0;
else if(*p1 < *p2)
return -1;
else
return 1;
}

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

// ovdje code koji sortiara array (pIntArray)

quicksort(pIntArray, SIZE);
// std::qsort(pIntArray, SIZE, sizeof(UINT), cmp_u32);

return 0;
}

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

// ovdje code koji sortiara array (pIntArray)

bizz.normal(pIntArray, SIZE);

return 0;
}