Problem bei der Wahl des Containers

Ad aCTa

Hallo!
Problemschilderung: Ich bin (immernoch) dabei, meinen B-Baum zu programmieren, und stoße hier auf ein kleines Problem: Ein B-Baum hat, sagen wir bei einer Ordnung von 5, mindestens 5 und höchstens 2 * 5 = 10 Kindverweise, demnach mindestens 5 - 1 = 4 und höchstens 2 * 5 - 1 = 9 Schlüssel(/Wert-Paare):
Beispielbelegung in einem Knoten:

+----+----+----+----+----+
          | k1 | k2 | k3 | k4 | k5 |    = 5 (Schlüssel-Wert-Paare)
          +----+----+----+----+----+
          /    |    |    |    |     \
        c1    c2    c3   c4   c5    c6  = 6 (Pointer, node*)

Ich suche jetzt einen geeigneten Container, um diese 2 Sequenzen von Schlüssel/Wert-Paaren und Zeigern zu modellieren. Bis jetzt habe ich einen std::vector mit den Schlüssel/Wert-Paaren und einen std::vector mit Zeigern benutzt. Das klappte bisher auch ganz gut, da ich random-access benötige, wenn ich bei einer Suche in die Mitte der Sequenzen zugreifen muss.

Jetzt will ich den Einfüge-Algorithmus implementieren, und da ist das Problem:
Wenn ein Knoten voll ist, muss ich ihn ja teilen und das mittlere Schlüssel/Wert-Paar in den Parent-Node nach oben bringen etc und muss dieses Paar auch mal in die Mitte des Vectors einsetzen. Bei der Aktion wird am vector ganz schön viel rumkopiert, bei einer Ordnung von 1024 (damit der Baum schön flach bleibt) kann das sehr schmerzhaft werden (frisst RAM).
Einfügen in der Mitte ist bei std::list natürlich günstiger, nur, dann habe ich kein random access mehr, wenn ich den Baum durchsuche und meine Suchlaufzeit schießt durch die Decke. Außerdem: um den richtigen Offset in den Vectoren zu finden, nutze ich die binäre Suche, welche bei einer Liste nicht existiert. Das verschlimmert die Suchlaufzeit noch mehr.

Wie kann ich verfahren? Welcher Container ist der richtige?

l'abra d'or

QList macht das nicht dumm:
http://doc.qt.nokia.com/4.6/qlist.html#details

Das Problem bei dir sind ja die erforderlichen Kopien der std::pairs (oder was du für Schlüssel/Wert-Paar hernimmst).
Nachteil des QList-Vorgehens: die Items liegen alle im Freispeicher, also nicht auf dem Stack, Es gibt also auch wieder nen gewissen Overhead beim Einfügen neuer Elemente. Du kannst natürlich so nen Container immer mit einer MAX Länge initialisieren und dann Elemente immer mit SWAP austauschen.

Wenn dir das Schreiben eines eigenen Containers zu aufwändig ist musst du halt selber schauen, ob dir ein std::advance (für Index-Zugriff bei ner std:list) gegenüber std::vector::insert() zu langsam ist oder umgekehrt. Bei maximal 9 Elementen denke ich advance ist ausreichend schnell.

Ad aCTa

Ich glaube nicht, dass Qt daran was ändern könnte, vectoren sind bzgl. dieses Problems einfach theoretisch unperformant. Außerdem wollte ich dieses riesige Monstrum jetzt nicht auch noch involvieren.

> Das Problem bei dir sind ja die erforderlichen Kopien der std::pairs (oder was du für Schlüssel/Wert-Paar hernimmst).

Das Problem ist, dass man nicht performant in die Mitte eines Arrays einfügen kann. Deshalb muss neuer, größerer Speicher angefordert und das alte Array kopiert werden. (Ließ Array als std::vector).
Nebenbei: es muss oft in die Mitte eingefügt werden, da das Array sortiert ist. Wenn ich es an das Ende pushen würde und anschließend neu sortiere, hätte ich das Ei des Kolumbus nicht gefunden, denke ich.

Bei Größenordnungen wie 9, 10 etc. mag das ja alles noch okay sein. Wenn man die Vorzüge des B-Baums richtig ausnutzen will, kann diese Zahl ganz schön groß werden. Eigentlich sollte der Baum bei einer größer werdenen Ordnung schneller, und nicht langsamer werden.

