Minimum

[volkard]

finix schrieb:

Meinst du nicht die Investition zahlt sich irgendwann aus?

es ging darum, aus einer menge das minimum zu finden. das ist schneller mit linearem durchgehen. du baust gerade ne ganz andere aufgabe. du willst n mal das minimum finden und dazuwischen die menge jeweils ein wenig verändern.
deinne methode mit dem baum ist für deine geänderte aufgabe nicht ganz dumm. aber für die anfängliche aufgabe ist es zu lahm. die anfängliche aufgabe ist viel einfacher.

[finix]

volkard schrieb:

also das beispiel von becks21 war

Ich will ja nur, dass ich z.B. die Werte (8,7,300,655,1000) habe und dann gibt er mir aus der kleinste Wert ist 7.

das sieht ungeordnet aus. und dann fragte er, wie man wohl von 3000 werten das minimum findet. welches seiner postings führt dich zu der annahme, es sei wahrscheinlich, daß er die daten als baum vorliegen hat?

Gar keins. Welches seiner Postings führt dich zu der Annahme es sei nicht möglich diese Menge geordnet zu speichern? Welches seiner Postings führt dich zu der Annahme die Minimumsuche kommt nicht häufig genug vor um eine alternative View auf die Menge ins Gespräch zu bringen?

volkard schrieb:

und wenn du einen baum draus machst, mußte auch die baummachkosten zahlen. die sind teuer mit N*log(N) im vergleich zu den minimumsuchkosten mit N.

Ich muss gestehen ich hab nicht alles gelesen was DEvent bis Seite 3 oder so geschrieben hat. Meine Aussage war von Anfang an das der Baum für eine einmalige Suche "Schwachsinn" ist.

volkard schrieb:

es ging darum, aus einer menge das minimum zu finden. das ist schneller mit linearem durchgehen. du baust gerade ne ganz andere aufgabe. du willst n mal das minimum finden und dazuwischen die menge jeweils ein wenig verändern.
deinne methode mit dem baum ist für deine geänderte aufgabe nicht ganz dumm. aber für die anfängliche aufgabe ist es zu lahm. die anfängliche aufgabe ist viel einfacher.

Der OP hat schlicht nicht genug Informationen geliefert um beurteilen zu können wie die tatsächliche Aufgabe aussieht.

[Jester]

Jo, irgendwann lohnt sich's, und zwar dann wenn mehr als O(log N) Anfragen kommen. Wie kommst Du auf die Idee das sei mir nicht klar? Von vielen Anfragen ist aber nirgends die Rede.

Nochmal: Die Originalaufgabenstellung war: "Ich habe Werte und will das Minimum finden". Das ist der Baum einfach keine angemessene Lösung dafür. Und selbst wenn Du N Lookups machen willst, dann ist sortieren noch besser als der Baum (wie ich schon schrieb) und nur wenn's noch dynamisch ist, ist der Baum gut (wie ich ebenfalls schon schrieb).

