Kleinster Wert aus Array

GeorgeHomes

array[10 000}

linear 9 999 durchläufe
quicksort 100 durchläufe

Du redest die ganze Zeit über die Durchläufe, und ich über die Vergleiche. Nur weil ich weniger durchläufe habe, heist das ja nicht, das es schneller ist. Es kommt ja darauf an, was in jedem Durchlauf gemacht werden muß. In jedem der 9999 Durchläufe der linearen Methode muß ja nur ein Wert mit dem anderen verglichen, und eventuell getauscht werden.

Ich habe jetzt auch mal einen kleinen Code geschrieben, der die Geschwindigkeit der linearen Suche mit der des Quicksorts (ohne suche) vergleicht.

#include <windows.h>
#include <stdlib.h>
#include <stdio.h>
#include <time.h>
#include <conio.h>

void Min(int* pArray, int iElementCount, int &iOutMin, int &iOutMinPos)
{
	iOutMinPos = 0;
	iOutMin = pArray[0];
	for (int i=1; i<iElementCount; i++)
	{
		if (pArray[i]<iOutMin)
		{
			iOutMin = pArray[i];
			iOutMinPos = i;
		}
	}
}

void QuickSort(int* pData, int iLow, int iHigh)
{
	int i=iLow;
	int j=iHigh;
	int x=pData[(iLow+iHigh)/2];

	// Aufteilung
	while (i<=j)
	{
		while (pData[i]<x) i++;
		while (pData[j]>x) j--;

		if (i<=j)
		{
			int iTemp = pData[i];
			pData[i] = pData[j];
			pData[j] = iTemp;
			i++;
			j--;
		}
	}

	if (iLow<j) QuickSort(pData, iLow, j);
	if (i<iHigh) QuickSort(pData, i, iHigh);
}

#define TESTCOUNT		100
#define ARRAYSIZE		100000

int main(int argc, char* argv[])
{
	srand( (unsigned)time( NULL ) );

	LARGE_INTEGER avgsort;
	LARGE_INTEGER avgsearch;

	avgsort.QuadPart = 0;
	avgsearch.QuadPart = 0;

	for (int i=0;i<TESTCOUNT;i++)
	{
		int pTest[ARRAYSIZE];
		for (int i=0; i<ARRAYSIZE; i++) pTest[i] = rand();

		LARGE_INTEGER time1;
		LARGE_INTEGER time2;
		LARGE_INTEGER sorttime;
		LARGE_INTEGER searchtime;

		QueryPerformanceCounter(&time1);
		int iMin;
		int iMinPos;
		Min(pTest, ARRAYSIZE, iMin, iMinPos);
		QueryPerformanceCounter(&time2);

		searchtime.QuadPart = time2.QuadPart - time1.QuadPart;
		avgsearch.QuadPart+=searchtime.QuadPart;

		QueryPerformanceCounter(&time1);
		QuickSort(pTest, 0, ARRAYSIZE-1);
		QueryPerformanceCounter(&time2);

		sorttime.QuadPart = time2.QuadPart - time1.QuadPart;
		avgsort.QuadPart+=sorttime.QuadPart;
	}

	avgsearch.QuadPart/=TESTCOUNT;
	avgsort.QuadPart/=TESTCOUNT;

	int iAvgSearch = avgsearch.QuadPart;
	int iAvgSort = avgsort.QuadPart;

	printf("Der Suchvorgang hat im Durchschnitt %i gedauert", iAvgSearch);
	printf("\nDer Sortiervorgang hat im Durchschnitt %i gedauert", iAvgSort);

	getch();

	return 0;
}

Ich habs mal durchlaufen lassen und bei mir kommt folgendes Ergebnis raus.

Der Suchvorgang hat im Durchschnitt 1336 gedauert
Der Sortiervorgang hat im Durchschnitt 84614 gedauert

Also ist die lineare Suche im Durschnitt 63x schneller als der Quicksort.

Es wurde ja auch schon gesagt, das sich der Quicksort vor allem lohnen würde, wenn man das ganze öfter machen muß und den Quicksort nur dann ausführt, wenn sich der Array geändert hat. Das ist aber irgendwie auch blödsinn, denn wenn sich der Array nicht verändert hat, hat sich der kleinste Wert mit Sicherheit auch nicht verändert.

tobis79211

Hi, ich möchte mich garnicht so sehr in Euren Kleinkrieg einmischen, aber ich würde gerne mal ein kleines Rechenbeispiel mit 2 Möglichkeiten machen... An sich möchte ich sagen, daß ich Mathe + Informatik studiere, als schon denke eine Ahnung über Exp.-Funktionen etc zu haben! Ich würde mich auch sehr freuen, wenn ihr Euch durchlest was ich schreibe, bevor ich irgendwie angegriffen werde:

- Ich geh hier einfach mal von 200 Elementen aus. Wie wir alle einsehen ist das leicht auf das 200*200-Problem übertragbar! Wer es nicht einsieht sollte anfangen zu studieren!

ok, dann los:

- Möglichkeit a) lineare Suche (NICHT "linear Sortieren", was immer das ist!)