l'abra d'or

Ich dachte jetzt nicht dass du Qt installieren sollst, sondern einen eigenen Container auf dein Problem zugeschnitten und für deine Zwecke ausreichend std-algorithm-kompatibel ist.

Um ein Einfügen in der Mitte zu verhindern kannst du ja die Indizes in nem std::vector<size_t, size_t> mappen. Ist wohl schneller als im vectorstd::pair rumzukopieren oder ein std::advance. Ich weiß halt nicht wie sich das in deine Algorithmen einfügt.

Ad aCTa

Ich drücke mich wohl nicht ganz richtig aus...
Ein Beispiel:

Gegeben: B-Baum dritter Ordnung, key = std::string, value = int
Einzufügen: paar = ("Peter"|45)
Fall-Situation:

Poition j:           j0       j1      j2
========        +--------+---------+------+
                | Arnold | Paulina | Raul |
                +--------+---------+------+
               /         |         |       \    
Subtrees c:   c0         c1        c2      c3
========

Einfüge-Tree ji für paar = c2

Poition j:           j0       j1      j2
========        +--------+---------+------+
                | Arnold | Egbert  | Raul |
                +--------+---------+------+
               /         |         |       \    
Subtrees c:   c0         c1        c2      c3
========                           |
                           +-------+-------+---------+----------+--------+
                           | Felix | Franz | Johanna | Lennardt | Marcel |
                           +-------+-------+---------+----------+--------+

Der Subtree ist voll, der Datensatz Johanna in der Mitte muss nach oben, damit Peter eingefügt werden kann:

[u]Ergebnis:[/u] 

Poition j:           j0       j1      j2        j3
========        +--------+---------+---------+------+
                | Arnold | Egbert  | Johanna | Raul |
                +--------+---------+---------+------+
               /         |         |         \       \
Subtrees c:   c0         c1        c2         c3      c4
========                           |           \
                           +-------+-------+    +----------+--------+-------+
                           | Felix | Franz |    | Lennardt | Marcel | Peter |
                           +-------+-------+    +----------+--------+-------+

Johanna wird oben in der Mitte des Vectors eingefügt, und unten gelöscht. Diese erase und insert-Vorgänge sind in einem Baum 3. Ordnung ja okay, aber z.B. bei 1024 ist das sehr aufwändig. Bei einer Liste wäre der Index-Zugriff in der Mitte ebenfalls sehr teuer.

Ad aCTa

Weiß denn da keiner Rat?

Ad aCTa

Gibt es eigentlich eine Möglichkeit, einen Vektor aus einem alten zu erzeugen, ohne dass er die Inhalte kopiert? Er soll einfach physikalisch intern das selbe Array benutzen, nur nicht alles davon

std::vector<int> v{4, 7, 3, 1, 9};
std::vector<int> v2(v.begin(), v.begin() + 2); // soll aber nicht kopieren!!!
for(int n : v2)
   std::cout << n << ' ';

// Output: 4 7 3

Da könnte man bestimmt was mit Rvalue-Referenzen zusammenbauen, kann mein Compiler nur leider kaum.

So könnte ich mir z.B. die Kopier-Kosten beim Teilen des Vektors sparen.

drakon

Wenn du den vector nicht veränderst kannst du auch Iteratoren auf diese Range behalten.

Du könntest auch Zeiger auf die Elemente der gewünschten Range holen und speichern, aber du hast die gleiche Probleme, wie bei Iteratoren (wegen Invalidierung bei Veränderung des vectors).

Ad aCTa

Ich glaube, ich habe eine Idee. Ich benutze ja die pair-Vektoren u.a. auch für das finden der richtigen Position, damit ich z.B. im richtigen Subtree lande.

An sich könnte ich das ja in eine Liste verwandeln. Damit habe ich das Kopier-Problem nicht mehr, da ich neue Inhalte ja einfach einfügen kann. Wie ist so das Suchverhalten in einer sortieren Liste?
À propos: gibt es in der STL eine Liste, die gleich sortierend einfügt, also an der richtigen Stelle, dass ich nicht auch noch sort() anwenden muss? push_back() kann das ja unmöglich machen.

