Kleinster Wert aus Array

estartu_de schrieb:

200 Threads suchen für je eine Zeile den kleinsten Wert. Aus denen dann den kleinsten rauszusuchen ist ja nicht das Zeit-Problem.

Sinn = 0;

also wenn es wirklich unsortiert ist

dann musst du linear vorgehen

also brauchst du 2 for schleifen

sag mal ehrlich:

hast es mal mit 2 for schleifen versucht? die zeit gestoppt?
wie lange dauert es? selbst auf einem 400mhz PC muss das ziemlich flott gehen, wenn der algor. nicht zu dumm ist.

wenn es schneller gehen soll also
wenn es dir zu lange dauert ( warum ist dein programm so zeitkritisch? ) dann kannste ja 200 mal ( je zeile ) quicksort machen. hat die komplexitaet von ( n log n ) und merkst dir dabei den kleinsten wert.
und denn merkst dir so lange bis ein einer anderen zeile der quicksort algort. ( der dir auch den kleinsten wert dabei liefert ! ) einen kleinern wert findet.

muesste insgesamt sogar schneller gehen als die linear suche!

oder du kaufst dir n vectorrechner der 200 zeilen auf einmal abklappert

ahmm

natuerlich hab ich mich vertippt als ich sagte das du linear vorgehen musst, denn das widerlege ich ja mit dem quicksort ( schaem )

