hat trie
v0.6.0
Implémentation de Trie basée sur « HAT-trie : une structure de données basée sur Trie et soucieuse du cache pour les chaînes ». (Askitis Nikolas et Sinha Ranjan, 2007). Pour l'instant, seul le HAT-trie pur a été implémenté, la version hybride pourrait arriver plus tard. Des détails concernant la structure de données HAT-trie peuvent être trouvés ici.
La bibliothèque fournit un moyen efficace et compact de stocker un ensemble ou une carte de chaînes en compressant les préfixes communs. Il permet également de rechercher des clés correspondant à un préfixe. Notez cependant que les paramètres par défaut de la structure visent à optimiser les recherches exactes. Si vous effectuez de nombreuses recherches de préfixes, vous souhaiterez peut-être réduire le seuil de rafale via la méthode burst_threshold .
C'est une structure bien adaptée pour stocker un grand nombre de chaînes.
Pour la partie hachage de tableau, le projet array-hash est utilisé et inclus dans le référentiel.
La bibliothèque fournit deux classes : tsl::htrie_map et tsl::htrie_set .
tsl::hat_trie à partir du fichier CMakeLists.txt.equal_prefix_range (utile pour la saisie semi-automatique par exemple) et les effacements de préfixes via erase_prefix .longest_prefix .serialize/deserialize dans l'API pour plus de détails).max_load_factor . Un facteur de charge maximum inférieur augmentera la vitesse, un facteur plus élevé réduira l'utilisation de la mémoire. Sa valeur par défaut est définie sur 8,0.burst_threshold .KeySizeT .Les garanties de sécurité des threads et d’exceptions sont similaires à celles des conteneurs STL.
La fonction de hachage par défaut utilisée par la structure dépend de la présence de std::string_view . S'il est disponible, std::hash<std::string_view> est utilisé, sinon une simple fonction de hachage FNV-1a est utilisée pour éviter toute dépendance.
Si vous ne pouvez pas utiliser C++ 17 ou version ultérieure, nous vous recommandons de remplacer la fonction de hachage par quelque chose comme CityHash, MurmurHash, FarmHash, ... pour de meilleures performances. Sur les tests que nous avons effectués, CityHash64 offre une amélioration d'environ 20 % sur les lectures par rapport au FNV-1a.
# 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; Le std::hash<std::string> ne peut pas être utilisé efficacement car la structure ne stocke aucun objet std::string . Chaque fois qu'un hachage serait nécessaire, une std::string temporaire devrait être créée.
Le benchmark consiste à insérer tous les titres de l'espace de noms principal de l'archive Wikipédia dans la structure de données, à vérifier l'espace mémoire utilisé après l'insertion (y compris la fragmentation potentielle de la mémoire) et à rechercher à nouveau tous les titres dans la structure de données. L'utilisation maximale de la mémoire pendant le processus d'insertion est également mesurée avec le temps (1).
Chaque titre est associé à un int (32 bits). Toutes les structures basées sur le hachage utilisent CityHash64 comme fonction de hachage. Pour les tests marqués de réserve , la fonction reserve est appelée au préalable pour éviter toute resucée.
Notez que tsl::hopscotch_map , std::unordered_map , google::dense_hash_map et spp::sparse_hash_map utilisent std::string comme clé qui impose une taille minimale de 32 octets (sur x64) même si la clé ne comporte qu'un seul caractère. D'autres structures peuvent être capables de stocker des clés à un caractère avec 1 octet + 8 octets pour un pointeur (sur x64).
Le benchmark a été compilé avec GCC 6.3 et fonctionnait sur Debian Stretch x64 avec un Intel i5-5200u et 8Go de RAM. Le meilleur des 20 runs a été réalisé.
Le code du benchmark peut être trouvé sur Gist.
L'ensemble de données enwiki-20170320-all-titles-in-ns0.gz est trié par ordre alphabétique. Pour ce benchmark, nous mélangeons d'abord l'ensemble de données via shuf(1) pour éviter un ensemble de données trié biaisé.
| Bibliothèque | Structure des données | Mémoire maximale (MiB) | Mémoire (Mio) | Insérer (ns/clé) | Lire (ns/clé) |
|---|---|---|---|---|---|
| tsl :: htrie_map | CHAPEAU-trie | 405.22 | 402.25 | 643.10 | 250,87 |
| tsl :: htrie_map max_load_factor=4 | CHAPEAU-trie | 471,85 | 468,50 | 638,66 | 212,90 |
| tsl :: htrie_map max_load_factor=2 | CHAPEAU-trie | 569,76 | 566.52 | 630.61 | 201.10 |
| tsl :: htrie_map max_load_factor=1 | CHAPEAU-trie | 713.44 | 709.81 | 645,76 | 190,87 |
| cèdre ::da | Essai à double matrice | 1269.68 | 1254.41 | 1102.93 | 557.20 |
| cèdre ::da ORDERED=false | Essai à double matrice | 1269.80 | 1254.41 | 1089.78 | 570.13 |
| cèdre ::da | Essai réduit à double réseau | 1183.07 | 1167.79 | 1076.68 | 645,79 |
| cèdre ::da ORDERED=false | Essai réduit à double réseau | 1183.14 | 1167.85 | 1065.43 | 641,98 |
| cèdre ::da | Essai de préfixe à double tableau | 498,69 | 496,54 | 1096.90 | 628.01 |
| cèdre ::da ORDERED=false | Essai de préfixe à double tableau | 498,65 | 496,60 | 1048.40 | 628,94 |
| chapeau-trie 1 (C) | CHAPEAU-trie | 504.07 | 501,50 | 917.49 | 261,00 |
| qp trie (C) | Essai QP | 941.23 | 938.17 | 1349.25 | 1281.46 |
| essai de bits critiques (C) | Essai critique | 1074.96 | 1071,98 | 2930.42 | 2869.74 |
| JudySL (C) | Tableau Judy | 631.09 | 628.37 | 884.29 | 803.58 |
| JudyHS (C) | Tableau Judy | 723.44 | 719.47 | 476,79 | 417.15 |
| tsl :: array_map | Table de hachage de tableau | 823.54 | 678,73 | 603.94 | 138.24 |
| tsl :: array_map avec réserve | Table de hachage de tableau | 564.26 | 555.91 | 249,52 | 128.28 |
| tsl :: hopscotch_map | Table de hachage | 1325.83 | 1077,99 | 368.26 | 119.49 |
| tsl :: hopscotch_map avec réserve | Table de hachage | 1080.51 | 1077,98 | 240,58 | 119.91 |
| google::dense_hash_map | Table de hachage | 2319.40 | 1677.11 | 466,60 | 138,87 |
| google::dense_hash_map avec réserve | Table de hachage | 1592.51 | 1589,99 | 259,56 | 120.40 |
| spp :: sparse_hash_map | Table de hachage clairsemée | 918.67 | 917.10 | 769.00 | 175,59 |
| spp :: sparse_hash_map avec réserve | Table de hachage clairsemée | 913.35 | 910.65 | 427.22 | 159.08 |
| std :: unordered_map | Table de hachage | 1249.05 | 1246.60 | 590,88 | 173,58 |
| std :: unordered_map avec réserve | Table de hachage | 1212.23 | 1209.71 | 350.33 | 178,70 |
Les clés sont insérées et lues par ordre alphabétique.
| Bibliothèque | Structure des données | Mémoire maximale (MiB) | Mémoire (Mio) | Insérer (ns/clé) | Lire (ns/clé) |
|---|---|---|---|---|---|
| tsl :: htrie_map | CHAPEAU-trie | 396.10 | 393.22 | 255,76 | 68.08 |
| tsl :: htrie_map max_load_factor=4 | CHAPEAU-trie | 465.02 | 461,80 | 248,88 | 59.23 |
| tsl :: htrie_map max_load_factor=2 | CHAPEAU-trie | 543,99 | 541.21 | 230.13 | 53,50 |
| tsl :: htrie_map max_load_factor=1 | CHAPEAU-trie | 692.29 | 689,70 | 243,84 | 49.22 |
| cèdre ::da | Essai à double matrice | 1269.58 | 1254.41 | 278,51 | 54,72 |
| cèdre ::da ORDERED=false | Essai à double matrice | 1269.66 | 1254.41 | 264.43 | 56.02 |
| cèdre ::da | Essai réduit à double matrice | 1183.01 | 1167.78 | 254,60 | 69.18 |
| cèdre ::da ORDERED=false | Essai réduit à double matrice | 1183.03 | 1167.78 | 241,45 | 69,67 |
| cèdre ::da | Essai de préfixe à double tableau | 621,59 | 619.38 | 246,88 | 57,83 |
| cèdre ::da ORDERED=false | Essai de préfixe à double tableau | 621,59 | 619.38 | 187,98 | 58.56 |
| chapeau-trie 2 (C) | CHAPEAU-trie | 521.25 | 518.52 | 503.01 | 86.40 |
| qp trie (C) | Essai QP | 940,65 | 937.66 | 392,86 | 190.19 |
| essai de bits critiques (C) | Essai critique | 1074.87 | 1071,98 | 430.04 | 347,60 |
| JudySL (C) | Tableau Judy | 616,95 | 614.27 | 279.07 | 114.47 |
| JudyHS (C) | Tableau Judy | 722.29 | 719.47 | 439,66 | 372.25 |
| tsl :: array_map | Table de hachage de tableau | 826,98 | 682,99 | 612.31 | 139.16 |
| tsl :: array_map avec réserve | Table de hachage de tableau | 565.37 | 555,35 | 246,55 | 126.32 |
| tsl :: hopscotch_map | Table de hachage | 1331.87 | 1078.02 | 375.19 | 118.08 |
| tsl :: hopscotch_map avec réserve | Table de hachage | 1080.51 | 1077,97 | 238,93 | 117.20 |
| google::dense_hash_map | Table de hachage | 2325.27 | 1683.07 | 483,95 | 137.09 |
| google::dense_hash_map avec réserve | Table de hachage | 1592.54 | 1589,99 | 257.22 | 113.71 |
| spp :: sparse_hash_map | Table de hachage clairsemée | 920,96 | 918.70 | 772.03 | 176,64 |
| spp :: sparse_hash_map avec réserve | Table de hachage clairsemée | 914.84 | 912.47 | 422,85 | 158,73 |
| std :: unordered_map | Table de hachage | 1249.09 | 1246.65 | 594,85 | 173,54 |
| std :: unordered_map avec réserve | Table de hachage | 1212.21 | 1209.71 | 347.40 | 176,49 |
Le benchmark consiste à insérer tous les mots du jeu de données "Distinct Strings" du Dr Askitis dans la structure de données, à vérifier l'espace mémoire utilisé et à rechercher tous les mots du jeu de données "Skew String Set 1" (où une chaîne peut être présents plusieurs fois) dans la structure de données. Notez que les chaînes de cet ensemble de données ont une longueur de clé moyenne et médiane assez courte (ce qui peut ne pas être un cas d'utilisation réaliste par rapport à l'ensemble de données Wikipédia utilisé ci-dessus). C'est similaire à celui de la page d'accueil de Cedar.
Le protocole de référence est le même que pour l'ensemble de données Wikipédia.
| Bibliothèque | Structure des données | Mémoire maximale (MiB) | Mémoire (Mio) | Insérer (ns/clé) | Lire (ns/clé) |
|---|---|---|---|---|---|
| tsl :: htrie_map | CHAPEAU-trie | 604.76 | 601.79 | 485.45 | 77,80 |
| tsl :: htrie_map max_load_factor=4 | CHAPEAU-trie | 768.10 | 764,98 | 491,78 | 75.48 |
| tsl :: htrie_map max_load_factor=2 | CHAPEAU-trie | 1002.42 | 999.34 | 496,78 | 72.53 |
| tsl :: htrie_map max_load_factor=1 | CHAPEAU-trie | 1344.98 | 1341.97 | 520,66 | 72.45 |
| cèdre ::da | Essai à double matrice | 1105.45 | 1100.05 | 682.25 | 71,98 |
| cèdre ::da ORDERED=false | Essai à double matrice | 1105.47 | 1100.05 | 668,75 | 71,95 |
| cèdre ::da | Essai réduit à double matrice | 941.16 | 926.04 | 684.38 | 79.11 |
| cèdre ::da ORDERED=false | Essai réduit à double matrice | 941.16 | 925,98 | 672.14 | 79.02 |
| cèdre ::da | Essai de préfixe à double tableau | 714.58 | 712.59 | 831.71 | 75,83 |
| cèdre ::da ORDERED=false | Essai de préfixe à double tableau | 714.66 | 712.31 | 786.93 | 75,89 |
| chapeau-trie 3 (C) | CHAPEAU-trie | 786.93 | 784.32 | 743.34 | 93.58 |
| qp trie (C) | Essai QP | 1800.02 | 1797.21 | 987,95 | 428.51 |
| essai de bits critiques (C) | Essai critique | 2210.52 | 2207.64 | 1986.19 | 1109.88 |
| JudySL (C) | Tableau Judy | 1025.59 | 1023.11 | 535.02 | 202.36 |
| JudyHS (C) | Tableau Judy | 1002,50 | 999,97 | 456.09 | 148.36 |
| tsl :: array_map | Table de hachage de tableau | 1308.08 | 1031.67 | 545.82 | 46.41 |
| tsl :: array_map avec réserve | Table de hachage de tableau | 979.44 | 921.363 | 244.19 | 45,74 |
| tsl :: hopscotch_map | Table de hachage | 2336.39 | 1611.54 | 288,70 | 47.05 |
| tsl :: hopscotch_map avec réserve | Table de hachage | 1614.22 | 1611.64 | 220,67 | 46.39 |
| google::dense_hash_map | Table de hachage | 3913.64 | 2636.31 | 317,66 | 43.62 |
| google::dense_hash_map avec réserve | Table de hachage | 2638.19 | 2635.68 | 227,58 | 43.09 |
| spp :: sparse_hash_map | Table de hachage clairsemée | 1419.69 | 1417.61 | 586.26 | 56h00 |
| spp :: sparse_hash_map avec réserve | Table de hachage clairsemée | 1424.21 | 1421.69 | 392,76 | 55,73 |
| std :: unordered_map | Table de hachage | 2112.66 | 2110.19 | 554.02 | 105.05 |
| std :: unordered_map avec réserve | Table de hachage | 2053.95 | 2051.67 | 309.06 | 109,89 |
Pour utiliser la bibliothèque, ajoutez simplement le répertoire include à votre chemin d'inclusion. Il s'agit d'une bibliothèque d'en-tête uniquement .
Si vous utilisez CMake, vous pouvez également utiliser la cible exportée tsl::hat_trie à partir du CMakeLists.txt avec target_link_libraries .
# 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) Le code doit fonctionner avec n'importe quel compilateur conforme à la norme C++11 et a été testé avec GCC 4.8.4, Clang 3.5.0 et Visual Studio 2015.
Pour exécuter les tests, vous aurez besoin de la bibliothèque Boost Test et de CMake.
git clone https://github.com/Tessil/hat-trie.git
cd hat-trie/tests
mkdir build
cd build
cmake ..
cmake --build .
./tsl_hat_trie_tests L'API peut être trouvée ici. Si std::string_view est disponible, l'API change légèrement et peut être trouvée ici.
# 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;
}
} La bibliothèque fournit un moyen efficace de sérialiser et de désérialiser une carte ou un ensemble afin qu'il puisse être enregistré dans un fichier ou envoyé via le réseau. Pour ce faire, l'utilisateur doit fournir un objet fonction pour la sérialisation et la désérialisation.
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);
};Notez que l'implémentation laisse la compatibilité binaire (endianisme, représentation binaire flottante, taille de int, ...) des types qu'elle sérialise/désérialise entre les mains des objets fonction fournis si la compatibilité est requise.
Plus de détails concernant les méthodes serialize et deserialize peuvent être trouvés dans l'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);
}
}Il est possible d'utiliser une bibliothèque de sérialisation pour éviter certains passe-partout si les types à sérialiser sont plus complexes.
L'exemple suivant utilise Boost Serialization avec le flux de compression Boost zlib pour réduire la taille du fichier sérialisé résultant.
# 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);
}
}Le code est sous licence MIT, voir le fichier LICENSE pour plus de détails.
