Minimum
-
Wenn Du den Aufwand für das Aufbauen des Suchbaums mit reinrechnest ist es langsamer.
-
finix schrieb:
volkard schrieb:
finix schrieb:
Benutzungscharakteristik
aua.
Ja ja, volkard, ich weiss. Egal wie und wozu man einen Container verwendet, die richtige Wahl ist immer das Array/der Vector.
falsch. und ich wollte nur auf das unpassende wort hinweisen.
-
Jester, bitte. Du bist Mathe-Mod, das kann doch nicht so schwer sein.
array tree ________________________________________ creation: | O(N) | O(N log N) | | lookup: | O(N) | O(log N) lookup: | O(N) | O(log N) lookup: | O(N) | O(log N) lookup: | O(N) | O(log N) lookup: | O(N) | O(log N) lookup: | O(N) | O(log N) lookup: | O(N) | O(log N) lookup: | O(N) | O(log N) lookup: | O(N) | O(log N) lookup: | O(N) | O(log N) | . | . . . . .Meinst du nicht die Investition zahlt sich irgendwann aus?
-
volkard schrieb:
finix schrieb:
volkard schrieb:
finix schrieb:
Benutzungscharakteristik
aua.
Ja ja, volkard, ich weiss. Egal wie und wozu man einen Container verwendet, die richtige Wahl ist immer das Array/der Vector.
falsch. und ich wollte nur auf das unpassende wort hinweisen.
Dann erleuchte mich bitte, warum ist dieses Wort falsch und welches hätte ich an seiner statt verwenden sollen?
-
finix schrieb:
Dann erklär doch mal warum die Minimumsuche in einem Suchbaum langsamer sein soll als in einem ungeordnetem Container. Ist mir nämlich nicht so ganz klar.
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?
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.
-
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.
-
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.
-
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).
-
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>
-
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.
-
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.
-
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.
-
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.
-
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.
-
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?
-
container.clear() erledigt das recht schön
-
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.
-
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.
-
@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).
-
Den Vektor kann ich ja auch einfach mehrdimensional machen? Oder spricht was dagegen?