Dies bedeutet, daß jedes Element mit dem "momentan kleinsten" verglichen wird, ergo: O(n) Vergleiche, also 200... eingesehen? denke schon!

- Möglichkeit b) QSort

Das Feld wird mit QSort sortiert und man merkt sich den kleinsten Wert!
So, zur Info: Welche Laufzeit hat QSort? O(nlogn), das kennen wir ja alle, nicht? Gut, dann setzen wir das mal ein: 200*log(200)=460.

Nun interpretieren wir das alle mal, bevor wir uns beschimpfen:

Vorteil von QSort ist, daß das Feld danach sortiert ist, man kann also weiter beliebige Werte in O(logn) suchen. Das ist ne tolle Sache, da der Aufwand bei n Elementen dann insgesamt O(nlogn + nlogn)=O(2nlogn), also natürlich kleiner als O(n*n)=O(n^2) bei linearer Suche ist! Bei NUR EINEM Element braucht man natürlich aber nlogn Vergleiche, wohingegen man bei linearer Suche nur n Vergleiche braucht!

Ergo: für die Suche nach EINEM kleinsten Element ist die lineare SUCHE am schnellsten! QSort benötigt O(logn-1) mal mehr Aufwand. Wird die Suche öfters wiederholt, dann sollte man natürlich wie beschrieben QSort verwenden und dann logarithmisch Suchen!

Gruß, Tobias

@newkid: O(n) ist weniger als O(n log n)

GeorgeHomes

@tobis79211
Da kann ich nur zu 100% zustimmen. Wie du schon sagtest, wenn man mehrere Werte suchen müsste hätte man mit QSort in Verbindung mit einer Binären suche ganz klar die bessere Lösung.

Normalerweise versuche ich bei Diskussionen auch sachlich zu bleiben und niemanden persönlich anzugreifen, aber da gibt es leider ein Problem. Was mich am meisten in Rage bringt, ist wenn ich für etwas zusammengeschissen werde, woran ich meiner Ansicht nach (Stimmt ja mit sicherheit nicht immer;)) nicht schuld bin. Oder eben wenn ich mich persönlich angegriffen Fühle, obwohl ich denke im Recht zu sein.

as schrieb:

@newkid: O(n) ist weniger als O(n log n)

stimmt

deswegen lag ich auch völlig falsch, da ich es mit logn verwechselt habe, sorry an allen. also bitte nicht sauer sein.

GeorgeHomes

@newkid
Ich entschuldige mich auch nochmal bei dir. Ich hätte nicht gleich ausfallend oder Gereizt werden müssen, zumal du ja nur (wie es bei einer diskussion nunmal so ist;)) deine Meinung vertreten hast.

SirLant

Um ein kleinstes Element zu finden hat man in einer unsortierten Liste keine andere Wahl als alle Elemente zu prüfen und ein Quicksort der Rekursiv oder Iterativ arbeitet hat _immer_ mehr Overhead als 2For-Schleifen und ist somit absolut ungeeignet für eine minimalistische Suche, da die 2For-Schleifen wie der Quicksort alle Elemente durchgehen müssen und prüfen und das mit _weniger_ Code

Ist einfach so, bei unsortierten Feldern ist lineares Suchen der _einzige_ Weg um den kleinsten Wert zu finden.

/Edit:

Zu dem letzten Satz: der schnellste, weil alles andere zusätzlichen overhead bedeutet und auch alles überprüfen muss

estartu

Also, regt euch doch nicht so über die Threadzahl auf...

Ich hab doch geschrieben, dass ich davon keine Ahnung habe und das nur so eine Idee ist.

Cpp_Junky

Hehehe, da hab ich hier ja einen richtigen Flamewars in Gang gesetzt mit meiner Frage

Um die Frage nach dem schnelleren Algorithmus zu lösen, hab ich mir mal die Mühe gemacht, einen "Benchmark" durchzuführen.

Vorher hab ich aber die "2-for-schleifen Suche" noch etwas getuned
Und zwar sieht die jetzt so aus:

int* pOffset = &Array[0][0];
	int nMinVal(9999999);
	int* pMinField;

	while (pOffset != &Array[199][200])
	{
		if (*pOffset < nMinVal)
		{
			nMinVal = *pOffset;
			pMinField = pOffset;
		}
		pOffset++;
	}

	int nKleinster = nMinVal;	// Kleinster Wert

Dann hab ich die qsort-Variante und den Code oben jeweils 20 Sekunden lang immer wieder aufgerufen und dann einfach die geschafften Aufrufe pro Sekunde errechnet.
Ergebnis (auf einem P4 mit 2Ghz im Debugmodus):
Quicksort: ~ 140 Aufrufe / Sek
Aufgemotzte Linearsuche: ~7500 Aufrufe / Sek

Mit Quicksort ist es also seltsamerweise beträchtlich langsamer.

das_brot

Ich nehm' mal an, das ist, weil qsort das Array auch gleich sortiert, und die lineare Suche sich nur den tiefsten Wert "merkt".
wie schon weiter oben gesagt, kannst du aber bei mehrmaliger Verwendung (2. kleinster Wert, 3. kleinster Wert...) u. U. Zeit sparen.