nicht angemeldet
Hi Cruz,
Ich vermute, der _prozentuale_ Performance-Gewinn wird immer proportional
zur Breite Deines Baums sein, nicht zur Gesamtzahl der Knoten.
ich glaube der Performance Gewinn hat sehr wohl etwas mit der Anzahl
der Knoten zu tun
der absolute, ja. Der relative, nein.
weil nämlich bei jedem Knoten ein neues Statement prepared wird und
gerade da lohnt es sich ja. Je mehr Knoten, umso mehr prepared
statements (d.h. jedesmal performance gewinn).
Ja.
Und je mehr Knoten, umso größer ist der Anteil der gesamten Laufzeit,
Nein. Wieso auch? Oder hat Dein Programm irgend einen nennenswerten
Grund-Overhead? Ich bin ganz automatisch davon ausgegangen, daß seine
Laufzeit O(n) bezüglich der Knotenzahl ist, da Du anscheinend den ganzen
Baum traversieren willst.
d.h. der _prozentuale_ Gewinn müsste auch steigen.
Wenn Du lauter binäre Knoten hast, dann spart das prepare relativ wenige
Operationen.
Hast Du aber eine Verzweigung von hunderten von Kind-Knoten pro Ebene
(etwa einen DOM-Baum eines HTML-Dokuments), dann reduzierst Du die Zahl
der Statement-Analysen von <n> auf 1. Das kann viel ausmachen - und genau
das ist der optimale Einsatzfall für Dein Vorgehen: Eine auf spezielle
Eigenschaften der Daten ausgelegte Optimierung.
Bei einem Baum mit einem Verzweigungsgrad von 1 (i. e. einer linearen
Liste) gewinnst Du _nichts_ - egal, wie groß oder klein der Baum ist.
Deshalb hängt der _relative_ Gewinn vom Verzweigungsgrad des Baums ab,
nicht von seiner Größe.
Deshalb fragte ich nach der mittleren Breite eines Knotens.
Insbesondere halte ich binäre Bäume für relativ häufig, und bei denen wäre
Dein Gewinn relativ klein. Deine Anwendung könnte natürlich 'degenerierte'
Daten haben - aber die von Dir genannten Zahlen lassen mich auf 'schlanke'
Bäume schließen.
Viele Grüße
Michael