Effizienz des Speichermanagers

[Namenloser]

Zitat von Patito:

Dein B+-Tree schlägt sich offensichtlich ganz gut. Der RBTree aus der FPC-STL ist aber wohl nicht gerade der beste.
Interessant wäre noch, wenn Du das ganze noch mit dem TAVLTree aus der FCL vergleichst.

Der scheint wirklich ziemlich schnell zu sein, zumindest wenn er erst mal einen Pool an TreeNodes angelegt hat, die er dann recyclen kann:

Code:

B+ 1000000 Inserts: 447
B+ 1000000 Locates: 280
B+ 500000 Removes: 201
B+ 500000 Reinserts: 241

SL 1000000 Inserts: 713
SL 1000000 Locates: 212
SL 500000 Removes: 324
SL 500000 Reinserts: 347

AVL 1000000 Inserts: 623
AVL 1000000 Locates: 259
AVL 500000 Removes: 73
AVL 500000 Reinserts: 91

RB 1000000 Inserts: 1345
RB 1000000 Locates: 849
RB 500000 Removes: 1050
RB 500000 Reinserts: 721

Falls die Zahlen etwas anders sind: Ich hab in meinem Benchmark-Code etwas Unsinn gefunden und ausgebessert... war halt schnell mit Copy & Paste-Programmierung zusammengestrickt . Allerdings wurden trotzdem alle unter den gleichen Umständen getestet.

Das Ergebnis finde ich interessant, weil man, wenn man bei Google nach Empfehlungen für balancierte Bäume sucht, eigentlich immer liest, dass AVL-Bäume bei häufigen Einfüge- und Löschoperationen wegen häufigem Rebalancing nicht so gut geeignet seien, insbesondere im Vergleich zu Rot-Schwarz-Bäumen.

Mich wundert es allerdings, dass die Removes hier schneller zu gehen scheinen als die Locates. Vielleicht sollte langsam mal ein repräsentativerer Test her...

[Dejan Vu]

Kannst Du den Testcode posten? Wie verhalten sich die Datenstrukturen beim Einfügen aufsteigender bzw. absteigender Schlüssel?

[Namenloser]

Der Testcode ist ziemlich hässlich und mit heißer Nadel gestrickt, aber gut:

Delphi-Quellcode:

const
  c = 500000;
begin
  Tree := TABTree.Create;

  t0 := GetTickCount64();
  for i := 1 to c do
    Tree.Insert(i,i);
  for i := 2*c downto c+1 do
    Tree.Insert(i,i);
  t1 := GetTickCount64();
  for i := 1 to c do
    Tree.Locate(i);
  for i := 2*c downto c+1 do
    Tree.Locate(i);
  t2 := GetTickCount64();
  for i :=  c - c div 2 to c do
    Tree.Remove(i);
  for i :=  c + c div 2 downto c do
    Tree.Remove(i);
  t3 := GetTickCount64;
  for i :=  c - c div 2 to c do
    Tree.Insert(i,i);
  for i :=  c + c div 2 downto c do
    Tree.Insert(i,i);
  t4 := GetTickCount64;

  Memo1.Append(Format('B+ %d Inserts: %d', [2*c, t1-t0]));
  Memo1.Append(Format('B+ %d Locates: %d', [2*c, t2-t1]));
  Memo1.Append(Format('B+ %d Removes: %d', [c, t3-t2]));
  Memo1.Append(Format('B+ %d Reinserts: %d', [c, t4-t3]));

  Tree.Free;

Analog sieht er für die anderen Datenstrukturen aus.

Also es werden immer zur Hälfte aufsteigend und zur Hälfte absteigend Daten eingefügt, gesucht, gelöscht etc.

[Dejan Vu]

Zitat von Namenloser:

Der Testcode ist ziemlich hässlich und mit heißer Nadel gestrickt, aber gut:

Eben. Gut Du testest mit Sonderbedingungen (aufsteigend, absteigend einfügen). Da wirst Du -zumindest im AVL und RB- eine Worst Case erwischen. Die müssen ja beinahe bei jedem Einfügen ausbalanciert werden.

Hmmm... oder gleicht sich das aus?

Teste doch mal zusätzlich mit Random-Werten. Achtung: Die Skiplist ist nicht ohne weiteres geeignet zur Aufnahme identischer Werte, müsstest du prüfen. Alternativ erstellst Du dir eine Liste mit 1Mio Einträgen, mischst die mit Fisher-Yates und fügst dann die Werte ein. Ist ja auch Random.

Ich teste jedenfalls immer so.

[Patito]

Zitat von Namenloser:

Das Ergebnis finde ich interessant, weil man, wenn man bei Google nach Empfehlungen für balancierte Bäume sucht, eigentlich immer liest, dass AVL-Bäume bei häufigen Einfüge- und Löschoperationen wegen häufigem Rebalancing nicht so gut geeignet seien, insbesondere im Vergleich zu Rot-Schwarz-Bäumen.

Die AVL-Trees sollten wohl etwas langsamer beim Insert/Remove und dafür etwas schneller beim Locate seien.
Meinen eigenen RB-Tree verwende ich deshalb so gerne, da er ein wenig schneller bei den Masseninserts ist als der AVL-Tree.

Massen-Inserts habe ich immer - Locates und andere Operationen treten oft nicht so gehäuft auf.
Daher denke ich, dass für die Praxis ein RB-Tree oder B-Tree etwas besser als der AVL-Tree sein sollte.
Den AVL-Tree der FCL zu schlagen ist aber nicht leicht.

Zitat von Namenloser:

Mich wundert es allerdings, dass die Removes hier schneller zu gehen scheinen als die Locates. Vielleicht sollte langsam mal ein repräsentativerer Test her...

Ich teste meine Container einmal mit einer sortierten Liste, und einmal mit einer zufällig zusammengewürfelten Liste.
Die sorted Inserts finde ich recht wichtig, da man damit Masseninserts oft wesentlich beschleunigen kann.

Am Memory-Manager kann man natürlich auch viel herumspielen...
Bei Single-Threaded Sachen hat mir das keinen wirklichen Vorteil gebracht - da poolt der Speichermanager oft selber gut genug.
Sobald aber Multi-Threading ins Spiel gekommen ist, ist bei mir Pooling richtig wichtig geworden.

[Dejan Vu]

Kurze Zwischenfrage: Müssen die Elemente eigentlich sortiert sein? Braucht man doch gar nicht so häufig.

[Patito]

Zitat von Dejan Vu:

Kurze Zwischenfrage: Müssen die Elemente eigentlich sortiert sein? Braucht man doch gar nicht so häufig.

Nunja, Einfügen in sortierter Reihenfolge ist eben je nach Containern-Implementierung gern mal 3x so schnell
wie Einfügen in chaotischer Reihenfolge.

Bei der Implementierung von Containern hat man an manchen Stellen die Wahl, ob man Sachen eher links oder rechts
einfügt, und ob man zuerst auf < oder > prüft. Damit kann man dem Container eine Lieblings-Reihenfolge einprogrammieren,
die dann schneller funktioniert.

[Dejan Vu]

Zitat von Patito:

Zitat von Dejan Vu:

Kurze Zwischenfrage: Müssen die Elemente eigentlich sortiert sein? Braucht man doch gar nicht so häufig.

Nunja, Einfügen in sortierter Reihenfolge ist eben je nach Containern-Implementierung gern mal 3x so schnell
wie Einfügen in chaotischer Reihenfolge.

Dann kennst Du aber Dictionaries schlecht. Die sind O(1), im Gegensatz zu den hier vorgestellten Strukturen, deren Einfügeverhalten vom Aufwand O(log n) ist. Auch Suchen, Löschen etc. ist bei Dictionaries O(1), würde also alle hier vorgestellten Strukturen um *Längen* schlagen. Es ist übrigens -gut programmiert- vollkommen egal, ob man 1000 oder 100.000.000.000 Elemente in einer Dictionary vorhält (solange der RAM das aushält). Der Aufwand ist immer gleich, die Teile sind also immer gleich schnell. Ein Baum wächst und somit wird das Laufzeitverhalten auch immer schlechter, ist zwar sublinear, also log n, aber immer noch schlechter als gar keine Verlangsamung.

Nebenbei kannst Du hier keine Faktoren angeben, denn z.B. das Einfügen in eine sortierte Liste ist (ggü einer unsortierten Liste) nicht gerne mal 3x so schnell, sondern -je nach Anzahl- auch ruhig mal 10000000000x so schnell.

Zitat von Patito:

Damit kann man dem Container eine Lieblings-Reihenfolge einprogrammieren,
die dann schneller funktioniert.

Wenn man den Container auch noch an die speziellen Bedürfnisse anpassen muss, taugt so ein Container ja nur bedingt.

Die Frage lautet also: Wozu muss die Liste sortiert sein? Der Namenlose hat den B+-Baum im Rahmen einer Lehrveranstaltung Programmiert (klasse), aber im Allgemeinen haben diese Strukturen keine sonderliche Verbreitung, weil man eben nicht sonderlich oft sortierte Listen benötigt.

Ach, wurde ein (binomial) Heap schon probiert? Müsste ich mal raussuchen...

[Namenloser]

Zitat von Dejan Vu:

Die Frage lautet also: Wozu muss die Liste sortiert sein? Der Namenlose hat den B+-Baum im Rahmen einer Lehrveranstaltung Programmiert (klasse)

Naja, nur dafür hätte ich es wohl auch nicht gemacht. Eine sortierte Liste braucht man z.B. hierfür. Ein Binomialheap ist da auch schon im Einsatz, reicht aber nur für eine der beiden Datenstrukturen.

Zitat von Patito:

Ich teste meine Container einmal mit einer sortierten Liste, und einmal mit einer zufällig zusammengewürfelten Liste.
Die sorted Inserts finde ich recht wichtig, da man damit Masseninserts oft wesentlich beschleunigen kann.

Ich hatte erst mal nur Sorted-Inserts getestet, weil es eigentlich spannender ist. Für wirklich zufällige Inserts bräuchte man theoretisch gar keinen balancierten Baum.

Für einen umfangreichen Test muss natürlich beides getestet werden, das ist klar.

[Dejan Vu]

Zitat von Namenloser;1255722...Eine sortierte Liste braucht man z.B. [url=https://en.wikipedia.org/wiki/Bentley%E2%80%93Ottmann_algorithm:

hierfür[/url].

Alles klar.

Zitat:

Für wirklich zufällige Inserts bräuchte man theoretisch gar keinen balancierten Baum.

Aber Du weißt ja nicht, wie die Sachen reinkommen. Daher neben der theoretischen Betrachtung der Standardfälle (aufsteigend, absteigend sortiert, zufällig) auch Laufzeitmessungen über alle Szenarien, um das Verhalten im Code zu analysieren und versteckte Bottlenecks zu lokalisieren. Aber das hättest Du ja gemacht, wie Du schreibst.

Schnellste sortierte Liste (bezüglich Insert/Update/Delete/Locate/)? Interessante Aufgabenstellung.