So, ich habe jetzt noch mal einen saubereren Test in einem neuen Projekt geschrieben.
Delphi-Quellcode:
B+ Tree
Ascending linear (1000000)
Insert: 451 ms
Locate: 273 ms
Remove: 543 ms
Descending linear (1000000)
Insert: 661 ms
Locate: 332 ms
Remove: 340 ms
Random (1000000)
Insert: 1858 ms
Locate: 1006 ms
Remove half: 810 ms
Reinsert half: 976 ms
AVL Tree
Ascending linear (1000000)
Insert: 340 ms
Locate: 270 ms
Remove: 255 ms
Descending linear (1000000)
Insert: 314 ms
Locate: 274 ms
Remove: 265 ms
Random (1000000)
Insert: 1604 ms
Locate: 1499 ms
Remove half: 946 ms
Reinsert half: 933 ms
Skiplist
Ascending linear (1000000)
Insert: 370 ms
Locate: 204 ms
Remove: 180 ms
Descending linear (1000000)
Insert: 233 ms
Locate: 255 ms
Remove: 337 ms
Random (1000000)
Insert: 3095 ms
Locate: 3490 ms
Remove half: 1758 ms
Reinsert half: 1818 ms
RB Tree
Ascending linear (1000000)
Insert: 865 ms
Locate: 387 ms
Remove: 1319 ms
Descending linear (1000000)
Insert: 1043 ms
Locate: 383 ms
Remove: 1643 ms
Random (1000000)
Insert: 3282 ms
Locate: 1682 ms
Remove half: 2139 ms
Reinsert half: 1780 ms
Einige Beobachtungen:
- Aus irgendeinem seltsamen Grund tritt im neuen Projekt der Engpass mit dem FPC-Speichermanager nicht mehr auf – wovon der AVL-Baum jetzt erheblich profitiert.
- Das Optimierungslevel hat starken Einfluss auf die Performance beim B+-Baum. Der Benchmark ist mit -O3 kompiliert, wie das Testprogramm zuvor auch. Mit der Standardeinstellung -O1 hab ich mich gefragt, warum das Teil plötzlich so langsam ist im Vergleich.
- Beim AVL-Baum hat sich bestätigt, dass das Löschen etwas schneller ist als das Finden. Caching-Effekte? Edit: Achso, nein, ist ja klar: Während dem Löschen wird der Baum ja auch kleiner und dadurch wird das Auffinden der Knoten immer schneller.
- Gewundert hat mich, dass der B+-Baum beim linearen Suchen eher langsamer ist als der AVL-Baum, ihn dafür aber deutlich und reproduzierbar bei der Random-Suche schlägt.
Eine Sache habe ich am B+-Baum übrigens noch geändert, und zwar habe ich innerhalb der Knoten von linearer auf binäre Suche umgestellt. Ich hatte schon vorher für beides den Quellcode dastehen, aber hatte standardmäßig die lineare Suche verwendet, weil sie im Mittel schneller schien. Allerdings ist das vor allem darauf zurückzuführen, dass das aufsteigende Einfügen schneller geht. Das absteigende Einfügen ist dafür deutlich langsamer (ist auch logisch). Deshalb setze ich jetzt aus Gründen der Vorhersagbarkeit wieder auf binäre Suche.
Source Code für den Benchmark ist im Anhang, falls jemand seine eigenen Implementierungen testen will. Am Anfang des Programms sind $DEFINES für die zu testenden Klassen, sodass ihr das Programm auch leicht kompilieren könnt, wenn ihr nicht alle Units habt (z.B. unter Delphi). Mitgeliefert wird nur die Skiplist von alzaimar.