تنزيل robin hood hashing - تنزيل رمز مصدر robin hood hashing

robin hood hashing

ج/ج++

3.11.5

تنزيل

➵ Robin_hood خريطة غير مرتبة ومجموعة

ملاحظة: لسوء الحظ ، ليس لدي وقت لمواصلة التطوير لهذا HashMap. لدي خليفة جدير ، يرجى التوجه إلى: ankerl::unordered_dense::{map, set}

لقد قضيت الكثير من الوقت في تطوير وتحسينه robin_hood ، وهو يعمل بشكل جيد لمعظم حالات الاستخدام. لن أقوم بأي تحديثات لهذا الرمز بعد الآن ، إلا إذا كانت PRS لإصلاحات الأخطاء الحرجة.

robin_hood::unordered_map و robin_hood::unordered_set هو استبدال مستقل منصة لـ std::unordered_map / std::unordered_set وهو أسرع وأكثر فعالية في الذاكرة لحالات الاستخدام في العالم الحقيقي.

التثبيت والاستخدام

التضمين المباشر

أضف robin_hood.h إلى مشروع C ++ الخاص بك.
استخدم robin_hood::unordered_map بدلاً من std::unordered_map
استخدم robin_hood::unordered_set بدلاً من std::unordered_set

كونان ، مدير حزمة C/C ++

قم بإعداد CMakeLists.txt (انظر وثائق Conan حول كيفية استخدام MSBuild و Meson وغيرها) مثل هذا:

 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)

إنشاء conanfile.txt في مصدرك dir (لا تنس تحديث الإصدار)
```
 [requires]
robin-hood-hashing/3.11.5

[generators]
cmake
```
قم بتثبيت وتشغيل كونان ، ثم قم ببناء مشروعك كما هو الحال دائمًا:
```
pip install conan
mkdir build
cd build
conan install ../ --build=missing
cmake ../
cmake --build .
```
يتم الحفاظ على حزمة robin-hood-hashing في كونان محدثة من قبل المساهمين في كونان. إذا كان الإصدار قديمًا ، فيرجى إنشاء مشكلة أو سحب طلب على مستودع conan-center-index .

المعايير

يرجى الاطلاع على معايير واسعة في معايير HashMaps. باختصار: robin_hood هو دائمًا من بين أسرع الخرائط ويستخدم ذاكرة أقل بكثير من std::unordered_map .

خيارات التصميم

تخطيطين للذاكرة . يتم تخزين البيانات إما في صفيف مسطح ، أو مع عدم التوجيه العقدة. إن الوصول إلى unordered_flat_map سريع للغاية بسبب عدم وجود توجيه ، ولكن الإشارات إلى العناصر ليست مستقرة. كما أنه يسبب تخصيص طفرات عند تغيير حجم الخريطة ، وستحتاج إلى الكثير من الذاكرة للكائنات الكبيرة. تحتوي الخريطة المستندة إلى العقدة على مراجع ومؤشرات مستقرة (وليس متكررين! على غرار std :: unordered_map) وتستخدم const Key في الزوج. إنه أبطأ قليلاً بسبب عدم التوجيه. الاختيار لك. يمكنك إما استخدام robin_hood::unordered_flat_map أو robin_hood::unordered_node_map مباشرة. إذا كنت تستخدم robin_hood::unordered_map فإنه يحاول اختيار التصميم الذي يبدو مناسبًا لبياناتك.
مخصص مخصص . يحتوي التمثيل المستند إلى العقدة على مخصص بالجملة مخصصة يحاول تقديم عدد قليل من تخصيصات الذاكرة. يتم إعادة استخدام جميع الذاكرة المخصصة ، لذلك لن يكون هناك أي طفرات تخصيص. إنه سريع جدًا أيضًا.
تجزئة الأمثل . robin_hood::hash لديه تطبيقات مخصصة لأنواع عدد صحيح وللطاقة std::string التي هي سريعة للغاية وتتراجع إلى std::hash لكل شيء آخر.
يعتمد على التجزئة الجيدة . بالنسبة إلى التجزئة السيئة حقًا ، لن يتحلل الأداء كما هو الحال في std::unordered_map ، ستفشل الخريطة ببساطة مع std::overflow_error . في الممارسة العملية ، عند استخدام قياسي robin_hood::hash ، لم أر هذا يحدث أبدًا.