Forum.hr

Natrag   Forum.hr > Informatička tehnologija > Za napredne korisnike > Programiranje
Korisničko ime
Lozinka

Programiranje Za programere i one koji to žele postati ...

Odgovor
 
Tematski alati Opcije prikaza
Old 10.04.2004., 17:01   #1
Shadowman
Mladić
 
Shadowman Avatar
 
Registracija: Nov 2002.
Lokacija: Chicago
Postova: 5,165
Brzo sortiranje

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?
__________________
Ja sam mladić u najboljim godinama i čovjek za sutra, a nekad sam bio sretno dijete. U mojoj općini problema nema, jer rade veze i poznanstva.
Shadowman is offline  
Odgovori s citatom
Old 10.04.2004., 17:09   #2
TomK
Registrirani korisnik
 
Registracija: Dec 2002.
Postova: 1,993
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?
TomK is offline  
Odgovori s citatom
Old 10.04.2004., 17:55   #3
Shadowman
Mladić
 
Shadowman Avatar
 
Registracija: Nov 2002.
Lokacija: Chicago
Postova: 5,165
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.
__________________
Ja sam mladić u najboljim godinama i čovjek za sutra, a nekad sam bio sretno dijete. U mojoj općini problema nema, jer rade veze i poznanstva.
Shadowman is offline  
Odgovori s citatom
Old 10.04.2004., 18:41   #4
TomK
Registrirani korisnik
 
Registracija: Dec 2002.
Postova: 1,993
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,
TomK is offline  
Odgovori s citatom
Sponsored links
Advertisement
 
Advertisement
Old 10.04.2004., 18:42   #5
cunac
XP agile freak
 
Registracija: Dec 2002.
Lokacija: Canada GTA
Postova: 2,245
Quote:
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
cunac is offline  
Odgovori s citatom
Old 10.04.2004., 18:52   #6
Shadowman
Mladić
 
Shadowman Avatar
 
Registracija: Nov 2002.
Lokacija: Chicago
Postova: 5,165
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.
__________________
Ja sam mladić u najboljim godinama i čovjek za sutra, a nekad sam bio sretno dijete. U mojoj općini problema nema, jer rade veze i poznanstva.
Shadowman is offline  
Odgovori s citatom
Old 10.04.2004., 21:12   #7
TomK
Registrirani korisnik
 
Registracija: Dec 2002.
Postova: 1,993
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):

Kod:
#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.
TomK is offline  
Odgovori s citatom
Old 10.04.2004., 21:27   #8
Shadowman
Mladić
 
Shadowman Avatar
 
Registracija: Nov 2002.
Lokacija: Chicago
Postova: 5,165
Za sve integer vrijednosti treba ti 8 GB.
__________________
Ja sam mladić u najboljim godinama i čovjek za sutra, a nekad sam bio sretno dijete. U mojoj općini problema nema, jer rade veze i poznanstva.
Shadowman is offline  
Odgovori s citatom
Old 10.04.2004., 22:01   #9
TomK
Registrirani korisnik
 
Registracija: Dec 2002.
Postova: 1,993
Quote:
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,
TomK is offline  
Odgovori s citatom
Old 10.04.2004., 22:03   #10
bizz
Under construction
 
bizz Avatar
 
Registracija: May 2003.
Postova: 1,016
Kod:
/************************************************ 
** 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;
}
:
bizz is offline  
Odgovori s citatom
Old 10.04.2004., 22:08   #11
Shadowman
Mladić
 
Shadowman Avatar
 
Registracija: Nov 2002.
Lokacija: Chicago
Postova: 5,165
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.
__________________
Ja sam mladić u najboljim godinama i čovjek za sutra, a nekad sam bio sretno dijete. U mojoj općini problema nema, jer rade veze i poznanstva.
Shadowman is offline  
Odgovori s citatom
Old 10.04.2004., 22:12   #12
bizz
Under construction
 
bizz Avatar
 
Registracija: May 2003.
Postova: 1,016
Quote:
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.
bizz is offline  
Odgovori s citatom
Old 10.04.2004., 22:25   #13
Shadowman
Mladić
 
Shadowman Avatar
 
Registracija: Nov 2002.
Lokacija: Chicago
Postova: 5,165
Š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).
__________________
Ja sam mladić u najboljim godinama i čovjek za sutra, a nekad sam bio sretno dijete. U mojoj općini problema nema, jer rade veze i poznanstva.
Shadowman is offline  
Odgovori s citatom
Old 10.04.2004., 22:29   #14
bizz
Under construction
 
bizz Avatar
 
Registracija: May 2003.
Postova: 1,016
Quote:
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.
bizz is offline  
Odgovori s citatom
Old 10.04.2004., 22:34   #15
Shadowman
Mladić
 
Shadowman Avatar
 
Registracija: Nov 2002.
Lokacija: Chicago
Postova: 5,165
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.
__________________
Ja sam mladić u najboljim godinama i čovjek za sutra, a nekad sam bio sretno dijete. U mojoj općini problema nema, jer rade veze i poznanstva.
Shadowman is offline  
Odgovori s citatom
Old 10.04.2004., 22:38   #16
Shadowman
Mladić
 
Shadowman Avatar
 
Registracija: Nov 2002.
Lokacija: Chicago
Postova: 5,165
Uh, pardon, može sizeof.
__________________
Ja sam mladić u najboljim godinama i čovjek za sutra, a nekad sam bio sretno dijete. U mojoj općini problema nema, jer rade veze i poznanstva.
Shadowman is offline  
Odgovori s citatom
Old 10.04.2004., 22:38   #17
bizz
Under construction
 
bizz Avatar
 
Registracija: May 2003.
Postova: 1,016
Quote:
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 is offline  
Odgovori s citatom
Old 10.04.2004., 22:39   #18
bizz
Under construction
 
bizz Avatar
 
Registracija: May 2003.
Postova: 1,016
Template je koristen kako bi ulazni podaci mogli bi signed ili unsigned int ili char, kao i short i long varijante.
bizz is offline  
Odgovori s citatom
Old 10.04.2004., 22:41   #19
bizz
Under construction
 
bizz Avatar
 
Registracija: May 2003.
Postova: 1,016
Sortiranje je linearno, odnosno brzina sortiranja ovisi samo o kolicini ulaznih podataka, ali ne i njihovom sadrzaju.
bizz is offline  
Odgovori s citatom
Old 10.04.2004., 22:44   #20
Shadowman
Mladić
 
Shadowman Avatar
 
Registracija: Nov 2002.
Lokacija: Chicago
Postova: 5,165
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š
__________________
Ja sam mladić u najboljim godinama i čovjek za sutra, a nekad sam bio sretno dijete. U mojoj općini problema nema, jer rade veze i poznanstva.
Shadowman is offline  
Odgovori s citatom
Sponsored links
Advertisement
 
Advertisement
Odgovor


Tematski alati
Opcije prikaza

Pravila postanja
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smajlići su On
[IMG] kôd je Off
HTML kôd je Off





Sva vremena su GMT +1. Trenutno vrijeme je: 09:15.



Powered by vBulletin Version 3.8.4 (hrvatski)
Copyright ©2000 - 2014, Jelsoft Enterprises Ltd.
Site content ©1999-2009 Forum.hr
Ad Management by RedTyger