reservera stort int-fält?

Jag har reserverat ett fält för 25000 heltal, dvs

int* values = new int[25000]

När jag skall utföra sorteringsalgoritmen quicksort på listan då den är fylld med sorterade värden verkar algoritmen bara godta en lista som är 9592 heltal stor, värdet varierar med något heltal upp eller ned beroende på testtillfälle. Vid större listor slutar quicksort att arbeta utan att ge någon indikation på något fel.
Verkar vara något minnesproblem trodde jag men en kraftfullare dator med mer ram hade samma gräns för vad quicksort ville klara av.

Någon som har erfarenheter av quicksort på redan sorterade värden? Jag vet att quicksort är allmänt dålig på redan sorterade värden, men det skall bara ha betydelse för tiden och inte huruvida den utför uppgiften alls.

Jag använder rekursion i algoritmen, ingen explicit stack.

Bespara mig från frågor om varför jag vill sortera en sorterad lista. :)

Storleken ska inte ha nån annan inverkan än tiden. Iaf så länge storleken inte överskrider de fysiska möjligheterna. Så bara av det du skrev kan jag inte se några problem. Hur ser koden ut? Är det en egen qsort eller använder du den medföljande? Hur ser resultatet ut om du kör med mindre allokerat fält?

För att sortera i C++, använd std::sort som finns i <algorithm>

int values[10000];
values[34] = 23;
values[1012] = 80;
std::sort(values, values+10000);

Annars får du nog ta och posta koden för din sökfunktion om vi ska kunna hjälpa dig.

Re: reservera stort int-fält?

FredrikF skrev:

Men kraftfullare dator med mer ram hade samma gräns för vad quicksort ville klara av.

Om det är stacken som är begränsningen så är väl den samma oberoende på vilken dator programmet körs. Stackstorleken väljer man (iaf i CodeWarrior) när man kompilerar programmet.

Dock ska ju stacken inte ta slut vid quicksort för det är väl O(log n) rekursiva anrop om jag inte minns helt fel.

PeW skrev:

Storleken ska inte ha nån annan inverkan än tiden. Iaf så länge storleken inte överskrider de fysiska möjligheterna. Så bara av det du skrev kan jag inte se några problem. Hur ser koden ut? Är det en egen qsort eller använder du den medföljande? Hur ser resultatet ut om du kör med mindre allokerat fält?

Det är en egen implementering. Denna är långt ifrån optimal, till exempel så tilldelar jag pivot värdet till höger. Detta resulterar ju i dess worst case när listan redan är sorterad, men något resultat skall ja ju få på alla storlekar på listan.

void qs(int begin, int end, int* a)
{
	int i, j, v;
	if(begin < end){
		i = begin - 1;
		j = end;
		v = a[end];
		for(;;){
			while(a[++i] < v);
			while(a[--j] > v);
			if(i >= j) 
				break;
			swap(a[i], a[j]);	
		}
		swap(a[i], a[end]);
		qs(begin, i - 1, a);
		qs(i + 1, end, a);
		
	}
	
}

jag anropar funktionen ovan i följande funktion som jag i sin tur anropar i main. Förfarandet går utmärkt vid mindre listor, så det är inget fel i anropen av funktionerna.

int* quicksort(int* a, int noofelements){
	qs(0, noofelements-1, a);
	cout << "quicksort klar" << endl;
	return a;
}

Jag har lyckats få quicksort att fungera på en lista med 9589 element OCH en även lista på 9592 element vid olika testtillfällen.

Resultatet av algoritmen när den inte fungerar är att den stannar efter ett antal rekursioner, den verkar aldrig anropa sig själv för sorterar den högra partitionen (rätt självklart eftersom listan är sorterad och jag har valt höger som pivot).

Jag har prövat fler implementeringar av quicksort. Alla med samma resultat, max ca 9500 element.

Algoritmen fungerar på slumpade värden samt när alla värden är identiska. Den fungerar inte när elementen är omvänt sorterade heller.

Re: Re: reservera stort int-fält?

Sang-drax skrev:

Dock ska ju stacken inte ta slut vid quicksort för det är väl O(log n) rekursiva anrop om jag inte minns helt fel.

N^2 i värsta fall. N*LogN i bästa fall.

Det tror jag inte på.
Du tänker på tiden. Rekursionsdjupet är något annat.

Fast jag skrev inte helt rätt heller, i bästa fall är djupet O( log n ), men det kan faktiskt också vara O( n ) i västa fall (n-1 för att vara exakt).

Efter lite mer analysernade av algoritmen verkar det som att ju mer bearbetning som sker i algoritmen desto färre sorterade element kan den hantera.

Jag lade till två testutskrifter i den yttre loopen i quicksort. Dvs

int x = 0;
void qs(int begin, int end, int* a){
	int i, j, v;
	if(end > begin){
		i = begin - 1;
		j = end;
		v = a[end];
		for(;;){
			while(a[++i] < v);
			while(a[--j] > v);
			if(i >= j) 
				break;
			swap(a[i], a[j]);	
		}
		swap(a[i], a[end]);
		cout << "vänster partition------->#" << x++ << endl;
		qs(begin, i - 1, a);
		cout << "<-------höger partition  #" << x++ << endl;
		
		qs(i + 1, end, a);
	}
}

