ดาวน์โหลด robin hood hashing - robin hood hashing Source Source Download

robin hood hashing

ซี/ซี++

3.11.5

ดาวน์โหลด

➵ ROBIN_HOW MAP & SET ที่ไม่ได้เรียงลำดับ

หมายเหตุ: น่าเสียดายที่ฉันไม่มีเวลาพัฒนาต่อไปสำหรับ 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

Conan, C/C ++ Manager

ตั้งค่า CMakeLists.txt ของคุณ (ดูเอกสารเกี่ยวกับวิธีการใช้ 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 ในแหล่งกำเนิดของคุณ (อย่าลืมอัปเดตเวอร์ชัน)
```
 [requires]
robin-hood-hashing/3.11.5

[generators]
cmake
```
ติดตั้งและเรียกใช้ Conan จากนั้นสร้างโครงการของคุณเช่นเคย:
```
pip install conan
mkdir build
cd build
conan install ../ --build=missing
cmake ../
cmake --build .
```
แพ็คเกจ robin-hood-hashing ในโคนันได้รับการปรับปรุงให้ทันสมัยโดย Conan ผู้มีส่วนร่วม หากเวอร์ชันล้าสมัยโปรดสร้างปัญหาหรือดึงคำขอบนที่เก็บ 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 ฉันไม่เคยเห็นเหตุการณ์นี้มาก่อน