Minimum
-
finix schrieb:
Natürlich ist es Schwachsinn den Baum jedesmal neu aufzubauen.
Es ist auch langsamer, wenn Du ihn nur einmal aufbaust. Zumindest nur wenn man das Minimum haben will.
@Plotzenhotz: Ich finde es wichtig hier klarzustellen, daß der Ansatz mit Bäumen für eine einfache Minimumsuche quatsch ist. Der nächste liest das sonst hier und denkt es sei besonders schnell. Es geht nicht nur darum was funktioniert (so lange zufällig ziehen, bis selbst nach 1000 Ziehungen kein kleineres Element mehr gekommen ist funktioniert auch mehr oder weniger). Trotzdem ist es für die meisten Anwendungen keine gute Lösung.
-
Jester schrieb:
finix schrieb:
Natürlich ist es Schwachsinn den Baum jedesmal neu aufzubauen.
Es ist auch langsamer, wenn Du ihn nur einmal aufbaust. Zumindest nur wenn man das Minimum haben will.
Dir ist klar dass zumindest ich von einem Suchbaum geredet habe, ja?
-
@Jester: ja, im Grunde genommen stimme ich ja mit dir überein. Und gerade weil die Frage bloss "min. Element finden" ohne nähere Info war hätte ich mal den einfachsten Algorithmus vorgeschlagen, der nunmal ne einfache Suche ist.
Und weil wir schon bei möglichen Lösungen sind die vll. sogar manchmal Sinn machen (oder auch nicht): man nehme eine Datenbank (z.B. sqlite), stecke die Werte in einen Table, und selektiere sich den kleinsten Wert raus
@fixnix: du kannst auch einen Suchbaum nicht in O(N) aufbauen. Wie gesagt, wenn man viele min/max Abfragen drauf macht (mit Änderungen dazwischen, sonst könnte man den Wert/die Werte ja einfach cachen) und/oder mehrmals eine (Teil-)Folge sortiert durchgehen will ist ein Baum sicher die beste Wahl.
-
Plotzenhotz schrieb:
@fixnix: du kannst auch einen Suchbaum nicht in O(N) aufbauen. Wie gesagt, wenn man viele min/max Abfragen drauf macht (mit Änderungen dazwischen, sonst könnte man den Wert/die Werte ja einfach cachen) und/oder mehrmals eine (Teil-)Folge sortiert durchgehen will ist ein Baum sicher die beste Wahl.
Deine schwachsinnige Nickänderung wirkt eher kindisch als irgendetwas sonst.
Und wenn du drei, vier Posts hochscrollst wirst du sehen dass ich gar nicht behauptet einen Suchbaum in O(N) aufbauen zu können. (Ich traue dir durchaus zu das aus meiner Aussage ableiten zu können.)
Ich habe lediglich angemerkt dass je nach dem wie des OPs konkreter Anwendungsfall aussieht es entweder sinnvoll ist die Menge georndet zu speichern oder dass ggf. eine View darauf ein lohnenswerter Trade-Off sein könnte.
Im Prinzip also ähnlich dem was du vorschlägst.
Du scheinst also nicht wirklich "DEN Plan" vom Lesen zu haben.
-
@finix:
lol. Koffer.
-
Plotzenhotz schrieb:
@Jester: ja, im Grunde genommen stimme ich ja mit dir überein. Und gerade weil die Frage bloss "min. Element finden" ohne nähere Info war hätte ich mal den einfachsten Algorithmus vorgeschlagen, der nunmal ne einfache Suche ist.
Und weil wir schon bei möglichen Lösungen sind die vll. sogar manchmal Sinn machen (oder auch nicht): man nehme eine Datenbank (z.B. sqlite), stecke die Werte in einen Table, und selektiere sich den kleinsten Wert raus
@fixnix: du kannst auch einen Suchbaum nicht in O(N) aufbauen. Wie gesagt, wenn man viele min/max Abfragen drauf macht (mit Änderungen dazwischen, sonst könnte man den Wert/die Werte ja einfach cachen) und/oder mehrmals eine (Teil-)Folge sortiert durchgehen will ist ein Baum sicher die beste Wahl.
Hallo, ich hab doch schon Jester Recht gegeben (wird Recht hier überhaupt groß geschrieben).
Wollt ja blos sagen das wenn man doch etwas sortiert haben will, ein Baum Sinn macht.
------
Baum Aufbauen: O(nlog n)
danach O(1)
------
Einmal Suchen O(n)
Zweites mal Suchen O(n)
usw.
Ergibt insgesammt O(n²)
-
O(n^2) aber nur, wenn auch wirklich n Suchanfragen da sind. Ist es ne konstante Anzahl k, dann O(n*k) = O(n) wegen k Konstante. Klar, hat man viele Anfragen, dann sollte man nicht jedes Mal komplett durchlaufen. Mein Lösungsfavorit dafür wäre allerdings ne sortierte Liste, sofern die Datenstruktur nicht dynamisch sein muß. Nur wenn das auch noch gefordert ist (man also die Werte über die das Minimum etc gesucht wird sich ändern), ist der Baum ne wirklich gute Lösung.
@finix: klar, ein Suchbaum. Sonst könnteste den beliebigen Baum ja in O(N) aufbauen, aber Suchen wäre nicht effizient.
-
finix schrieb:
Benutzungscharakteristik
aua.
-
DEvent schrieb:
Wollt ja blos sagen das wenn man doch etwas sortiert haben will, ein Baum Sinn macht.
na, dann halt DEvent-bashing, die 2. runde.
wenn man etwas sortiert haben will, nimmt man eine sortierfunktion. das ist sinnvoll. nur ganz selten ist ein baum sinnvoll. zum beispiel dann, wenn man es jederzeit sortiert habern will, um auch bereits in der einfüllphase schnelle suchzugriffe haben will UND wenn man nicht nur immer den kleinsten (die k kleinsten) oder größten braucht.
-
finix schrieb:
Jester schrieb:
finix schrieb:
Natürlich ist es Schwachsinn den Baum jedesmal neu aufzubauen.
Es ist auch langsamer, wenn Du ihn nur einmal aufbaust. Zumindest nur wenn man das Minimum haben will.
Dir ist klar dass zumindest ich von einem Suchbaum geredet habe, ja?
sicherlich ist es ihm klar. erstans stand es am anfang so da,
DEvent schrieb:
Ich würde einfach einen binären Baum nehmen, nach dem Einfügen ist der min. Wert dann im linken Unterbaum, der max. Wert im rechten Unterbaum.
und zweitens gelten seine aussagen alle für suchbäume. ich denke nicht, daß sie für andere bäume gelten.
-
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.
-
volkard schrieb:
finix schrieb:
Jester schrieb:
finix schrieb:
Natürlich ist es Schwachsinn den Baum jedesmal neu aufzubauen.
Es ist auch langsamer, wenn Du ihn nur einmal aufbaust. Zumindest nur wenn man das Minimum haben will.
Dir ist klar dass zumindest ich von einem Suchbaum geredet habe, ja?
sicherlich ist es ihm klar. erstans stand es am anfang so da,
DEvent schrieb:
Ich würde einfach einen binären Baum nehmen, nach dem Einfügen ist der min. Wert dann im linken Unterbaum, der max. Wert im rechten Unterbaum.
und zweitens gelten seine aussagen alle für suchbäume. ich denke nicht, daß sie für andere bäume gelten.
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.
-
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).