4. Kleinster Wert aus Array

Kleinster Wert aus Array

  • ?

    ok will mal nicht so sein und ich geb dir ein tipp

    eine übersicht

    ersetzt kein gutes buch.

    http://www.math.tu-freiberg.de/~ernst/Lehre/AD/adKapitel5.pdf

    wenn dir das zu hoch ist dann kauf dir

    ALGORITHMEN UND DATENSTRUKTUREN oder ( untertitel )
    algo was?? for dummies band 1-8

    0
  • G

    Warum soll eine Funktion die sich selbst bis zum auftreten einer Abbruchbedingung aufruft, weniger Vergleich brauchen als eine die das nicht tut?

    Es geht ja nicht darum, die Liste Linear zu sortieren sodern bloß darum, alle Werte mit jeweils einem anderen zu vergleichen.

    Du hast doch selbst gesagt

    bei Quicksort wird auch jedes element verglichen, ABER REKURSIV ! das ist der unterschied.

    Das ist sind doch dann im minimalfall n vergleiche. Wo ist dann mein Denkfehler? Wie zum verrecken soll irgendetwas das auch mindestens 40000 vergleiche braucht, schneller sein als:

    int array[40000];
int value;
for (int i=0;i<40000;i++)
{
  if (array[i]<value) ...
}

    Nein, da muß ich dir zustimmen, das verstehe ich beim besten willen nicht.

    Dann zeig mir doch einfach mal ein Codebeispiel, das mit sortieren aus einem Array schneller das kleinste Element ermittelt als das nachfolgende. Wenn ihr das könnt, bin ich ganz ruhig und fange schon mal an zu schmökern.

    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;
    }
  }
}
    0
  • ?

    sag mal ehrlich

    hast den link überhaupt angeschaut????

    lol sag ich nur

    ok hier mal ne aufgabenstellung

    http://pimpf.pi.informatik.tu-darmstadt.de/loop/aufgaben/fischer/own/sort/quick/

    und hier die lösung

    hier mal ein ZITAT von der nachfolgenden site ( die ich gleich nenne werde )

    *****************
    Quicksort ist wahrscheinlich der komplizierteste der 4 Algorithmen. Dennoch ist es gut, wenn man ihn versteht, denn er heißt nicht umsonst Quicksort. Jedenfalls werden wir Schritt für Schritt vorgehen, weil es unter Umständen nicht ganz so leicht ist. Im Folgenden sind also die wichtigsten Schritte des Quicksort Algorithmus aufgelistet:
    ********************************

    ok jetzt weisst das es gut ist ihn zu verstehen

    und es wird auch ein bsp für REKURSION gennant am berühmten bsp der fakultät

    also dann man dein versprehchen war wenn du das jetzt hier sehen tust ( mit c++ code )

    http://www.zfx.info/Tutorials.php?ID=79

    und wenn du es jetzt immer noch nicht schnallst dann ......

    PS

    was glaubst du warum es verschiedene sortieralgorithmen gibt???? wenn die lineare das beste ist und man nicht drunter kann. ALSO WARUM wird zeit und geld da reingesteckt??? sind alle doofer als du????

    checks mal ab

    machst ja eh nicht da du den ersten link ja nicht mal nachgegangen bist

    0
  • G

    was glaubst du warum es verschiedene sortieralgorithmen gibt???? wenn die lineare das beste ist und man nicht drunter kann. ALSO WARUM wird zeit und geld da reingesteckt??? sind alle doofer als du????

    Ich hatte doch nie vor die verdammte Liste zu sortieren. Ich habe auch nie behauptet, das Quicksort nicht schneller ist als ein Linearer Sortieralgorithmus. Mir ist bewusst das Quicksort einer der besten Sortieralgorythmen ist. Es geht doch überhaupt nicht darum ob Quicksort besser ist als ein anderer Soriteralgorythmus.

    Es geht darum ob es sinn macht, überhaupt irgendeinen Sortieralgorythmus zu verwenden um den kleinsten Wert in einem Array ausfindig zu machen.

    Entweder du zeigst mir jetzt eine Funktion die mit einem Sortieralgorythmus den Minimalen Wert eines Arrays schneller ermittelt als meine oben genannte Funktion oder du hörst endlich auf mich die ganze Zeit anzugreifen.

    P.S.
    Les du dir meine Posts bitte auch mal komplett durch.

    0
  • ?

    also zum letzen male

    deine lineare suche läuft darauf aus

    das du bei array[200]

    was machen musst?

    eine schleife machen

    int wert = array[0];
    dann ne schleife wo du 199 male etwas machen musst. also 199 male vergleichen

    ob der derzeitige wert array[i] kleiner ist als der akt. wert

    wenn das der fall ist dann kriegt der wert den neuen wert.
    diese zuweisung musst du in der regel ( durchschnitt ) ca. 100 mal machen.

    also zum rekapitulieren

    199 schleifen durchgänge ( 199 male etwas machen, die vergleiche eben ) und ca. 100 male den wert zuweisen. ich geh jetzt nicht von best oder worst case aus.

    beim sortieren gehts is in der regel ( wieder nicht best oder worst case ) logarithmisch zu ( wegen der rekursion die drin steckt )

    weisst du das die logarithmus funktion die umkehrfunktion der expon. fkt. ist?

    also bei 200 werten musst du etwas dann ( aufgerundet ) 15 male machen. eben links recht pivot element ( so wie in den links beschrieben )

    und am ende EINE zuweisung machen. FOLGENDE: int KleinsterWert = array[0];
    da ganz links der kleinste wert ist.

    also zum wiederholen ( im average case )

    linear: 199 durchläufe und 100 zuweisungen
    quicksort: 15 durchläufe 1 zuweisung

    newkid sagte auch ( lies mal ), das das array dann sortiert ist. aber wenn du nur den kleinsten wert haben willst ( und das interesiert ja jetzt ) dann ist es schneller (idr ) als lineare suche

    zudem du dann auch wenn du weitere male suchen willst

    ( z.b. grösstes element ) eine zuweisung nur machen musst.

    jede andere zahl kann man mit der BINÄR SUCHE MACHEN

    deswegen lohnt es sich auf ein array ( wo man öfters mal braucht ) das zuerst zu sortieren. dann kann man immer schneller suchen! und wenn sich werte verändern ( dazu kann mein ein flag setzen das status überprüft ) dann kann man bubblesort oder anders verfahren nehmen.

    kapiert???
    also wenn man ein array hat ( kleines ) z.b. array[10] dann macht man nicht extra den ganzen code rein zum sortieren und so.

    wenn man ein grosses array hat, dann sortiert man ( ausser man darf es nicht, da die eihenfolge wichtig ist ) das array zuerst und hat dann den wert.

    kapierst es jetzt

    noch ein bsp.

    array[10 000}

    linear 9 999 durchläufe
    quicksort 100 durchläufe

    was ist besser??? aber das verstehst du einfach nicht.

    0
  • ?

    GeorgeHomes schrieb:

    Entweder du zeigst mir jetzt eine Funktion die mit einem Sortieralgorythmus den Minimalen Wert eines Arrays schneller ermittelt als meine oben genannte Funktion oder du hörst endlich auf mich die ganze Zeit anzugreifen.

    also angreifen tue ich dich nicht. ich will es für dich nur begreiflich machen

    ich hab dir sogar den link gegeben wo der sortieralgo. drauf ist.

    den findest idr auch bei MFC

    jetzt mach mal ein sehr sehr grosses array. dann mach mal beide methoden und tue mal die zeit messen. MFC untersützt das doch oder? oder tue meinetwegen vorm suchbeginn eine variable die akt zeit ( mit microsec ) zuweisen und am schluss auch und dann haste die genaue differenz.

    mach das doch mal. wie gesagt lohnt es sich bei grossen arrays. bei aray[2] ist es nicht so der hit. kapiert? ne gell. so das war mein letzter post. ausser du machst die versuche und machst screenshots und tust mich vom gegenteil überzeugen ( wegen beweiss ). alles andere ( deine erklärungsversuche ) die kannst behalten, genauso wie meine rechtschreibfehler.

    0
  • G

    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.

    0
  • T

    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

    0
  • ?

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

    0
  • G

    @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.

    0
  • ?

    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.

    0
  • G

    @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.

    0
  • S

    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

    0
  • E

    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. 🙄

    0
  • C

    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. 😕

    0
  • D

    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.

    0
Anmelden zum Antworten