Minimum

[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

[THX 1138]

becks21 schrieb:

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

Können kannst DU schon, dann hast Du einfach soviele Suchanfragen wie Dimensionen.
Nun sag doch mal was Du vorhast.
Woher kommen die Werte?
Willst Du das Minimum jeder Serie oder das aller Serien?
Brauchst Du die Werte nachher noch oder brauchst Du nur das Minimum?

[Xin]

Jester schrieb:

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.

Ich las die Fragestellung und was danach kam, sieht mir eher nach deutlichen STL-Verliebtheit, als einer sinnvollen Problemlösung aus. Ich denke, dass liest sich auch quer da wunderbar raus.

Jester schrieb:

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

Das beurteilst Du so? Okay, damit kann ich gut leben und mir gedanklich eine kleine Notiz für unter 'Jester' anlegen, irgendwie scheint mir da sowieso schonwas aus früheren Threads zu klingeln... Aber deklariere derartiges doch bitte als Deine persönliche Meinung, denn mehr stellt es nicht dar.
Abgesehen davon, kann es nicht schaden, wenn sich nach 7 Seiten mal jemand um das eigentliche Problem bemüht.
Schön, dass Deine Reaktion derart freundlich formuliert ist, nur weil mein Ansatz ein anderer ist als der von Dir bevorzugte.

Aus der Anfrage las ich nämlich nicht, dass die Daten entsprechend eines STL-Templates iterierbar sind. Wenn er das zusätzlich noch entwickeln muss, dann bröckelt Deine kompetente Argumentation angefangen von 'weniger zu tippen' von hinten weg.
Für den Fall, dass er tatsächlich Anfänger ist, könnte die STL-Lösung ihn damit vollends überfordern und außer seine Zeit zu verschwenden keinen weiteren Nutzen bringen.

Jester schrieb:

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

Worum es in diesem Thread geht, steht in der Regel im ersten Posting. Um das Minimum diverser Werte. Wie mir scheint, scheint das bisher kaum beachtet worden zu sein.

r0nny schrieb:

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

Das stellt für mich ein gutes Beispiel einer sinnvollen, möglichen Problemlösung dar - daher meine Frage, wie die Daten überhaupt vorliegen.

[finix]

Xin schrieb:

Ich las die Fragestellung und was danach kam, sieht mir eher nach deutlichen STL-Verliebtheit, als einer sinnvollen Problemlösung aus. Ich denke, dass liest sich auch quer da wunderbar raus.

Haha, und das von jemandem der so for -verliebt ist wie du? Du hättest auch ganz einfach if & goto verwenden können...

(Die STL ist Teil des C++-Standards. Jemandem der darauf hinweist dass es in der Standardbibliothek einen dem Problem angemessenen Algorithmus gibt STL-Verliebtheit vorzuwerfen ist äußerst lächerlich.)

Xin schrieb:

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

Das beurteilst Du so? Okay, damit kann ich gut leben und mir gedanklich eine kleine Notiz für unter 'Jester' anlegen, irgendwie scheint mir da sowieso schonwas aus früheren Threads zu klingeln...[/quote]

Es wäre weniger albern wenn du statt dieser ominösen Andeutung + Pseudodrohung einfach auf sein Argument eingehen würdest.

Xin schrieb:

Aber deklariere derartiges doch bitte als Deine persönliche Meinung, denn mehr stellt es nicht dar.

Ich sehe nicht dass du deine Meinung als solche deklariert hast. (Und wozu auch, das ist in aller Regel nicht nötig, der Unterschied zwischen "1+1=2" und "mir gefällt die 3" ist offensichtlich.)

Nicht zu vergessen dass nicht alle Meinungen gleich viel Wert sind.

Xin schrieb:

Abgesehen davon, kann es nicht schaden, wenn sich nach 7 Seiten mal jemand um das eigentliche Problem bemüht.
Schön, dass Deine Reaktion derart freundlich formuliert ist, nur weil mein Ansatz ein anderer ist als der von Dir bevorzugte.

Xin schrieb:

Aus der Anfrage las ich nämlich nicht, dass die Daten entsprechend eines STL-Templates iterierbar sind. Wenn er das zusätzlich noch entwickeln muss, dann bröckelt Deine kompetente Argumentation angefangen von 'weniger zu tippen' von hinten weg.

Ähm, LOL?

Xin schrieb:

Für den Fall, dass er tatsächlich Anfänger ist, könnte die STL-Lösung ihn damit vollends überfordern und außer seine Zeit zu verschwenden keinen weiteren Nutzen bringen.

Es geht hier nicht um hochgradig obskure Metaprogrammierung sondern schlicht um simples Standard C++. Kann es sein dass du dich damit einfach selber nicht auskennst und deswegen dagegen sträubst?

Xin schrieb:

Jester schrieb:

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

Worum es in diesem Thread geht, steht in der Regel im ersten Posting. Um das Minimum diverser Werte. Wie mir scheint, scheint das bisher kaum beachtet worden zu sein.

Folgt man deiner Argumentation dürfte kein Thread aus mehr als 2 Beiträgen bestehen, redundante Postings die sich dem OP anschließen ausgenommen.

Xin schrieb:

r0nny schrieb:

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

Das stellt für mich ein gutes Beispiel einer sinnvollen, möglichen Problemlösung dar - daher meine Frage, wie die Daten überhaupt vorliegen.

Hättest du den Thread gelesen wäre dir klar dass dieser Punkt auch schon angesprochen wurde.

[Xin]

Hallo finix.

Erstaunlich, dass Du mir eine for-Verliebtheit nach einer einzigen for-Schleife unterstellst... ich muss Dich enttäuschen, im Schnitt bin ich eher im while-Wahn denn for-verliebt.

Um Dein Weltbild jedoch nicht ganz zu zerstören: ich gehöre tatsächlich zu den Leuten, die in goto eine sinnvolle C/C++ Anweisung sehen. Vielleicht nicht in dem von Dir genannten Zusammenhang, aber dennoch der Mehrheit der C/C++-Gläubigen zum Widerspruch.

finix schrieb:

Xin schrieb:

Für den Fall, dass er tatsächlich Anfänger ist, könnte die STL-Lösung ihn damit vollends überfordern und außer seine Zeit zu verschwenden keinen weiteren Nutzen bringen.

Es geht hier nicht um hochgradig obskure Metaprogrammierung sondern schlicht um simples Standard C++. Kann es sein dass du dich damit einfach selber nicht auskennst und deswegen dagegen sträubst?

Wer sich bemüht, eine Frage zu tippen, die hoffentlich auch für Dich aufwendiger ist, als eine Minimumfunktion zu implementieren, lernt C++ vermutlich zur Zeit. Das heißt, es ist kein Standard C++ vorhanden. In dem Fall liegt die Definition von 'simples Standard C++' sicherlich anders, als es vielleicht Deine Vorstellung ist.

Ich meine, dass es durchaus sinnvoll ist, den Wissenstand des Fragenden zu berücksichtigen, damit er die Problemlösung auch umsetzen kann. Meinst Du nicht?

Weiterhin meine ich, dass es immernoch weniger aufwendig ist, eine Minimum-Funktion zu schreiben, als für nicht STL-iterierbare Werte einen Iterator.
Der notwendige Aufwand ist meiner Meinung nach ebenfalls beachtenswert oder meinst Du nicht?

finix schrieb:

Xin schrieb:

Worum es in diesem Thread geht, steht in der Regel im ersten Posting. Um das Minimum diverser Werte. Wie mir scheint, scheint das bisher kaum beachtet worden zu sein.

Folgt man deiner Argumentation dürfte kein Thread aus mehr als 2 Beiträgen bestehen, redundante Postings die sich dem OP anschließen ausgenommen.

Meine Argumentation ist, dem Fragenden erst zu helfen und sich danach bei Bedarf dann an der STL aufzugeilen.

Bisher sehe ich jedenfalls nicht, ob der Fragende sein Problem gelöst hat.
Darum geht es doch in diesem Forum und in diesem Thread, dachte ich!?
Vielleicht gibt es da auch gleichwertige andere Meinungen und ich muss meine mal überdenken.

[finix]

Xin schrieb:

Erstaunlich, dass Du mir eine for-Verliebtheit nach einer einzigen for-Schleife unterstellst... ich muss Dich enttäuschen, im Schnitt bin ich eher im while-Wahn denn for-verliebt.

Um Dein Weltbild jedoch nicht ganz zu zerstören: ich gehöre tatsächlich zu den Leuten, die in goto eine sinnvolle C/C++ Anweisung sehen. Vielleicht nicht in dem von Dir genannten Zusammenhang, aber dennoch der Mehrheit der C/C++-Gläubigen zum Widerspruch.

Erstaunlich dass du anderen STL-Verliebtheit vorwirfst nach einem einzigen Algorithmus....
Weniger erstaunlich dass du komplett am Punkt vorbei geantwortet hast.

Die Unterstellung im zweiten Absatz entbehrt nicht nur jeglicher Grundlage, sondern hat noch weniger Bezug zum eigentlichen Punkt.

Xin schrieb:

Wer sich bemüht, eine Frage zu tippen, die hoffentlich auch für Dich aufwendiger ist, als eine Minimumfunktion zu implementieren, lernt C++ vermutlich zur Zeit. Das heißt, es ist kein Standard C++ vorhanden. In dem Fall liegt die Definition von 'simples Standard C++' sicherlich anders, als es vielleicht Deine Vorstellung ist.

Sorry, kompletter Semantik-Crash. Kannst du das nochmal neu formulieren?

Xin schrieb:

Ich meine, dass es durchaus sinnvoll ist, den Wissenstand des Fragenden zu berücksichtigen, damit er die Problemlösung auch umsetzen kann. Meinst Du nicht?

Ja, das ist genau mein Punkt. Standard-Container & -Algorithmen sind keine Atomphysik, daher ist Wissensstand |= generische Standardlösung durchaus erstrebenswert.

Xin schrieb:

Weiterhin meine ich, dass es immernoch weniger aufwendig ist, eine Minimum-Funktion zu schreiben, als für nicht STL-iterierbare Werte einen Iterator.
Der notwendige Aufwand ist meiner Meinung nach ebenfalls beachtenswert oder meinst Du nicht?

Hm. Sollte das nicht der Fall sein liegt aller Wahrscheinlichkeit nach ein Designfehler vor, der behoben werden sollte.
Vor allem geht dein Code geht vom Vorhandensein eines op[] aus, was eine wesentlich größere Einschränkung darstellt.

Xin schrieb:

Meine Argumentation ist, dem Fragenden erst zu helfen und sich danach bei Bedarf dann an der STL aufzugeilen.

Du magst die Standardbibliothek nicht, was? Aber dein Argument kann man genauso gut (und wesentlich sinnvoller, IMAO) umdrehen: man sollte dem Fragenden zunächst die angemessene Lösung anbieten und sich dann erst, auf ausdrücklichen Wunsch, an NIH-Konstrukten aufgeilen.

Xin schrieb:

Bisher sehe ich jedenfalls nicht, ob der Fragende sein Problem gelöst hat.
Darum geht es doch in diesem Forum und in diesem Thread, dachte ich!?
Vielleicht gibt es da auch gleichwertige andere Meinungen und ich muss meine mal überdenken.

Dass der OP sich nicht zum Stand seines Problems geäußert hat legt eher die Vermutung nahe dass er es bereits lösen konnte.

Und vielleicht solltest du dich mit dem Gedanken anfreunden dass es ggf nicht nur gleichwertige sondern auch höherwertige Meinungen neben deiner gibt.