robin hood hashing Download - robin hood hashing Source Code Download

robin hood hashing

C/C++

3.11.5

Unduh

➵ robin_hood peta & set yang tidak dipesan

Catatan: Sayangnya saya tidak punya waktu untuk melanjutkan pengembangan untuk hashmap ini. Saya memiliki penerus yang layak, silakan kunjungi: ankerl::unordered_dense::{map, set}

Saya telah menghabiskan banyak waktu mengembangkan dan meningkatkannya robin_hood , dan itu bekerja cukup baik untuk sebagian besar kasus penggunaan. Saya tidak akan melakukan pembaruan lagi untuk kode ini, kecuali mereka adalah PRS untuk perbaikan bug kritis.

robin_hood::unordered_map dan robin_hood::unordered_set adalah penggantian platform independen untuk std::unordered_map / std::unordered_set yang lebih cepat dan lebih efisien memori untuk kasus penggunaan dunia nyata.

Instalasi & Penggunaan

Inklusi langsung

Tambahkan robin_hood.h ke proyek C ++ Anda.
Gunakan robin_hood::unordered_map bukannya std::unordered_map
Gunakan robin_hood::unordered_set bukan std::unordered_set

Conan, Manajer Paket C/C ++

Siapkan CMakeLists.txt Anda (lihat Dokumentasi Conan tentang Cara Menggunakan MsBuild, Meson dan Lainnya) seperti ini:

 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)

Buat conanfile.txt di Dir Sumber Anda (Jangan lupa untuk memperbarui versi)
```
 [requires]
robin-hood-hashing/3.11.5

[generators]
cmake
```
Instal dan jalankan Conan, lalu bangun proyek Anda seperti biasa:
```
pip install conan
mkdir build
cd build
conan install ../ --build=missing
cmake ../
cmake --build .
```
Paket robin-hood-hashing di Conan terus diperbarui oleh kontributor Conan. Jika versi sudah ketinggalan zaman, silakan buat masalah atau tarik permintaan pada repositori conan-center-index .

Tolok ukur

Silakan lihat tolok ukur luas di tolok ukur hashmaps. Singkatnya: robin_hood selalu menjadi peta tercepat dan menggunakan memori yang jauh lebih sedikit daripada std::unordered_map .

Pilihan desain

Dua tata letak memori . Data disimpan dalam array datar, atau dengan tipu daya node. Akses untuk unordered_flat_map sangat cepat karena tidak ada tipuan, tetapi referensi ke elemen tidak stabil. Ini juga menyebabkan lonjakan alokasi ketika peta mengubah ukuran, dan akan membutuhkan banyak memori untuk objek besar. Peta berbasis node memiliki referensi & pointer yang stabil (bukan iterator! Mirip dengan std :: unordered_map) dan menggunakan const Key pada pasangan. Ini sedikit lebih lambat karena tipuan. Pilihannya adalah milik Anda; Anda dapat menggunakan robin_hood::unordered_flat_map atau robin_hood::unordered_node_map secara langsung. Jika Anda menggunakan robin_hood::unordered_map ia mencoba memilih tata letak yang tampaknya sesuai untuk data Anda.
Alokasi khusus . Representasi berbasis node memiliki alokasi curah khusus yang mencoba membuat beberapa alokasi memori. Semua memori yang dialokasikan digunakan kembali, jadi tidak akan ada lonjakan alokasi apa pun. Ini juga sangat cepat.
Hash yang dioptimalkan . robin_hood::hash memiliki implementasi khusus untuk tipe integer dan untuk std::string yang sangat cepat dan jatuh kembali ke std::hash untuk yang lainnya.
Tergantung pada hashing yang baik . Untuk hash yang benar -benar buruk, kinerja tidak hanya akan menurun seperti di std::unordered_map , peta hanya akan gagal dengan std::overflow_error . Dalam praktiknya, saat menggunakan robin_hood::hash , saya belum pernah melihat ini terjadi.