drakon

Ad aCTa schrieb:

À propos: gibt es in der STL eine Liste, die gleich sortierend einfügt, also an der richtigen Stelle, dass ich nicht auch noch sort() anwenden muss? push_back() kann das ja unmöglich machen.

std::set und std::multiset

unskilled

es gibt auch noch priority-que, auch wenn die hier vll nicht die klügste ist ;o)
ich würde für das erstellen eines baumes btw boost::ptr_vector oder wie der heißt verwenden - das einfügen braucht so zwar jedes mal ein new (statt eines placement news), aber dafür musst du immer nur nen paar byte umkopieren und kannst trotzdem ne binäre suche nutzen... aber ich hab kein plan, ob das das non plus ultra ist... das durchiterieren wird so jeweils eine dereferenzierung länger dauern - das kann man also denke ich vernachlässigen...

oder spricht da was dagegen?

nur eine funktion, die sortiert einfügt, kenne ich nicht - aber sind ja nur 2 zeilen ( std::(binary_)search und dann container::insert )

das ganze lohnt sich aber halt auch erst bei "richtigen" b-bäumen - und wird bei b-bäumen kleinerer ordnung viel zu lahm sein

was du auch machen könntest, wäre weiterhin vector zu nutzen und nen eigenes pair zu schreiben, was das eigentliche pair eben pimpelt(nur per pointer hält) - sollte aufs gleiche hinauskommen

bb

Ad aCTa

Hm... ja. In dem vector mit den Schlüssel/Wert-Paaren (ich nenne es ab jetzt std::pair) sind natürlich nur Zeiger enthalten, die die Objekte vom Allokator kommen (er sollte möglichst STL-kompatibel sein).

Der Algorithmus fängt so an:
k sei der zu suchende Schlüssel, x der aktuelle Knoten

Suche die kleinste Position j in den Schlüsseln von x, welche größergleich dem Suchschlüssel ist.
Wenn es ein innerer Knoten ist
Wenn so eine Position j existiert:
Wenn der Schlüssel x.k an Position j gleich k ist, wurde der Schlüssel gefunden
sonst muss der Schlüssel in einem Unterbaum x.c mit Position j sein.
...
...

In Pseudo-C++:

iterator pos = std::find_if(paare.begin(), paare.end(), compare());
if(!kindknoten.empty()) // Kinder vorhanden ---> das ist ein innerer Knoten
   if(pos != paare.end()) // Wenn diese Position existiert
     if(pos.second == k) // Wenn der gefundene Schlüssel gleich Suchschlüssel ist
        // Erfolg!...
     else
         // Der Schlüssel muss in einem der Kindknoten sein. Die Zeiger sind im Vektor "kindknoten"
         size_t j = pos - paare.begin(); // absolute Position aus Iterator bestimmen
         return kindknoten[j].suche(k); // rekrusiver Aufruf

Das klappt ja wunderbar. Angenommen, ich verwende für die Bewarung der Paar-Zeiger jetzt ein std::set, kann ich diese Berrechnung in Zeile 8 nicht durchführen. Mit der bestimme ich aber die Position im Vektor mit den Kindverweisen. Ach, das ist zum Mäusemelken.

Ad aCTa

Kann man irgendwie (außer durch Sachen wie operator -()) von einem Iterator darauf schließen, auf das wievielte Element in der Sequenz er zeigt? Ich brauche ja nur den Offset.

OhneName

Ad aCTa schrieb:

Kann man irgendwie (außer durch Sachen wie operator -()) von einem Iterator darauf schließen, auf das wievielte Element in der Sequenz er zeigt? Ich brauche ja nur den Offset.

Wie wärs mit

typename iterator_traits<input_iterator>::difference_type
  distance( input_iterator pos1, input_iterator pos2 );

?

unskilled

wieso willst du nen b-baum durch nen avl-baum implementieren?
was spricht denn ggn nen pointer-vektor und es so zu machen, wie ich geschrieben hatte?

bb

Ad aCTa

Die Pairs sind ja gepimpelt. Sie werden vom Allokator erzeugt, und diese Zeiger packe ich momentan in ein std::set (ja, es ist schon komisch, einen Baum mit einem Baum zu implementieren).

