hat trie
v0.6.0
「HAT-trie: 文字列用のキャッシュを意識したトライベースのデータ構造」に基づいたトライの実装。 (Askitis Nikolas および Sinha Ranjan、2007) 論文。今のところ、純粋な HAT-trie のみが実装されていますが、ハイブリッド バージョンは後で登場する可能性があります。 HAT-trie データ構造の詳細については、ここを参照してください。
このライブラリは、共通のプレフィックスを圧縮することで文字列のセットまたはマップを保存する効率的かつコンパクトな方法を提供します。プレフィックスに一致するキーを検索することもできます。ただし、構造体のデフォルトのパラメーターは正確な検索の最適化を目的としているため、プレフィックス検索を頻繁に行う場合は、 burst_thresholdメソッドを通じてバーストしきい値を下げることをお勧めします。
これは、多数の文字列を格納するのに適した構造です。
配列ハッシュ部分には、配列ハッシュ プロジェクトが使用され、リポジトリに含まれます。
このライブラリは、 tsl::htrie_mapとtsl::htrie_set 2 つのクラスを提供します。
tsl::hat_trieターゲットを使用することもできます。equal_prefix_rangeによるプレフィックス検索 (オートコンプリートなどに便利) と、 erase_prefixによるプレフィックス消去をサポートします。longest_prefixによる最長一致プレフィックス検索をサポートします。serialize/deserializeメソッドを参照してください)。max_load_factorメソッドを通じて変更できます。最大負荷率が低いほど速度が向上し、最大負荷率が高いほどメモリ使用量が減少します。デフォルト値は 8.0 に設定されています。burst_thresholdメソッドによる結果の反復を高速化するために、値を 1024 以下に減らすことをお勧めします。KeySizeTテンプレート パラメーターを通じて上げることができます。スレッドセーフと例外の保証は STL コンテナーと同様です。
構造体で使用されるデフォルトのハッシュ関数は、 std::string_viewの存在によって異なります。利用可能な場合はstd::hash<std::string_view>が使用され、それ以外の場合は単純な FNV-1a ハッシュ関数が依存関係を回避するために使用されます。
C++17 以降を使用できない場合は、パフォーマンスを向上させるために、ハッシュ関数を CityHash、MurmurHash、FarmHash などに置き換えることをお勧めします。私たちが行ったテストでは、CityHash64 は FNV-1a と比較して読み取りが最大 20% 向上しました。
# include < city.h >
struct str_hash {
std:: size_t operator ()( const char * key, std:: size_t key_size) const {
return CityHash64 (key, key_size);
}
};
tsl::htrie_map< char , int , str_hash> map; std::hash<std::string>構造体にstd::stringオブジェクトが格納されていないため、効率的に使用できません。ハッシュが必要になるたびに、一時的なstd::string作成する必要があります。
ベンチマークは、Wikipedia アーカイブのメイン名前空間からすべてのタイトルをデータ構造に挿入し、挿入後に使用されているメモリ領域 (潜在的なメモリ断片化を含む) を確認し、データ構造内ですべてのタイトルを再度検索することで構成されます。挿入プロセス中のピークのメモリ使用量も time(1) で測定されます。
各タイトルは int (32 ビット) に関連付けられています。すべてのハッシュ ベースの構造は、ハッシュ関数として CityHash64 を使用します。 reserve とマークされたテストでは、再ハッシュを避けるために、事前にreserve関数が呼び出されます。
tsl::hopscotch_map 、 std::unordered_map 、 google::dense_hash_map 、およびspp::sparse_hash_map 、 std::string 。他の構造では、1 バイト + ポインター用の 8 バイトで 1 文字のキーを格納できる場合があります (x64 の場合)。
このベンチマークは GCC 6.3 でコンパイルされ、Intel i5-5200u と 8Go の RAM を搭載した Debian Stretch x64 上で実行されました。 20 ランのベストが取られました。
ベンチマークのコードは Gist にあります。
enwiki-20170320-all-titles-in-ns0.gzデータセットはアルファベット順にソートされています。このベンチマークでは、偏った並べ替えられたデータセットを避けるために、最初に shuf(1) によってデータセットをシャッフルします。
| 図書館 | データ構造 | ピークメモリ (MiB) | メモリ (MiB) | 挿入 (ns/キー) | 読み取り (ns/キー) |
|---|---|---|---|---|---|
| tsl::htrie_map | ハットトライ | 405.22 | 402.25 | 643.10 | 250.87 |
| tsl::htrie_map max_load_factor=4 | ハットトライ | 471.85 | 468.50 | 638.66 | 212.90 |
| tsl::htrie_map max_load_factor=2 | ハットトライ | 569.76 | 566.52 | 630.61 | 201.10 |
| tsl::htrie_map 最大負荷係数=1 | ハットトライ | 713.44 | 709.81 | 645.76 | 190.87 |
| 杉::だ | 二重配列トライ | 1269.68 | 1254.41 | 1102.93 | 557.20 |
| 杉::da ORDERED=false | 二重配列トライ | 1269.80 | 1254.41 | 1089.78 | 570.13 |
| 杉::だ | 二重配列の縮小トライ | 1183.07 | 1167.79 | 1076.68 | 645.79 |
| 杉::da ORDERED=false | 二重配列の縮小トライ | 1183.14 | 1167.85 | 1065.43 | 641.98 |
| 杉::だ | 二重配列プレフィックストライ | 498.69 | 496.54 | 1096.90 | 628.01 |
| 杉::da ORDERED=false | 二重配列プレフィックストライ | 498.65 | 496.60 | 1048.40 | 628.94 |
| ハットトライ1 (C) | ハットトライ | 504.07 | 501.50 | 917.49 | 261.00 |
| qpトライ(C) | QPトライ | 941.23 | 938.17 | 1349.25 | 1281.46 |
| クリティカルビットトライ(C) | クリティカルビットトライ | 1074.96 | 1071.98 | 2930.42 | 2869.74 |
| ジュディSL (C) | ジュディ・アレイ | 631.09 | 628.37 | 884.29 | 803.58 |
| ジュディHS (C) | ジュディ・アレイ | 723.44 | 719.47 | 476.79 | 417.15 |
| tsl::array_map | 配列ハッシュテーブル | 823.54 | 678.73 | 603.94 | 138.24 |
| tsl::array_map 予備あり | 配列ハッシュテーブル | 564.26 | 555.91 | 249.52 | 128.28 |
| tsl::石けり遊び_マップ | ハッシュテーブル | 1325.83 | 1077.99 | 368.26 | 119.49 |
| tsl::石けり遊び_マップ 予備あり | ハッシュテーブル | 1080.51 | 1077.98 | 240.58 | 119.91 |
| google::dense_hash_map | ハッシュテーブル | 2319.40 | 1677.11 | 466.60 | 138.87 |
| google::dense_hash_map 予備あり | ハッシュテーブル | 1592.51 | 1589.99 | 259.56 | 120.40 |
| spp::sparse_hash_map | スパースハッシュテーブル | 918.67 | 917.10 | 769.00 | 175.59 |
| spp::sparse_hash_map 予備あり | スパースハッシュテーブル | 913.35 | 910.65 | 427.22 | 159.08 |
| std::unowned_map | ハッシュテーブル | 1249.05 | 1246.60 | 590.88 | 173.58 |
| std::unowned_map 予備あり | ハッシュテーブル | 1212.23 | 1209.71 | 350.33 | 178.70 |
キーはアルファベット順に挿入され、読み取られます。
| 図書館 | データ構造 | ピークメモリ (MiB) | メモリ (MiB) | 挿入 (ns/キー) | 読み取り (ns/キー) |
|---|---|---|---|---|---|
| tsl::htrie_map | ハットトライ | 396.10 | 393.22 | 255.76 | 68.08 |
| tsl::htrie_map max_load_factor=4 | ハットトライ | 465.02 | 461.80 | 248.88 | 59.23 |
| tsl::htrie_map max_load_factor=2 | ハットトライ | 543.99 | 541.21 | 230.13 | 53.50 |
| tsl::htrie_map 最大負荷係数=1 | ハットトライ | 692.29 | 689.70 | 243.84 | 49.22 |
| 杉::だ | 二重配列トライ | 1269.58 | 1254.41 | 278.51 | 54.72 |
| 杉::da ORDERED=false | 二重配列トライ | 1269.66 | 1254.41 | 264.43 | 56.02 |
| 杉::だ | 二重配列の縮小トライ | 1183.01 | 1167.78 | 254.60 | 69.18 |
| 杉::da ORDERED=false | 二重配列の縮小トライ | 1183.03 | 1167.78 | 241.45 | 69.67 |
| 杉::だ | 二重配列プレフィックストライ | 621.59 | 619.38 | 246.88 | 57.83 |
| 杉::da ORDERED=false | 二重配列プレフィックストライ | 621.59 | 619.38 | 187.98 | 58.56 |
| ハットトライ2 (C) | ハットトライ | 521.25 | 518.52 | 503.01 | 86.40 |
| qpトライ(C) | QPトライ | 940.65 | 937.66 | 392.86 | 190.19 |
| クリティカルビットトライ(C) | クリティカルビットトライ | 1074.87 | 1071.98 | 430.04 | 347.60 |
| ジュディSL (C) | ジュディ・アレイ | 616.95 | 614.27 | 279.07 | 114.47 |
| ジュディHS (C) | ジュディ・アレイ | 722.29 | 719.47 | 439.66 | 372.25 |
| tsl::array_map | 配列ハッシュテーブル | 826.98 | 682.99 | 612.31 | 139.16 |
| tsl::array_map 予備あり | 配列ハッシュテーブル | 565.37 | 555.35 | 246.55 | 126.32 |
| tsl::石けり遊び_マップ | ハッシュテーブル | 1331.87 | 1078.02 | 375.19 | 118.08 |
| tsl::石けり遊び_マップ 予備あり | ハッシュテーブル | 1080.51 | 1077.97 | 238.93 | 117.20 |
| google::dense_hash_map | ハッシュテーブル | 2325.27 | 1683.07 | 483.95 | 137.09 |
| google::dense_hash_map 予備あり | ハッシュテーブル | 1592.54 | 1589.99 | 257.22 | 113.71 |
| spp::sparse_hash_map | スパースハッシュテーブル | 920.96 | 918.70 | 772.03 | 176.64 |
| spp::sparse_hash_map 予備あり | スパースハッシュテーブル | 914.84 | 912.47 | 422.85 | 158.73 |
| std::unowned_map | ハッシュテーブル | 1249.09 | 1246.65 | 594.85 | 173.54 |
| std::unowned_map 予備あり | ハッシュテーブル | 1212.21 | 1209.71 | 347.40 | 176.49 |
ベンチマークは、Askitis 博士の「Distinct Strings」データセットからのすべての単語をデータ構造に挿入し、使用されているメモリ領域を確認し、「Skew String Set 1」データセットからすべての単語を検索することで構成されます (文字列はデータ構造内に複数回存在します。このデータセットの文字列の平均キー長と中央値キーの長さは非常に短いことに注意してください (これは、上で使用した Wikipedia データセットと比較すると現実的な使用例ではない可能性があります)。杉のホームページにあるものと似ています。
ベンチマーク プロトコルは Wikipedia データセットの場合と同じです。
| 図書館 | データ構造 | ピークメモリ (MiB) | メモリ (MiB) | 挿入 (ns/キー) | 読み取り (ns/キー) |
|---|---|---|---|---|---|
| tsl::htrie_map | ハットトライ | 604.76 | 601.79 | 485.45 | 77.80 |
| tsl::htrie_map max_load_factor=4 | ハットトライ | 768.10 | 764.98 | 491.78 | 75.48 |
| tsl::htrie_map max_load_factor=2 | ハットトライ | 1002.42 | 999.34 | 496.78 | 72.53 |
| tsl::htrie_map 最大負荷係数=1 | ハットトライ | 1344.98 | 1341.97 | 520.66 | 72.45 |
| 杉::だ | 二重配列トライ | 1105.45 | 1100.05 | 682.25 | 71.98 |
| 杉::da ORDERED=false | 二重配列トライ | 1105.47 | 1100.05 | 668.75 | 71.95 |
| 杉::だ | 二重配列の縮小トライ | 941.16 | 926.04 | 684.38 | 79.11 |
| 杉::da ORDERED=false | 二重配列の縮小トライ | 941.16 | 925.98 | 672.14 | 79.02 |
| 杉::だ | 二重配列プレフィックストライ | 714.58 | 712.59 | 831.71 | 75.83 |
| 杉::da ORDERED=false | 二重配列プレフィックストライ | 714.66 | 712.31 | 786.93 | 75.89 |
| ハットトライ3 (C) | ハットトライ | 786.93 | 784.32 | 743.34 | 93.58 |
| qpトライ(C) | QPトライ | 1800.02 | 1797.21 | 987.95 | 428.51 |
| クリティカルビットトライ(C) | クリティカルビットトライ | 2210.52 | 2207.64 | 1986.19 | 1109.88 |
| ジュディSL (C) | ジュディ・アレイ | 1025.59 | 1023.11 | 535.02 | 202.36 |
| ジュディHS (C) | ジュディ・アレイ | 1002.50 | 999.97 | 456.09 | 148.36 |
| tsl::array_map | 配列ハッシュテーブル | 1308.08 | 1031.67 | 545.82 | 46.41 |
| tsl::array_map 予備あり | 配列ハッシュテーブル | 979.44 | 921.363 | 244.19 | 45.74 |
| tsl::石けり遊び_マップ | ハッシュテーブル | 2336.39 | 1611.54 | 288.70 | 47.05 |
| tsl::石けり遊び_マップ 予備あり | ハッシュテーブル | 1614.22 | 1611.64 | 220.67 | 46.39 |
| google::dense_hash_map | ハッシュテーブル | 3913.64 | 2636.31 | 317.66 | 43.62 |
| google::dense_hash_map 予備あり | ハッシュテーブル | 2638.19 | 2635.68 | 227.58 | 43.09 |
| spp::sparse_hash_map | スパースハッシュテーブル | 1419.69 | 1417.61 | 586.26 | 56.00 |
| spp::sparse_hash_map 予備あり | スパースハッシュテーブル | 1424.21 | 1421.69 | 392.76 | 55.73 |
| std::unowned_map | ハッシュテーブル | 2112.66 | 2110.19 | 554.02 | 105.05 |
| std::unowned_map 予備あり | ハッシュテーブル | 2053.95 | 2051.67 | 309.06 | 109.89 |
ライブラリを使用するには、インクルード ディレクトリをインクルード パスに追加するだけです。ヘッダーのみのライブラリです。
CMake を使用する場合は、 target_link_librariesを使用して CMakeLists.txt からエクスポートされたtsl::hat_trieターゲットを使用することもできます。
# Example where the hat-trie project is stored in a third-party directory
add_subdirectory (third-party/hat-trie)
target_link_libraries (your_target PRIVATE tsl::hat_trie) コードは C++11 標準に準拠したコンパイラで動作する必要があり、GCC 4.8.4、Clang 3.5.0、および Visual Studio 2015 でテストされています。
テストを実行するには、Boost Test ライブラリと CMake が必要です。
git clone https://github.com/Tessil/hat-trie.git
cd hat-trie/tests
mkdir build
cd build
cmake ..
cmake --build .
./tsl_hat_trie_testsAPI はここにあります。 std::string_viewが使用可能な場合、API は少し変更されており、ここで見つけることができます。
# include < iostream >
# include < string >
# include < tsl/htrie_map.h >
# include < tsl/htrie_set.h >
int main () {
/*
* Map of strings to int having char as character type.
* There is no support for wchar_t, char16_t or char32_t yet,
* but UTF-8 strings will work fine.
*/
tsl::htrie_map< char , int > map = {{ " one " , 1 }, { " two " , 2 }};
map[ " three " ] = 3 ;
map[ " four " ] = 4 ;
map. insert ( " five " , 5 );
map. insert_ks ( " six_with_extra_chars_we_ignore " , 3 , 6 );
map. erase ( " two " );
/*
* Due to the compression on the common prefixes, the letters of the string
* are not always stored contiguously. When we retrieve the key, we have to
* construct it.
*
* To avoid a heap-allocation at each iteration (when SSO doesn't occur),
* we reuse the key_buffer to construct the key.
*/
std::string key_buffer;
for ( auto it = map. begin (); it != map. end (); ++it) {
it. key (key_buffer);
std::cout << " { " << key_buffer << " , " << it. value () << " } " << std::endl;
}
/*
* If you don't care about the allocation.
*/
for ( auto it = map. begin (); it != map. end (); ++it) {
std::cout << " { " << it. key () << " , " << *it << " } " << std::endl;
}
tsl::htrie_map< char , int > map2 = {{ " apple " , 1 }, { " mango " , 2 }, { " apricot " , 3 },
{ " mandarin " , 4 }, { " melon " , 5 }, { " macadamia " , 6 }};
// Prefix search
auto prefix_range = map2. equal_prefix_range ( " ma " );
// {mandarin, 4} {mango, 2} {macadamia, 6}
for ( auto it = prefix_range. first ; it != prefix_range. second ; ++it) {
std::cout << " { " << it. key () << " , " << *it << " } " << std::endl;
}
// Find longest match prefix.
auto longest_prefix = map2. longest_prefix ( " apple juice " );
if (longest_prefix != map2. end ()) {
// {apple, 1}
std::cout << " { " << longest_prefix. key () << " , "
<< *longest_prefix << " } " << std::endl;
}
// Prefix erase
map2. erase_prefix ( " ma " );
// {apricot, 3} {melon, 5} {apple, 1}
for ( auto it = map2. begin (); it != map2. end (); ++it) {
std::cout << " { " << it. key () << " , " << *it << " } " << std::endl;
}
tsl::htrie_set< char > set = { " one " , " two " , " three " };
set. insert ({ " four " , " five " });
// {one} {two} {five} {four} {three}
for ( auto it = set. begin (); it != set. end (); ++it) {
it. key (key_buffer);
std::cout << " { " << key_buffer << " } " << std::endl;
}
} このライブラリは、マップまたはセットをシリアル化および逆シリアル化し、ファイルに保存したり、ネットワーク経由で送信したりするための効率的な方法を提供します。これを行うには、ユーザーはシリアル化と逆シリアル化の両方のための関数オブジェクトを提供する必要があります。
struct serializer {
// Must support the following types for U: std::uint64_t, float and T if a map is used.
template < typename U>
void operator ()( const U& value);
void operator ()( const CharT* value, std:: size_t value_size);
}; struct deserializer {
// Must support the following types for U: std::uint64_t, float and T if a map is used.
template < typename U>
U operator ()();
void operator ()(CharT* value_out, std:: size_t value_size);
};互換性が必要な場合、実装ではシリアル化/逆シリアル化する型のバイナリ互換性 (エンディアン、浮動小数点バイナリ表現、int のサイズなど) が提供された関数オブジェクトの手に委ねられることに注意してください。
serializeメソッドとdeserializeメソッドの詳細については、API を参照してください。
# include < cassert >
# include < cstdint >
# include < fstream >
# include < type_traits >
# include < tsl/htrie_map.h >
class serializer {
public:
serializer ( const char * file_name) {
m_ostream. exceptions (m_ostream. badbit | m_ostream. failbit );
m_ostream. open (file_name);
}
template < class T ,
typename std::enable_if<std::is_arithmetic<T>::value>::type* = nullptr >
void operator ()( const T& value) {
m_ostream. write ( reinterpret_cast < const char *>(&value), sizeof (T));
}
void operator ()( const char * value, std:: size_t value_size) {
m_ostream. write (value, value_size);
}
private:
std::ofstream m_ostream;
};
class deserializer {
public:
deserializer ( const char * file_name) {
m_istream. exceptions (m_istream. badbit | m_istream. failbit | m_istream. eofbit );
m_istream. open (file_name);
}
template < class T ,
typename std::enable_if<std::is_arithmetic<T>::value>::type* = nullptr >
T operator ()() {
T value;
m_istream. read ( reinterpret_cast < char *>(&value), sizeof (T));
return value;
}
void operator ()( char * value_out, std:: size_t value_size) {
m_istream. read (value_out, value_size);
}
private:
std::ifstream m_istream;
};
int main () {
const tsl::htrie_map< char , std:: int64_t > map = {{ " one " , 1 }, { " two " , 2 },
{ " three " , 3 }, { " four " , 4 }};
const char * file_name = " htrie_map.data " ;
{
serializer serial (file_name);
map. serialize (serial);
}
{
deserializer dserial (file_name);
auto map_deserialized = tsl::htrie_map< char , std:: int64_t >:: deserialize (dserial);
assert (map == map_deserialized);
}
{
deserializer dserial (file_name);
/* *
* If the serialized and deserialized map are hash compatibles (see conditions in API),
* setting the argument to true speed-up the deserialization process as we don't have
* to recalculate the hash of each key. We also know how much space each bucket needs.
*/
const bool hash_compatible = true ;
auto map_deserialized =
tsl::htrie_map< char , std:: int64_t >:: deserialize (dserial, hash_compatible);
assert (map == map_deserialized);
}
}シリアル化する型がより複雑な場合は、シリアル化ライブラリを使用して定型句の一部を回避することができます。
次の例では、Boost zlib 圧縮ストリームと Boost Serialization を使用して、生成されるシリアル化ファイルのサイズを削減します。
# include < boost/archive/binary_iarchive.hpp >
# include < boost/archive/binary_oarchive.hpp >
# include < boost/iostreams/filter/zlib.hpp >
# include < boost/iostreams/filtering_stream.hpp >
# include < boost/serialization/split_free.hpp >
# include < boost/serialization/utility.hpp >
# include < cassert >
# include < cstdint >
# include < fstream >
# include < tsl/htrie_map.h >
template < typename Archive>
struct serializer {
Archive& ar;
template < typename T>
void operator ()( const T& val) { ar & val; }
template < typename CharT>
void operator ()( const CharT* val, std:: size_t val_size) {
ar. save_binary ( reinterpret_cast < const void *>(val), val_size* sizeof (CharT));
}
};
template < typename Archive>
struct deserializer {
Archive& ar;
template < typename T>
T operator ()() { T val; ar & val; return val; }
template < typename CharT>
void operator ()(CharT* val_out, std:: size_t val_size) {
ar. load_binary ( reinterpret_cast < void *>(val_out), val_size* sizeof (CharT));
}
};
namespace boost { namespace serialization {
template < class Archive , class CharT , class T >
void serialize (Archive & ar, tsl::htrie_map<CharT, T>& map, const unsigned int version) {
split_free (ar, map, version);
}
template < class Archive , class CharT , class T >
void save (Archive & ar, const tsl::htrie_map<CharT, T>& map, const unsigned int version) {
serializer<Archive> serial{ar};
map. serialize (serial);
}
template < class Archive , class CharT , class T >
void load (Archive & ar, tsl::htrie_map<CharT, T>& map, const unsigned int version) {
deserializer<Archive> deserial{ar};
map = tsl::htrie_map<CharT, T>:: deserialize (deserial);
}
}}
int main () {
const tsl::htrie_map< char , std:: int64_t > map = {{ " one " , 1 }, { " two " , 2 },
{ " three " , 3 }, { " four " , 4 }};
const char * file_name = " htrie_map.data " ;
{
std::ofstream ofs;
ofs. exceptions (ofs. badbit | ofs. failbit );
ofs. open (file_name, std::ios::binary);
boost::iostreams::filtering_ostream fo;
fo. push ( boost::iostreams::zlib_compressor ());
fo. push (ofs);
boost::archive::binary_oarchive oa (fo);
oa << map;
}
{
std::ifstream ifs;
ifs. exceptions (ifs. badbit | ifs. failbit | ifs. eofbit );
ifs. open (file_name, std::ios::binary);
boost::iostreams::filtering_istream fi;
fi. push ( boost::iostreams::zlib_decompressor ());
fi. push (ifs);
boost::archive::binary_iarchive ia (fi);
tsl::htrie_map< char , std:: int64_t > map_deserialized;
ia >> map_deserialized;
assert (map == map_deserialized);
}
}このコードは MIT ライセンスに基づいてライセンスされています。詳細については、LICENSE ファイルを参照してください。