Detta medförde att algoritmen slutade fungera vid 8912 st element. Dvs, ungefär 700 element lägre än utan utskrifter.

En ökning av algoritmens komplexitet sänker dess tolerans för hur många element den kan klara av. Vad menas? Vilken slutsats kan dras?

Du skriver att programmet slutar fungera. Vad menar du med det? Är det att programmet terminerar i förtid eller att programmet står och tuggar utan respons?

En ökning av algoritmens komplexitet sänker dess tolerans för hur många element den kan klara av. Vad menas? Vilken slutsats kan dras?

Då du skriver att det fungerar utmärkt med mindre antal element i listan kan man undra om systemet inte vill släppa ifrån sig tillräckligt med minne?
Har du testat samma kod i nån annan kompilator och/eller en annan plattform?

PeW skrev:

Du skriver att programmet slutar fungera. Vad menar du med det? Är det att programmet terminerar i förtid eller att programmet står och tuggar utan respons?

En ökning av algoritmens komplexitet sänker dess tolerans för hur många element den kan klara av. Vad menas? Vilken slutsats kan dras?

Då du skriver att det fungerar utmärkt med mindre antal element i listan kan man undra om systemet inte vill släppa ifrån sig tillräckligt med minne?
Har du testat samma kod i nån annan kompilator och/eller en annan plattform?

Programmet terminerar i förtid. Dock utan klagomål på minnesresurs eller array-out-of-bounds eller liknande, med andra ord tillsynes gracefully. Jag har inte haft möjlighet att pröva att kompilera på annan plattform eller med annan kompilator. Om någon vänlig själ har tid över är jag tacksam om jag får algoritmen testad på något annat än Visual c++ i WindowsXP.

Jag kompilerade med g++ (på Linux) och körde programmet utan problem. Dels tryckte jag in värden från 10000 och ned till noll - vilket ska innebära att ordningen ska vändas. Sen gjorde jag samma sak med stigande tal (vilket blir detsamma som redan sorterat). För att testa gränser så ökade jag på med en nolla till 100 000 element och det fungerade det med - om än att det tog några sekunder längre tid (366MHz /128Mb ram)

Så jag antar att dina problem är visual c++ relaterat på nåt sätt :l
(Kan ju vara nån optimerings flagga eller liknande som du behöver slå av)

PeW skrev:

Jag kompilerade med g++ (på Linux) och körde programmet utan problem. Dels tryckte jag in värden från 10000 och ned till noll - vilket ska innebära att ordningen ska vändas. Sen gjorde jag samma sak med stigande tal (vilket blir detsamma som redan sorterat). För att testa gränser så ökade jag på med en nolla till 100 000 element och det fungerade det med - om än att det tog några sekunder längre tid (366MHz /128Mb ram)

Så jag antar att dina problem är visual c++ relaterat på nåt sätt :l
(Kan ju vara nån optimerings flagga eller liknande som du behöver slå av)

Ok, tack för dina tester. Ska titta lite bland kompileringsinställningarna i visual.

PeW skrev:

Jag kompilerade med g++ (på Linux) och körde programmet utan problem. Dels tryckte jag in värden från 10000 och ned till noll - vilket ska innebära att ordningen ska vändas. Sen gjorde jag samma sak med stigande tal (vilket blir detsamma som redan sorterat). För att testa gränser så ökade jag på med en nolla till 100 000 element och det fungerade det med - om än att det tog några sekunder längre tid (366MHz /128Mb ram)

Så jag antar att dina problem är visual c++ relaterat på nåt sätt :l
(Kan ju vara nån optimerings flagga eller liknande som du behöver slå av)

Jag ställde om från win32 debug mode till win32 release mode
vilket höjde ribban till ca 30000 element. Fortfarande verkar det vara någon begränsning.

Fortfarande verkar det vara någon begränsning.

Onekligen. Eller rättare sagt så skalar du ju bort en massa överflödig information från objektkoden om du väljer releasemode vilket kanske minskar symptomen. Men 'felet' kvarstår. Kolla efter flaggor/växlar för kompilatorn (har för mig att det ligger angivet något eller några som default) och kontrollera vad de gör.

Sang-drax skrev:

För att sortera i C++, använd std::sort som finns i <algorithm>

int values[10000];
values[34] = 23;
values[1012] = 80;
std::sort(values, values+10000);

Motsvarar denna sort-algoritm quicksort?

FredrikF skrev:

Motsvarar denna sort-algoritm quicksort?

Ej definerat i standarden, men quicksort är ju en bra implementering för de flesta.
En C++-kompilator för kvantdatorer skulle nog använda sig av någon form av kvantsortering som körs i O(1) tid. :)

Sang-drax skrev:

En C++-kompilator för kvantdatorer skulle nog använda sig av någon form av kvantsortering som körs i O(1) tid. :)

men bubble sort då? den är ju snabb! ;)

FredrikF skrev:

Sang-drax skrev:

En C++-kompilator för kvantdatorer skulle nog använda sig av någon form av kvantsortering som körs i O(1) tid. :)

men bubble sort då? den är ju snabb! ;)

Jag vet inte om du är ironisk nu, men här finns en demo som åskådliggör skillnaderna i sorteringshastighet: http://java.sun.com/applets/jdk/1.0/demo/SortDemo/example1.html