AW: Effizienz des Speichermanagers
Zitat:
Hmmm... oder gleicht sich das aus? :gruebel: 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. |
AW: Effizienz des Speichermanagers
Zitat:
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:
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. |
AW: Effizienz des Speichermanagers
Kurze Zwischenfrage: Müssen die Elemente eigentlich sortiert sein? Braucht man doch gar nicht so häufig.
|
AW: Effizienz des Speichermanagers
Zitat:
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. |
AW: Effizienz des Speichermanagers
Zitat:
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:
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... |
AW: Effizienz des Speichermanagers
Zitat:
Zitat:
Für einen umfangreichen Test muss natürlich beides getestet werden, das ist klar. |
AW: Effizienz des Speichermanagers
Zitat:
Zitat:
Schnellste sortierte Liste (bezüglich Insert/Update/Delete/Locate/)? Interessante Aufgabenstellung. |
AW: Effizienz des Speichermanagers
Liste der Anhänge anzeigen (Anzahl: 1)
So, ich habe jetzt noch mal einen saubereren Test in einem neuen Projekt geschrieben.
Delphi-Quellcode:
Einige Beobachtungen:
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
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. |
AW: Effizienz des Speichermanagers
Ich würde noch vergleichen, wie sich die Strukturen bei kleineren Datenmengen verhalten. Hier macht sich der generelle Overhead stärker bemerkbar. Bei sehr kleinen Listen ist ein einfaches sortiertes Array oft schneller als ein Baum, weil eigentlich kein Overhead vorhanden ist.
Man muss wirklich aufpassen ob und wann man diese 'Ungetüme' (300+ Zeilen für eine 'einfache Liste' ist schon happig) verwenden sollte und wann nicht. Alzaimar hat ja hier einen ganz netten Vergleich geschrieben, der das Verhalten bei kleineren Datenmengen analysiert, da kommt sogar der AVL-Baum und die Skplist vor. Allerdings ist dort die Skiplist viel schneller als der AVL-Baum. Vielleicht, weil es auch viel weniger Daten sind(?) |
AW: Effizienz des Speichermanagers
Zitat:
Ich habe mal -O1 und -O3 getestet und dazu das ganze auch mal mit Delphi7 mit FastMM ausprobiert: FPC 2.7.1 -O1 AVL Tree AL (1000000) I:203 L:109 R:94 ms DL (1000000) I:172 L:94 R:109 ms RD (1000000) I:577 L:452 ms Remove half: 344 ms Reinsert half: 374 ms Skiplist AL (1000000) I:265 L:188 R:124 ms DL (1000000) I:125 L:203 R:250 ms RD (1000000) I:1216 L:1389 ms Remove half: 671 ms Reinsert half: 733 ms RBMap (ohne Pooling) AL (1000000) I:312 L:171 R:125 ms DL (1000000) I:312 L:172 R:140 ms RD (1000000) I:842 L:640 ms Remove half: 406 ms Reinsert half: 452 ms RBMultiMap (Pooled) AL (1000000) I:203 L:109 R:62 ms DL (1000000) I:203 L:109 R:78 ms RD (1000000) I:593 L:515 ms Remove half: 312 ms Reinsert half: 374 ms FPC 2.7.1 -O3 AVL Tree AL (1000000)I: 203 L: 93 R: 110 DL (1000000)I: 187 L: 93 R: 110 RD (1000000)I: 592 L: 468 RH: 328 RIH: 406 Skiplist AL (1000000)I: 249 L: 94 R: 93 DL (1000000)I: 125 L: 109 R: 172 RD (1000000)I: 1357 L: 1326 RH: 655 RIH: 749 RBMap AL (1000000)I: 218 L: 125 R: 109 DL (1000000)I: 219 L: 125 R: 109 RD (1000000)I: 764 L: 609 RH: 390 RIH: 421 RBMultiMap (Pooled) AL (1000000)I: 109 L: 62 R: 47 DL (1000000)I: 125 L: 62 R: 47 RD (1000000)I: 562 L: 452 RH: 297 RIH: 327 Delphi 7 - FastMM AVL Tree AL (1000000)I: 125 L: 93 R: 94 DL (1000000)I: 140 L: 94 R: 78 RD (1000000)I: 515 L: 468 RH: 312 RIH: 359 Skiplist AL (1000000)I: 218 L: 203 R: 62 DL (1000000)I: 78 L: 188 R: 234 RD (1000000)I: 1154 L: 1373 RH: 639 RIH: 687 RBMap AL (1000000)I: 141 L: 46 R: 47 DL (1000000)I: 125 L: 62 R: 47 RD (1000000)I: 515 L: 437 RH: 296 RIH: 312 RBMultiMap (Pooled) AL (1000000)I: 94 L: 62 R: 31 DL (1000000)I: 94 L: 62 R: 31 RD (1000000)I: 515 L: 437 RH: 281 RIH: 296 Fazit: - Für Inserts ist die Skiplist Descending Linear am schnellsten, allerdings leidet der Lookup deutlich darunter - An den AVL-Tree komm ich unter FPC ohne Node-Pooling kaum heran. Unter Delphi kann FastMM die Lücke recht gut ausbügeln - Gepooltes RedBlack und AVL-Tree liegen recht eng beieinander. Vom Algorithmus her sind beide in der Praxis wohl ziemlich gleich. Den Unterschied machen wohl nur ein paar Tricks in der Implementierung aus - Beim schnellsten Container liegen FPC und Delphi von der Geschwindigkeit in derselben Region. Der Speichermanager unter Delphi hilft eingen weniger optimierten Containern deutlich - Wegen der Messtoleranz sind 1000000 Nodes fast schon zu wenig... |
Alle Zeitangaben in WEZ +1. Es ist jetzt 23:31 Uhr. |
Powered by vBulletin® Copyright ©2000 - 2024, Jelsoft Enterprises Ltd.
LinkBacks Enabled by vBSEO © 2011, Crawlability, Inc.
Delphi-PRAXiS (c) 2002 - 2023 by Daniel R. Wolf, 2024 by Thomas Breitkreuz