und das mit denn 200 threads ist dumm, aber es koennte mit mehreren threads gehen (( nicht 400 ! )) wenn du hast z.b. multiprozessor board ( z.b. 4 CPU's ) system. und das Betriebssytem checks ab und parallelisiert ( -> theorie ). das geht dann tatsaechlich schneller ( auch wenn nur super klein messbar )

oder du hast ( wiederrum meherer Prozessoren ) und die Programierumgebung unterstuezt das ( z.b. OCCAM ) dann kannst tatsaechlich parallelprogramieren, ohne threads. nachteil DU musst dich selber drum kuemmern. aber das nur am rande ( hat ja nichts mit MFC zu tun )

Cpp_Junky schrieb:

200 Threads ?

Wenn schon dann nimm 40000 Threads. Damit gehts am schnellsten.

Cpp_Junky

Noch dazu kommt, das die Suche nach dem kleinsten Wert nur ein Teil eines anderen Algorithmus ist. Und dieser ist sogar rekursiv und wird daher auch "ein Paar mal" aufgerufen. Der "suche den kleinsten Wert"-Teil wird innerhalb des ganzen also öfters ausgeführt und muss deshalb sehr schnell sein.

Wenn das Array nicht sortiert ist, musst du in jedem Fall alle 40000 Einträge ablaufen. Da gibts keinen Trick.

Cpp_Junky schrieb:

Noch dazu kommt, das die Suche nach dem kleinsten Wert nur ein Teil eines anderen Algorithmus ist. Und dieser ist sogar rekursiv und wird daher auch "ein Paar mal" aufgerufen. Der "suche den kleinsten Wert"-Teil wird innerhalb des ganzen also öfters ausgeführt und muss deshalb sehr schnell sein.

ok und jetzt auf deutsch bitte

welchen algorithmus nimmt du aus basis, der wiederum ein teil eines andern sein soll

welche beiden meinst du da???

zitat:

Der "suche den kleinsten Wert"-Teil wird innerhalb des ganzen also öfters ausgeführt und muss deshalb sehr schnell sein.

zitat einde:

was?? weil etwas oefters ausgefuehrt wird, MUSS es sehr schnell sein?? oder meinst du sollte?
und wenn etwas rekursiv wird es in der regel oefters ausgefuehrt ( ausser die stopbedingung ist gleich nachdem ersten mal erfuellt )

das ist ja nichts verkehrtes. kommt nur auf das problem drauf an. manche lassen sich sehr gut rekursiv loesen und manche sind rekursiv schei...

bsp.

tuerme von hanoi und fibonatschi zahlen ( k.a. wie man den schreibt )

far away schrieb:

Wenn das Array nicht sortiert ist, musst du in jedem Fall alle 40000 Einträge ablaufen. Da gibts keinen Trick.

FALSCH

was heisst wohl QUICKSORT

besteht aus.

also einmal QUICK ( = schnell )

und einmal SORT ( = sortieren ) sprich du sortierst die werte anhand der groesse.

beim sortieren merkst dir den kleinsten wert!

dein 40 000 eintrage ablaufen ist komplesitaet O(n) = linear
QUICKSORT hat komplesiteat von O(n log n ) = logartithmisch

denk mal drueber nach!

fuer die mathematiker unter euch

also ist nicht ganz die komplesitaet von O( n log n ) weil man ja n mal macht ( n in diesem fall 200 )

also ist es

n mal n log n

GeorgeHomes

Ich weiß ja das Quicksort verdammt schnell ist, aber effektiv gesehen muß er doch auch jedes Element midnestens einmal vergleichen um es einordnen zu können, also müsste das doch auf jeden fall langsamer sein als die Lineare durchsuchvariante. Ich sehe da schwarz.

Das einzige was du machen kannst, ist die Suche beim fund eines minimalwertes (z.B. 0) zu beenden.

Andorxor

Du kannst den Vergleich ja beim Füllen des Arrays machen da musst du doch sowieso alle Elemente durchlaufen.

ZITAT:
also müsste das doch auf jeden fall langsamer sein als die Lineare durchsuchvariante
ZITAT ENDE:

lesen bildet

http://www.quick-sort.de/refqsort_2.htm

ganz gut

http://www.iti.fh-flensburg.de/lang/algorithmen/sortieren/quick/quick.htm

heisst auch "teile und hersche" deswegen hat O(n log n) also nichts mit auf jeden fall langsamer

natürlich im worstcase O(.....) ( sag ich jetzt lieber nicht )

-----------------

das ganze ist natürlich dumm, wenn das array nicht sortiert werden darf.

ausser man sortiert und merkt sich was vertauscht worden ist ( mehr speicheraufwand )

und macht dann in einer ruhigen min alle rückgaängig, hehe ( ich hoff den letzen teil nimmt jetzt niemand zu ernst )

GeorgeHomes schrieb:

Das einzige was du machen kannst, ist die Suche beim fund eines minimalwertes (z.B. 0) zu beenden.

meine lieblingsstelle von dir

was wenn es sich um kontostände ect. handelt.
darfs da keine negativen zahlen geben?

ok, du schriebst ja auch z.b. ( aber trozdem )

das_brot

Moin,

Hab's mal so versucht:

int array [200][200];

void CTestDlg::OnButton1() // array mit zufallszahlen füllen
{

for(int a = 0; a<200;a++)
{
	for(int b = 0; b<200; b++)
	{
		array [a][b] = rand();
	}
}
}

void CTestDlg::OnButton2() //kleinsten wert finden und ausgeben
{

int f1 = 0;
int f2 = 0;
int CH = array [0][0];

	for(int a = 0; a<200;a++)
	{
		for(int b = 0; b < 200; b++)
		{
			if(array [a][b] < CH)
			{
				CH = array [a][b];
				f1 = a;
				f2 = b;
			}
		}
	}

CString sa;
sa.Format("%d in [%d][%d]",array[f1][f2],f1,f2);
MessageBox(sa);
}

Ergebnis: Er findet den Wert in weniger als einer Sekunde,
entweder hab' ich einen Fehler im Code gemacht, oder diese Lösung ist brauchbar

Gruss

[edit]
so, jetzt sollte der Code sogar stimmen...
[/edit]

was an deinem code mir merkwürdig erscheint, ist die tatsache das du

f1,f2,ch deklarieren tust, aber keine werte initialisierst.

dann machst du 2 for schleifen
und in der 2ten prüfst du

ausserdem auch noch falsch, da ( array [a][b] > CH ) also sprich immer wenn im array ein groesserer wert steht, es muss aber ein kleinerer wert sein

also weiter, du prüfst dann

array [a][b] und dies hat einen wert. CH hat bis jetzt noch keinen wert.

da wahrscheinlich CH am anfang irgendwas mit minus n ( n sehr gross ) springt er rein.
ich häts anders gemacht in der 2ten for schleife

CH = array [0][0];  // jetzt hat CH den ersten wert.

//1.te for schleife

//2.te for schleife dann

if(array [a][b] < CH)   // kleiner zeichen (  nicht groesser !!!  )
{
    CH = array [a][b];
    f1 = a;
    f2 = b;
}

probierst jetzt mal aus. aber wie gesagt. diese linerare suche muss schnell sein beim heutigen PC. weiss auch nicht warum der so zeitkritisch programmieren will.

GeorgeHomes

@littlekid
Jetzt glaub ichs aber langsam. Wenn du auch mal eine Sekunde darüber nachdenkst, wirst du wohl auch darauf kommen das kein Sortieralgorytmus in der Lage ist mit Weniger Vergleichen auszukommen als Elemente vorhanden sind. Es muß jedes Element midestens einmal verarbeitet werden, um es einsortieren zu können. Das bedeutet eine absolute Minimalzahl von n Vergleichen. Dies wiederum ist die konstante der Linearen Methode, sprich, sie ist unter keinen Umständen schneller. Im allerbesten Fall wäre Sie genauso schnell.

GeorgeHomes schrieb:

@littlekid
Jetzt glaub ichs aber langsam. Wenn du auch mal eine Sekunde darüber nachdenkst, wirst du wohl auch darauf kommen das kein Sortieralgorytmus in der Lage ist mit Weniger Vergleichen auszukommen als Elemente vorhanden sind. Es muß jedes Element midestens einmal verarbeitet werden, um es einsortieren zu können. Das bedeutet eine absolute Minimalzahl von n Vergleichen. Dies wiederum ist die konstante der Linearen Methode, sprich, sie ist unter keinen Umständen schneller. Im allerbesten Fall wäre Sie genauso schnell.

du bist ein echt ein noob ( anfänger )

newkid hat recht !

hast du schon mal was von TEILE UND HERSCHE gehört???

Sagt dir Rekursion was???? weisst was das ist???

kauf dir ein buch über "algorithmen und datenstrukturen"

dann kannste mitreden.

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

deswegen ist es ( bei unsortierten elementen und zufälligen PIVOT element ) schneller als linear.

aber das verstehst du nicht.

wie gesagt kauf dir ein buch und lies erstmal, bevor du hier irgendwelchen "inteligente" sachen posten tust.

checks mal ab

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

GeorgeHomes

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;
    }
  }
}

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