robin hood hashingダウンロード - robin hood hashingソースコードダウンロード

robin hood hashing

C/C++

3.11.5

ダウンロード

robin_hood順序付けられていないマップ＆セット

注：残念ながら、このハッシュマップの開発を継続する時間はありません。私は価値のある後継者を持っていますが、 ankerl::unordered_dense::{map, set}にアクセスしてください。

robin_hood開発と改善に多くの時間を費やしてきましたが、ほとんどのユースケースで非常にうまく機能しています。重要なバグ修正のPRSでない限り、このコードの更新はこれ以上ありません。

robin_hood::unordered_map and robin_hood::unordered_set std::unordered_map / std::unordered_setのプラットフォーム独立した代替品です。

インストールと使用

直接包含

robin_hood.h C ++プロジェクトに追加します。
std::unordered_mapの代わりにrobin_hood::unordered_map unordered_mapを使用します
std::unordered_setの代わりにrobin_hood::unordered_set unordered_setを使用します

C/C ++パッケージマネージャーのコナン

このように、 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
```
コナンをインストールして実行してから、いつものようにプロジェクトを構築してください。
```
pip install conan
mkdir build
cd build
conan install ../ --build=missing
cmake ../
cmake --build .
```
コナンのrobin-hood-hashingパッケージは、コナンの寄稿者によって最新の状態に保たれています。バージョンが古くなっている場合は、 conan-center-indexリポジトリに問題を作成するか、リクエストをプルしてください。

ベンチマーク

Hashmapsベンチマークの広範なベンチマークをご覧ください。要するに、 robin_hood常に最速のマップの1つであり、 std::unordered_mapよりもはるかに少ないメモリを使用します。

デザインの選択

2つのメモリレイアウト。データは、フラットアレイに保存されるか、ノード間接で保存されます。 unordered_flat_mapへのアクセスは、間接がないため非常に高速ですが、要素への参照は安定していません。また、マップが変更されたときに割り当てのスパイクを引き起こし、大きなオブジェクトに十分なメモリが必要になります。ノードベースのマップには、安定した参照とポインター（iteratorsではありません！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を使用するとき、私はこれが起こっているのを見たことがありません。