Stress für B-Baum
-
Ad aCTa schrieb:
Der B-Baum ist immer balanciert und kann nicht (wirklich nie) zur Liste werden.
ein normaler b-tree ist nicht balanciert...
Ad aCTa schrieb:
der binäre Baum der std::map ist um Längen schneller beim Inserten
das ist auch kein std. binary tree
stl map schrieb:
Implemented using a self-balancing binary search tree.
also eher rb oder avl tree
-
-
> du hast mal von nem Vektor geredet.
Jap, der genannte Vektor beinhaltet die Zeiger zu den Childnodes.
> schau mal, ob dir der nicht voll läuft und er dann auf einmal deine ganze schöne Struktur umkopiert...
Wie kann ich das verstehen? Bisher habe ich die Elemente, die ich anfüge, immer mit
push_backneu alloziiert. An sich habe ich nur 2 Stellen im Code, an denen ich den Vektor beeinflusse:// Diese Stelle entscheidet, ob beim Teilen eines Knotens der zu teilende Knoten selber Children hat. Die müssen dann auf die neuen beiden Teilnodes verteilt werden. /* Simuliertes Beispiel: Baum der Ordnung 2, Node voll bei 2*2-1 = 3 Schlüsseln: 2 5 <---------- Ich befinde mich in diesem Knoten und sehe: / | \ | / | \ | \ \|/ 7 9 11 <---------- voll, muss geteilt werden und Children / | | \ müssen verteilt werden, denn Knoten hat / | | \ auch noch Childnodes 6 8 10 12 14 2 5 9 / | | \ | \ 7 11 /\ / \ 6 8 10 12 14 */ //children ist der Vektor mit Zeigern auf Kindknoten // left und right sind die neuen Teilnodes, auf die die Zeiger nun verteilt werden if(children[position]->children.size() > 0) for(unsigned i = 0; i < children[position]->children.size(); i++) { if(i < order) left->children.push_back(children[position]->children[i]); else right->children.push_back(children[position]->children[i]); }Voller als 2 * Ordnung wird der Vektor nicht. Die Reihenfolge behalte ich ja eigentlich auch immer bei.
-
noobLolo schrieb:
Ad aCTa schrieb:
Der B-Baum ist immer balanciert und kann nicht (wirklich nie) zur Liste werden.
ein normaler b-tree ist nicht balanciert...
Dann wartet http://de.wikipedia.org/wiki/B-Baum auf deine Korrektur:
-
Bashar schrieb:
noobLolo schrieb:
Ad aCTa schrieb:
Der B-Baum ist immer balanciert und kann nicht (wirklich nie) zur Liste werden.
ein normaler b-tree ist nicht balanciert...
Dann wartet http://de.wikipedia.org/wiki/B-Baum auf deine Korrektur:
sry dachte das b-tree steht als abkürzung für einen binary-tree
-
wikipedia schrieb:
Die häufigste Interpretation ist, dass B für balanciert steht. Weitere Interpretationen sind B für Bayer, Barbara (nach seiner Frau), Broad, Bushy, oder Boeing, da Rudolf Bayer für Boeing Scientific Research Labs gearbeitet hat.
-
So, ich habe mir das noch mal mit 1000 Elementen bei einer std::map angeschaut. Die Map brauchte 1mal 15ms. Diese Zahl kommt mir verdächtig vor, könnte das nicht die Zeit sein, die der Scheduler vom OS mein Programm warten lässt? Wenn dem so ist, dann brauchen meine Insertions einfach ingesamt länger, und umso mehr Takte ich benötige, desto mehr Wartezeiten bekommt mein Programm.
Toll, das war jetzt ein Schuss für den Ofen, jetzt weiß ich das, was ich vorher wusste: mein Insert ist langsam.
Weiß jemand, wie ich den Flaschenhals in einem Code finden kann? Es sind ca. 100 Zeilen.
-
Hast du's mal mit einem Profiler versucht?
-
Hm... mit denen habe ich keine Erfahrnung. Kannst du mir einen empfehlen?
-
Nö, aber für den Anfang reicht ja irgendeiner.
-
Ich habe mir jetzt mal einen gesucht, der sehr schön mit meiner IDE arbeiten kann. Ganz nette Sache, er zeigt mir also an, wie oft welche Funktionen aufgerufen wurden. Er sagt mir, dass insert() oft aufgerufen wurde. Schön, das weiß ich schon. Aber richtig Auskunft kann er mir nicht geben. Ohne jetzt genau den Algorithmus verstehen zu müssen, sieht jemand in diesem Code irgendeine Art "no-go"?
template <unsigned order, typename key_t, typename payload_t, typename compare_t, typename allocator_t> std::pair<typename node<order, key_t, payload_t, compare_t, allocator_t>::iterator, bool> node<order, key_t, payload_t, compare_t, allocator_t>::insert(const std::pair<key_t, payload_t>& dp) { // greater_equal, smaller_equal search: typename std::list<pointer>::iterator key = std::find_if(payload.begin(), payload.end(), bind2nd(compare_t(), dp.first)); if(!children.empty()) { // it's an inner node if(key != payload.end()) { // there is a key with those condition if((*key)->first != dp.first) { // key is not equal to the needle typename std::list<pointer>::difference_type position = std::distance(payload.begin(), key); // is the child candidate full? if(children[position]->payload.size() == 2 * order - 1) { position = split(dp, position); // then split it and get new position to search } return children[position]->insert(dp); // map position on childnodes and search in subtree } else return std::make_pair(iterator(this, key), false); // found in inner node } else {// there is not such a position if(children.back()->payload.size() == 2 * order - 1) { // is the node full? typename std::list<pointer>::difference_type position = payload.size(); position = split(dp, position); // split it and return new position to continue searching return children[position]->insert(dp); } return children.back()->insert(dp); // the very right subtree may contain the key } } else { if(key == payload.end() || (*key)->first != dp.first) { // key does not exist or is too big --> we can insert pointer n = allocate(1); construct(n, dp); std::list<pointer>::iterator pos = payload.insert(payload.end(), n); // insert at the end payload.sort(cmp()); // sort the payload list return std::make_pair(iterator(this, pos), true); } else return std::make_pair(iterator(this, key), false); // found in leave node } }Nur von Seiten der Performance. Ich habe den Algorithmus einfach mal umgesetzt, und wüsste nicht, wie ich das ummodeln sollte, damit es schneller wird.
-
Ad aCTa schrieb:
Ich habe mir jetzt mal einen gesucht, der sehr schön mit meiner IDE arbeiten kann. Ganz nette Sache, er zeigt mir also an, wie oft welche Funktionen aufgerufen wurden. Er sagt mir, dass insert() oft aufgerufen wurde.
Eigentlich sollte er auch anzeigen, welche Anweisung wie oft durchlaufen wurde und wieviel Zeit darin verbracht wurde.
Schön, das weiß ich schon. Aber richtig Auskunft kann er mir nicht geben. Ohne jetzt genau den Algorithmus verstehen zu müssen, sieht jemand in diesem Code irgendeine Art "no-go"?
Naja no-go vielleicht nicht, aber ein paar Sachen fallen mir schon auf.
- Warum eine Liste und kein Vektor?
- Wenn schon Liste, warum enthält sie dann Pointer und nicht Objekte?
- Du fügst unten einfach mal ein und sortierst die Liste dann. Zum Einfügen in eine sortierte Liste gibt's aber effizientere Verfahren.Ich muss aber zugeben, dass ich den Code nur kurz überflogen habe.
-
> - Wenn schon Liste, warum enthält sie dann Pointer und nicht Objekte?
Weil diese Objekte von einem Allokator kommen. Der gibt mir nur Pointer.
> Warum eine Liste und kein Vektor?
> Du fügst unten einfach mal ein und sortierst die Liste dann. Zum Einfügen in eine sortierte Liste gibt's aber effizientere Verfahren.Ich hab da lange rumüberlegt. Ich wollte gerne einen Container haben, bei dem Einfügen in der Mitte günstig ist, am besten gleich sortierend einfügt. Ich verstehe nicht, warum es in der Standardbibliothek nicht eine automatisch sortierende Liste gibt, der einzige Container, der das kann ist std::set. Außerdem fand ich die splice()-Methode recht nett auf mein Problem zugeschnitten, die Liste zu teilen und automatisch zu löschen. Zuletzt hielt ich list::sort() dem std::sort für überlegen, in der Hoffnung, dort am meisten Performance raus zu holen. Dem ist scheinbar nicht so.
Zugegeben, was gescheites, wie man auf n Elemente n + 1 andere draufmappen kann, ist mir noch nicht eingefallen. Bis jetzt taten es vector und list.
-
Ad aCTa schrieb:
> - Wenn schon Liste, warum enthält sie dann Pointer und nicht Objekte?
Weil diese Objekte von einem Allokator kommen. Der gibt mir nur Pointer.
Ich kenn mich mit Allokatoren nicht aus, aber warum ist das so? Die STL-Container arbeiten mit dem Standard-Allokator-Interface und enthalten Objekte.
-
> Die STL-Container arbeiten mit dem Standard-Allokator-Interface und enthalten Objekte.
Ne, das glaub ich nicht. Schließlich werden ja die Elemente, die du in einen Container packst, kopiert. Der Allokator ist eigentlich nur das:
T* memory = allocator.allocate(1); allocator.construct(memory, T()); // ... allocator.destroy(memory); allocator.deallocate(memory);z.B. ein malloc() mit einem placement-new.
Bzgl. dieser Vektor-Liste-Angelegenheit: Vielleicht regele ich es einfach so, dass es einen Payload-Typen gibt, der immer einen Zeiger auf den Nächsten Node hat. Dieser Payload-Typ kommt in einen Vektor. Das allererste Element hat zwar einen Next-Zeiger, ist aber sonst leer. Dann muss ich vielleicht nicht mehr so mit diesen 2 Vektoren/Listen rumhantieren.