Brzo sortiranje

[Shadowman]

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]

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]

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]

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]

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]

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]

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]

Za sve integer vrijednosti treba ti 8 GB.

[TomK]

Za sve integer vrijednosti treba ti 8 GB.

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]

/************************************************ 
** Copyright (C) 2004 [email protected]. 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]

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.

[bizz]

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]

Š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]

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]

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]

Uh, pardon, može sizeof.

[bizz]

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]

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

[bizz]

Sortiranje je linearno, odnosno brzina sortiranja ovisi samo o kolicini ulaznih podataka, ali ne i njihovom sadrzaju.

[Shadowman]

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š