robin hood hashing Download - robin hood hashing Source Code Download

robin hood hashing

C/C++

3.11.5

Herunterladen

➵ Robin_Hood Unordnete Karte & Set

Hinweis: Leider habe ich keine Zeit, um die Entwicklung für diese Hashmap fortzusetzen. Ich habe jedoch einen würdigen Nachfolger, bitte gehen Sie zu: ankerl::unordered_dense::{map, set}

Ich habe viel Zeit damit verbracht, es zu entwickeln und zu verbessern, robin_hood , und es funktioniert für die meisten Anwendungsfälle recht gut. Ich werde diesen Code nicht mehr aktualisieren, es sei denn, es handelt sich um PRS für kritische Fehlerbehebungen.

robin_hood::unordered_map und robin_hood::unordered_set ist ein unabhängiger Plattform-Ersatz für std::unordered_map / std::unordered_set das für reale Anwendungsfälle sowohl schneller als auch speicherer effizienter ist.

Installation & Nutzung

Direkte Aufnahme

Fügen Sie robin_hood.h zu Ihrem C ++ - Projekt hinzu.
Verwenden Sie robin_hood::unordered_map anstelle von std::unordered_map
Verwenden Sie robin_hood::unordered_set anstelle von std::unordered_set

Conan, der C/C ++ Paketmanager

Richten Sie Ihre CMakeLists.txt ein (siehe Conan -Dokumentation zur Verwendung von MSBuild, Meson und anderen) wie folgt:

 project (myproject CXX)

add_executable ( ${PROJECT_NAME} main.cpp)

include ( ${CMAKE_BINARY_DIR} /conanbuildinfo.cmake) # Include Conan-generated file
conan_basic_setup(TARGETS) # Introduce Conan-generated targets

target_link_libraries ( ${PROJECT_NAME} CONAN_PKG::robin-hood-hashing)

Erstellen Sie conanfile.txt in Ihrer Quell -Dir. (Vergessen Sie nicht, die Version zu aktualisieren).
```
 [requires]
robin-hood-hashing/3.11.5

[generators]
cmake
```
Installieren und führen Sie Conan aus und erstellen Sie dann Ihr Projekt wie immer:
```
pip install conan
mkdir build
cd build
conan install ../ --build=missing
cmake ../
cmake --build .
```
Das robin-hood-hashing Paket in Conan wird von Conan-Mitwirkenden auf dem Laufenden gehalten. Wenn die Version veraltet ist, erstellen Sie bitte eine Ausgabe- oder Zuganfrage im conan-center-index Repository.

Benchmarks

Bitte beachten Sie umfangreiche Benchmarks bei Hashmaps Benchmarks. Kurz gesagt: robin_hood gehört immer zu den schnellsten Karten und verwendet weit weniger Speicher als std::unordered_map .

Designoptionen

Zwei Speicherlayouts . Die Daten werden entweder in einem flachen Array oder mit Knotenindirektion gespeichert. Der Zugriff auf unordered_flat_map ist aufgrund der Nicht -Indirektion extrem schnell, aber Verweise auf Elemente sind nicht stabil. Es führt auch zu Zuordnungsspitzen, wenn die Karte ändert, und benötigt viel Speicher für große Objekte. Knotenbasierte Karte verfügt über stabile Referenzen und Hinweise (nicht Iteratoren! Ähnlich wie std :: uncondeded_map) und verwendet const Key im Paar. Es ist aufgrund der Indirektion etwas langsamer. Die Wahl gehört dir; Sie können entweder robin_hood::unordered_flat_map oder robin_hood::unordered_node_map verwenden. Wenn Sie robin_hood::unordered_map verwenden, versucht es, das Layout auszuwählen, das für Ihre Daten geeignet zu sein scheint.
Benutzerdefinierter Allocator . Die notenbasierte Darstellung hat einen benutzerdefinierten Bulk -Allocator, der versucht, nur wenige Speicherzuweisungen vorzunehmen. Alle zugewiesenen Speicher werden wiederverwendet, sodass es keine Zuteilungsspitzen gibt. Es ist auch sehr schnell.
Optimierter Hash . robin_hood::hash hat benutzerdefinierte Implementierungen für Ganzzahltypen und für std::string , die sehr schnell sind und für alles andere auf std::hash zurückfallen.
Kommt auf gutes Hashing an . Für einen wirklich schlechten Hash wird sich die Aufführung nicht nur wie in std::unordered_map verschlechtern, die Karte wird einfach mit einem std::overflow_error versagen. In der Praxis habe ich bei der Verwendung des Standard robin_hood::hash dies noch nie gesehen.