Wir sollten vielleicht schon davon ausgehen, daß der OP seine Anforderungen (die sind hier imho ziemlich klar formuliert) kennt. Wenn wir davon natürlich nicht ausgehen können, würde ich empfehlen das ganze auf nem Linux-Server mit mindestens 2G RAM laufen zu lassen, ne mySQL-Datenbank wegen großer Datenmengen zu verwenden (wir wissen ja nicht wieviele Werte es sind) und die Suche nach Möglichkeit auf nem Cluster parallel laufen zu lassen. Zustätzlich sollten jeweils Gesamtsumme und Durchschnitt der Werte mit vorgehalten werden (vielleicht braucht man's mal).

[Shade Of Mine]

finix schrieb:

Der OP hat schlicht nicht genug Informationen geliefert um beurteilen zu können wie die tatsächliche Aufgabe aussieht.

also ich finde die aufgabenstellung:

"Ich will ja nur, dass ich z.B. die Werte (8,7,300,655,1000) habe und dann gibt er mir aus der kleinste Wert ist 7."

ziemlich eindeutig und da ist die perfekte antwort min_elemenet() aus <algorithm>

[finix]

Jester schrieb:

Wir sollten vielleicht schon davon ausgehen, daß der OP seine Anforderungen (die sind hier imho ziemlich klar formuliert) kennt.

OP schrieb:

Hallo!

Ich hab mehrere Werte und ich muss das Minimum der Werte herausfinden, gibt's da eine Funktion oder muss ich das selbst programmieren?

Ja, klarer geht's wohl kaum.

[Shade Of Mine]

sagt dir
KISS
etwas?

klar kannst du davon ausgehen dass was weiss ich was mit den daten noch passieren wird. am besten stellen wir uns deshalb nen Oracle DB server hin, am besten geclustert. Dazu 3 dedizierte xeon server wo die suche verteilt ablaufen kann.

dazu bauen wir uns diverse suchbaeume auf. wir stellen noch nen db server ab zum cachen diverser daten...

vielleicht noch n load balancer zwischen schalten damit wir mehrere suchanfragen effizient gleichzeitig machen koennen...

schiesst etwas ueber das ziel hinaus.

der OP hat eine sammlung von werten und will da den niedrigsten raus haben. das geht super mit min_element. was willst du mehr? wozu irgendwelche komplizierten strukturen aufbauen die der op eh nicht versteht - er kannte ja nichtmal std::vector.

[finix]

Shade Of Mine schrieb:

"Ich will ja nur, dass ich z.B. die Werte (8,7,300,655,1000) habe und dann gibt er mir aus der kleinste Wert ist 7."

... die perfekte antwort min_elemenet() aus <algorithm>

Prinzipiell schon. Das heißt aber nicht unbedingt dass eine Liste die optimale Datenstruktur ist.

[Jester]

finix schrieb:

OP schrieb:

Hallo!

Ich hab mehrere Werte und ich muss das Minimum der Werte herausfinden, gibt's da eine Funktion oder muss ich das selbst programmieren?

Ja, klarer geht's wohl kaum.

Schön daß wir uns einig sind.

[Shade Of Mine]

finix schrieb:

Prinzipiell schon. Das heißt aber nicht unbedingt dass eine Liste die optimale Datenstruktur ist.

das ist aber nicht teil der aufgabenstellung.

wenn dich jemand fragt wie er am schnellsten von hier zum bahnhof kommt, dann ist die antwort: gerade aus, dann links. bei der bank dann rechts und durch die bruecke und sie sind vorm bahnhof.

und nicht das es effektiver waere wenn er nach Muenchen umzieht, weil dort fahren die Zuege schneller und der bahnhof ist viel effizienter mit der strassenbahn zu erreichen.

[becks21]

Mal noch ne Frage, wie kann ich meinen Container wiederleeren?

Vor meinem nächsten Schleifendurchlauf müssen alle Werte wieder raus und neue rein? Wie?

[Plotzenhotz]

container.clear() erledigt das recht schön

[DEvent]

Für die Minimumsuche wäre eine Devide&Conquer Lösung nicht schlecht. Man teilt die Liste der Zahlen in 2 gleich große Teillisten, sucht aus diesen Teillisten das Minimum und vergleich die 2 so gefunden Minima miteinander. Das ganze natürlich rekursiv, so das am Ende nur 2 Werte verglichen werden.

Aber irgendwie bezweifle ich, dass das ein Vorteil bringt, man bräuchte trotzdem O(n) Vergleiche.

Es wäre aber immerhin gut parallelisierbar. Der Zeitaufwand würde sich linear mit den verwenden CPUs verringern. Auf Multicore-Systemen müsste die rekursive Minimasuche weitaus schneller laufen, wenn man für jede Teilliste einen eigenen Thread laufen lässt.

[nutzlos]

DEvent schrieb:

Für die Minimumsuche wäre eine Devide&Conquer Lösung nicht schlecht. Man teilt die Liste der Zahlen in 2 gleich große Teillisten, sucht aus diesen Teillisten das Minimum und vergleich die 2 so gefunden Minima miteinander. Das ganze natürlich rekursiv, so das am Ende nur 2 Werte verglichen werden.

Aber irgendwie bezweifle ich, dass das ein Vorteil bringt, man bräuchte trotzdem O(n) Vergleiche.

Es wäre aber immerhin gut parallelisierbar. Der Zeitaufwand würde sich linear mit den verwenden CPUs verringern. Auf Multicore-Systemen müsste die rekursive Minimasuche weitaus schneller laufen, wenn man für jede Teilliste einen eigenen Thread laufen lässt.

... dass es was bringt muss man es auch auf 2 Threads verteilen. Und solange man nicht sehr sehr sehr sehr viel Daten hat lohnt sich das definitiv nicht. Diese Vergleiche sind nicht sehr CPU intensiv.

[Plotzenhotz]

@DEvent:
Damit das wirklich was bringt brauchst du einen Scheduler mit sehr sehr geringem Overhead. Diverse OpenMP Implementierungen haben das, oder auch die "Cilk" Sprache (C-Extension für SMP), aber unter WIN32/POSIX + reinen Libraries wirst du da so schnell nicht fündig werden. Ein einfaches InterlockedCompareExchange (aka. CAS) ist auf vielen Systemen (inklusive Pentium mit HT oder Dual Core) so teuer wie etliche hundert nicht-interlocked Befehle. Und einen neuen Thread anzulegen kostet dich gleich noch zig bis hundertmal so lange.

Von daher müsste bei einer straight-forward Implementierung ohne oben genannte Tools das Input-Set schon wirklich GROSS sein und man müsste die Anzahl der Threads auf die Anzahl der Cores/Hardware-Threads limitieren (oder knapp darüber, z.B. die nächste 2er Potenz).

[becks21]

Den Vektor kann ich ja auch einfach mehrdimensional machen? Oder spricht was dagegen?

[life]

Jester schrieb:

Wenn er das kleinste und das zweitkleinste haben will (oder die k kleinsten, k Konstante), dann geht das immer noch in O(N) und man muß nicht auf O(N log N) Laufzeit hoch.

Übrigens geht das auch für das i-kleinste Element des Array, mit i nicht unbedingt konstante, in O(n)
Nämlich z.B. so: http://wwwcs.uni-paderborn.de/cs/ag-monien/LEHRE/SS06/DuA/9.pdf

[Xin]

Nachdem ich hier jede Menge Zeugs über STL gelesen habe und beim Überfliegen etwas mitbekommen habe von Anfänger und 3000 Werten, sei die Frage erlaubt, ob 6 Seiten STL-Fachsimpelei Dir irgendetwas bei Deinem Problem geholfen haben?

Falls nicht - und das befürchte ich, schließlich scheint das Problem noch nicht gelöst zu sein - so lass uns mal an den Anfang zurückgehen und Dich einfach fragen, wie Du die Daten vorliegen hast.

becks21 schrieb:

Ich hab mehrere Werte und ich muss das Minimum der Werte herausfinden, gibt's da eine Funktion oder muss ich das selbst programmieren?

Klingt für mich erstmal nach einem Dreizeiler, ganz ohne dass Du erstmal Templates und STL lernen musst. Die eigentliche Frage ist nämlich nur, wie die Daten eigentlich vorliegen, dass Du sie vergleichen kannst.
Der Vergleich ist schließlich nur

Minimum = Wert[0];
  for( int i = 0; x < AnzahlWerte; x++ )
    if( Wert[x] < Minimum ) Minimum = Wert[x];

In dem Sinne programmiere es selbst, es wird vermutlich kürzer, weniger aufwendig und schneller sein, als jegliche STL-Lösung.
Klar kann man das in eine Funktion packen, aber ob es das wirklich wert ist, dafür die STL zu bemühen?

Falls Du Fragen hast, lass mich doch bitte wissen, wie die Daten vorliegen, ob Du sie bereits in einem Array im Computer zur Verfügung hast oder erst einlesen musst... beschreibe Dein Problem einfach genauer. Der "Algorithmus", wenn man das überhaupt so nennen darf, steht da. Die Frage ist nun nur noch, wie Du drauf zugreifst ("Wert[x]") und wie Du für Deine Werte Kleiner ("<") definierest.

Wenn ich damit richtig liege, so mögen sich die STL-Vertreter kurz überlegen, ob die beste Lösung im Sinne der C++ Softwaretechnik auch die beste Lösung für das zu lösende Problem sei. Ich habe das Gefühl, dass die STL-Kanonen hier sehr unangebracht sind, um diesen Spatzen zu erlegen.

STL != 42!

[Jester]

Xin schrieb:

Nachdem ich hier jede Menge Zeugs über STL gelesen habe und beim Überfliegen etwas mitbekommen habe von Anfänger und 3000 Werten, sei die Frage erlaubt, ob 6 Seiten STL-Fachsimpelei Dir irgendetwas bei Deinem Problem geholfen haben?

Ja, daß Du nur überflogen hast merkt man Deinem Posting deutlich an.

In dem Sinne programmiere es selbst, es wird vermutlich kürzer, weniger aufwendig und schneller sein, als jegliche STL-Lösung.

Okay, mal vergleichen. Schneller als std::min_element? Ne, das macht ja das Gleiche. Kürzer? Ne, std::min_element ist kürzer. Aufwendiger... naja, std::min_element ist sogar weniger zu tippen.

std::min_element vs superschnelle_einfache_schleife: 3 : 0

Aber letzlich ging es im Rest des Threads auch darum nicht. Fall Dich interessiert worum es stattdessen ging kannste ja einfach mal nachlesen.

[SG1]

Jester schrieb:

Okay, mal vergleichen. Schneller als std::min_element? Ne, das macht ja das Gleiche. Kürzer? Ne, std::min_element ist kürzer. Aufwendiger... naja, std::min_element ist sogar weniger zu tippen.

std::min_element vs superschnelle_einfache_schleife: 3 : 0

<nitpick>2,5 : 0,5. "macht das Gleiche" ist wohl kaum ein voller Punkt fuer eine der beiden Seiten</nitpick> *duckundweg*

[ronny]

btw - werden die werte von irgendwo eingelesen? dann ist es evtl schlauer eine variable mitzuführen, die das aktuelle minimum enthält, anstatt sich zig seiten um irgendwelche sinnfrei verwendeten algos zu streiten