C/C++ Benchmark - Effizientes Suchen
Verfasst: 07.09.2022, 11:36
Ich habe ja vor Ewigkeiten etliche Tests zu verschiedenen Suchmethoden gemacht.
Damit die Daten nicht nur auf der Platte vergammeln, möchte ich sie hier vorstellen,
vielleicht helfen sie, die graue Theorie abzurunden...
Und wenn man ein zeitkritisches Suchproblem hat, dann geben die Zahlen einen Anhalt,
welche Methoden geeignet sind. Achtung: Die Diagramme sind doppelt logarithmisch.
--- Zufallssuche mit Integer Key ---
--- Zufallssuche mit strcmp ---
--- Zufallssuche mit Integer Key, sehr große Felder ---
---
Die zu suchenden Elemente sind 32 Byte Strukturen in einem grossen Feld.
Der Suchindex ist zufällig und entweder eine Integerzahl, oder ein String (strmcp).
Betriebssystem ist Win10, compiler ist VS2019, das ganze läuft auf einem Dell Laptop mit einem i7-8850H
(L1 Cache 32kByte, L2=256k, L3=1.5MByte).
Direkter-Speicherzugriff:
In manchen Fällen reden wir über < 300 Pikosekunden, moderne HW ist sauschnell!
Robin-Hood Hash Map:
Hash Suche, die den Robin-Hood Algo verwendet.
Als Hash Funktion wird die Intel HW CRC32 verwendet, die in meine Tests meist sehr gut war.
https://codecapsule.com/2013/11/11/robin-hood-hashing/
AVL Tree:
Adelson Velskii Landis (AVL) binärer Suchbaum.
Standard Methode seit 1962 aus Russland.
Unglaublich viele komplizierte Spezialfälle.
Ich würde es nicht nochmal programmieren wollen.
https://en.wikipedia.org/wiki/AVL_tree
std::map:
Wahrscheinlich ein Red-Black binärer Baum.
std::unordered_map:
C++ hash table. Keine Ahnung, was da genau verwendet wird.
Lineare Suche:
Eine einfache for Schleife.
Laut https://dirtyhandscoding.github.io/post ... earch.html
soll die bis zu 256 Einträgen ja schneller sein.
Ich habe das mit dem Code der Seite nachvollzogen, aber nicht mit meinen komplexeren Tests hier.
Gruss,
Udo
Damit die Daten nicht nur auf der Platte vergammeln, möchte ich sie hier vorstellen,
vielleicht helfen sie, die graue Theorie abzurunden...
Und wenn man ein zeitkritisches Suchproblem hat, dann geben die Zahlen einen Anhalt,
welche Methoden geeignet sind. Achtung: Die Diagramme sind doppelt logarithmisch.
--- Zufallssuche mit Integer Key ---
Die zu suchenden Elemente sind 32 Byte Strukturen in einem grossen Feld.
Der Suchindex ist zufällig und entweder eine Integerzahl, oder ein String (strmcp).
Betriebssystem ist Win10, compiler ist VS2019, das ganze läuft auf einem Dell Laptop mit einem i7-8850H
(L1 Cache 32kByte, L2=256k, L3=1.5MByte).
Direkter-Speicherzugriff:
In manchen Fällen reden wir über < 300 Pikosekunden, moderne HW ist sauschnell!
Robin-Hood Hash Map:
Hash Suche, die den Robin-Hood Algo verwendet.
Als Hash Funktion wird die Intel HW CRC32 verwendet, die in meine Tests meist sehr gut war.
https://codecapsule.com/2013/11/11/robin-hood-hashing/
AVL Tree:
Adelson Velskii Landis (AVL) binärer Suchbaum.
Standard Methode seit 1962 aus Russland.
Unglaublich viele komplizierte Spezialfälle.
Ich würde es nicht nochmal programmieren wollen.
https://en.wikipedia.org/wiki/AVL_tree
std::map:
Wahrscheinlich ein Red-Black binärer Baum.
std::unordered_map:
C++ hash table. Keine Ahnung, was da genau verwendet wird.
Lineare Suche:
Eine einfache for Schleife.
Laut https://dirtyhandscoding.github.io/post ... earch.html
soll die bis zu 256 Einträgen ja schneller sein.
Ich habe das mit dem Code der Seite nachvollzogen, aber nicht mit meinen komplexeren Tests hier.
Gruss,
Udo