> was spricht denn ggn nen pointer-vektor und es so zu machen, wie ich geschrieben hatte?

Nun ja, das hier:

> nur eine funktion, die sortiert einfügt, kenne ich nicht - aber sind ja nur 2 zeilen (std::(binary_)search und dann container::insert)

(Statt binary_search() meinst du wohl sort()). Das Einfügen am Ende ist schön billig, aber den z.B. 1024-Elemente langen Vektor anschließend zu sortieren, ist m.E. nicht ganz ohne. Deshalb hätte ich gerne einen Container, bei dem es
entweder:
günstig ist, ist der Mitte ein zu fügen (das kann vector nicht sein)
oder:
günstig ist, ihn zu sortieren, wenn man nur schlecht in der Mitte einfügen kann

Sortieren ist nie so schnell, deshalb wollte ich das erst mal vermeinden und lieber einen Container benutzen, der beim Einfügen bereits sortiert. Der leider einzige Container, der das kann, ist std::set. Bei ihm ist Einfügen in der Mitte auch sehr günstig. Aber eigentlich wäre mir eine std::list lieber, nur, die fügt nicht sortierend ein, die müsste man dann auch erst mit list::sort() sortieren. Aber std::list hat noch ein anderes Schmankerl: splice(). Wenn ich die Liste teilen muss (wie oben geschildert), kann ich die durch splice() teilen und die alte Liste wird gleich gelöscht, eine Move-Semantik wie ich sie wollte. Aber std::set hat sowas natürlich nicht. Grrrrrrr

Ad aCTa

Hm... so gesehen kann ich auch eine std::list verwenden. Da der sort()-Algorithmus der Liste ja optimiert ist, kann das nicht der Flaschenhals sein. Nur eine paar allgemeine Fragen:

std::list<pointer> payload;

// Erzeuge einfach mal ein paar Key/Values mit dem Allokator
pointer n = allocate(5);
construct(n,     std::make_pair("Brnold", "Schwarzennegger"));
construct(n + 1, std::make_pair("Frnold", "Mustermann"));
construct(n + 2, std::make_pair("Irnold", "Schwarzennegger"));
construct(n + 3, std::make_pair("Krnold", "Hellermann"));
construct(n + 4, std::make_pair("Xrnold", "Dunklermann"));
payload.push_back(n + 3);
payload.push_back(n + 2);
payload.push_back(n + 1);
payload.push_back(n + 4);
payload.push_back(n);
payload.sort(); // Sortieren nicht vergessen!

/* Ich will jetzt das Element in der Mitte finden. Das ist wohl das unperformanteste an der Liste, der Wert ist logischweise "Irnold": */

typename std::list<pointer>::iterator half = payload.begin();
std::advance(half, payload.size() / 2); // geht das irgendwie eleganter?

/* Jetzt muss die Liste in der Mitte geteilt werden. Der mittlere Wert muss ganz raus. Den Effekt kann man durch Ausgabe ja leicht erreichen: */
for(std::set<pointer>::iterator iter = payload.begin(); iter != half; ++iter) {
   std::cout << (*iter)->first << std::endl;
}
/* Das gibt logischerweise
Brnold
Frnold
aus. Jetzt will ich das aber in eine neue Liste packen (verschieben), bloß wie? */

std::list<pointer neue_liste;
neue_liste.splice(neue_liste.begin(), payload, payload.begin(), half); // das könnte doch klappen, splice schiebt von einschließlich begin bis half, aber nimmt half nicht auf, das wollte ich
// Aber die Test-Ausgabe:
for(std::list<pointer>::iterator i = neue_liste.begin(); i != neue_liste.end(); ++i)
	std::cout << (*i)->first << std::endl;
/*
Ausgabe:
Brnold
Frnold
Brnold
Frnold
Irnold
Krnold
Xrnold

What the hell??!
*/

Was mache ich falsch?

hustbaer

Ich hab irgendwie den Eindruck, dass du dich da ein wenig in etwas verrannt hast. Wenn das Umkopieren von z.B. 1000 Zeigern zu langsam ist, dann ist vermutlich 1000 einfach zu breit, d.h. du solltest den Baum schmäler machen.