Red/Black-Tree
-
Ein RB-Tree hat höchstens Höhe 2 log(n+1) und ein AVL-Baum afaik log(n+1). Somit ist die Suche beim AVL-Tree im Durchschnitt günstiger als beim RB-Tree..
-
Dann verstehe ich aber nicht wieso sie bei einer Map (die ja vorzugsweise dem Auflösen von Key->Value dient und daher meistens sehr suchlastig benützt wird) einen RB-Tree und keinen AVL-Tree verwenden.
RB-Trees scheinen mir ja auf Grund ihres geringeren Aufwands bei Insert/Delete für stark dynamische Datenstrukturen eine Option zu sein.
MfG SideWinder
-
Vermutlich wirst du sehr viel mehr suchen als ändern müssen, damit sich der AVL-Tree lohnt. Die Implementierer der Map wissen nicht, wie ihre Map einmal verwendet werden wird, deshalb müssen sie Annehmen, dass man so und so viel sucht und so und so viel verändert. Der Unterschied bei der Suchzeit zwischen den beiden Bäumen scheint ausreichend gering zu sein, dass die verringerten Kosten zum Verändern das locker wettmachen. Letztlich ist das aber alles nur statistisches Rumgetue, oder es hat sich aus der Praxis ergeben. Es ist O(log n) zum Suchen, mehr finde ich in den meisten Fällen nicht besonders wichtig.
Wenn du total statische Daten hast, kannst du sowieso erstmal noch viel mehr Aufwand betreiben, um die Datenstrukturen aufzubauen. Für das reine Suchen eine Hashtable, für größer/kleiner suchen einen AVL-Baum oder bei riesigen Datenmengen einen B-Baum, der die Cache-Größen berücksichtigt.
Du kannst aber auch einfach die std::map benutzen und das wird dann schon passen.
-
Hmm wenn ich das hier so lese wäre es gut wenn man die Implementation des Maps einfach per Policy bestimmen könnte. Dann kann man selbst aussuchen was für den eigenbedarf besser wäre
BR
Vinzenz
-
Unfortunately, AVL trees typically do not contain a parent pointer,
which means that traversal is slower than with an RB-tree that has
parent pointers. That's because traversing to a sibling node requires
starting over at the root, rather than only moving up the tree as far
as you need to.das ist doch ein implementierungsdetail, meine avl-tree node schaut so aus von den membern her:
T* m_pLeft; T* m_pRight; T* m_pParent; DSINT m_Height;dadurch ist sie bei 32bit systemen auf 32byte alligned und bei 64bit systemen auf 64byte.
Bei einem test, bei dem ich bei hunderttausenden dreiecken die eckpunkte mergen möchte, indem ich, falls ein eckpunkt noch nicht in der map vorhanden ist, den neu in die map stecke, ist mein AVL ca 30% fixer als die map der STL-port und ca 20% fixer als die map von der microsoft stl.
meiner persönlichen überlegung nach ist ein AVL-tree schneller, weil:
- ist schneller beim durchsuchen
- langsammer beim einfügen
da aber zum einfügen erstmal die richtige position "gesucht" wird, hebt sich das paar mal mehr rotieren gegen die suchdauer auf.
- löschen? da eine node weiß wo sie steckt, dürfte die zeit dabei konstant sein (natürlich kommt rotieren hinzu)
-
@rapso: Schau dir ganz einfach mal die STL-Implementierung an. Die bringen meistens haufenweise Überprüfungen, Verkomplizierungen, etc. mit sich. Wenn es um Performance geht würde ich jetzt nicht unbedingt auf die MSVC-STL setzen.
Ich habe jetzt erstmal einen RB-Tree implementiert, da ich den sowieso noch nicht gekannt habe und mich so gut einarbeiten kann und zweitens sich die Entwickler der JavaVM und der einzelnen STL-Ports sicher auch Gedanken gemacht haben.
Rapsos Überlegungen stimmen dann ja wohl eher für große Bäume wo ein Höhenunterschied von Faktor 2 sich ordentlich auf die Performance auswirken kann. Bei Bäumen bis zu 50 Elementen würde ich aber doch dem RB-Tree den Vorrang geben. Die 3 Such-Schleifen-Durchläufe mehr machen imho den Rotationsaufwand nicht wett.
MfG SideWinder
-
@rapso: Zum 32bit-Alignment deines Nodes: Wo ist da der Data-Ptr? Du als Low-Level-Fuchs kannst mir dann doch sicher auch hier noch helfen:
Bei mir sieht das noch so aus:
Element data; // sizeof(Element) Node* up; // 32 Bit Node* left; // 32 Bit Node* right; // 32 Bit Bool color; // 8 BitWäre folgendes besser?
Element* data; // 32 Bit Node* up; // 32 Bit Node* left; // 32 Bit Node* right; // 32 Bit Int color; // 32 Bit;MfG SideWinder
-
Wenn rapso zum Einfügen auch noch vorher suchen muss, kann ich mir gut vorstellen, dass die Rotationsdauer vernachlässigbar wird, was dann ein Pluspunkt für den AVL ist. Das ist aber nicht etwas, nach dem ich die STL implementieren könnte, weil ich nicht in jedem Fall davon ausgehen kann, dass ich vorher suchen muss (EDIT: Zum Beispiel beim Einfügen von mehreren benachbarten Werten muss ich beim RB Baum weniger oft die Einfügeposition suchen). So ne Policy wäre wirklich nicht schlecht.
-
Und nochmal BTW@rapso: Würdest du mir eventuell deine AVL-Baum-Implementierung schicken damit ich sie mit meinem R/B-Baum vergleichen kann?
MfG SideWinder
-
einen dataptr hab ich nicht, da die node ein template ist, dass sich um die objekte legt (die sind bei mir auch 32byte alligned, zumeist). dadurch kann man ein wenig performance gewinnen, weil beim durchgang durch den tree immer auf die data-objekte (wegen dem vergleich) durchgeführt wird, das resultiert in random data-reads (mehr als schon sowieso wegen dem baum vorhanden ist).
du solltest immer versuchen zumindestens 32bit zu allignen, 32byte is schon optimal für die meisten cpus.
wenn du immer auf 32bit allignst, dann könntest du die untersten bits der pointer als deinen bool für Red/Black nehmen und würdest auch ein wenig speicher sparen, was am ende fixer sein kann.und ja, für 50 elemente könnte ein R/B vielleicht schneller sein, vielleicht ist das rotieren aber auch nicht so teuer dass ein AVL fixer ist. aber so kleine dinge (50 elemente) sind meistens nicht performancerelavant und wenn doch, dann kann man sich speicherintensivere systeme ausdenken die besser als O(log n) sind ;).