robin hood hashing 다운로드 -Robin robin hood hashing 소스 코드 다운로드

robin hood hashing

C/C++

3.11.5

다운로드

Robin_hood unordered 맵 및 세트

참고 : 불행히도이 해시 맵을 위해 개발을 계속할 시간이 없습니다. 그래도 가치있는 후계자가 있습니다. ankerl::unordered_dense::{map, set} 로 가십시오.

나는 robin_hood 를 개발하고 개선하는 데 많은 시간을 보냈으며 대부분의 사용 사례에 매우 효과적입니다. 중요한 버그 수정을위한 PR이 아니라면이 코드를 더 이상 업데이트하지 않을 것입니다.

robin_hood::unordered_map 및 robin_hood::unordered_set 실제 사용 사례에 대해 더 빠르고 메모리가 효율적 인 std::unordered_map / std::unordered_set 위한 플랫폼 독립적 인 대체입니다.

설치 및 사용

직접 포함

C ++ 프로젝트에 robin_hood.h 추가하십시오.
std::unordered_map robin_hood::unordered_map :: unordered_map을 사용하십시오
std::unordered_set robin_hood::unordered_set :: unordered_set을 사용하십시오

C/C ++ 패키지 관리자 인 Conan

다음과 같이 CMakeLists.txt 설정하십시오 (MSBuild, Meson 및 기타 사용 방법에 대한 Conan 문서 참조).

 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 .
```
Conan의 robin-hood-hashing 패키지는 Conan 기고자들에 의해 최신 상태로 유지됩니다. 버전이 오래된 경우 conan-center-index 저장소에서 문제를 만들거나 요청을 가져 오십시오.

벤치 마크

Hashmaps Benchmarks의 광범위한 벤치 마크를 참조하십시오. 요컨대 : 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 사용할 때, 나는 이런 일이 일어나는 것을 본 적이 없다.