hat trie
v0.6.0
Implementación de Trie basada en "HAT-trie: una estructura de datos para cadenas basada en Trie consciente de la caché". (Askitis Nikolas y Sinha Ranjan, 2007) artículo. Por ahora, sólo se ha implementado el HAT-trie puro, la versión híbrida puede llegar más adelante. Los detalles sobre la estructura de datos HAT-trie se pueden encontrar aquí.
La biblioteca proporciona una manera eficiente y compacta de almacenar un conjunto o un mapa de cadenas comprimiendo los prefijos comunes. También permite buscar claves que coincidan con un prefijo. Sin embargo, tenga en cuenta que los parámetros predeterminados de la estructura están orientados a optimizar las búsquedas exactas; si realiza muchas búsquedas de prefijos, es posible que desee reducir el umbral de ráfaga mediante el método burst_threshold .
Es una estructura bien adaptada para almacenar una gran cantidad de cuerdas.
Para la parte del hash de matriz, se utiliza el proyecto array-hash y se incluye en el repositorio.
La biblioteca proporciona dos clases: tsl::htrie_map y tsl::htrie_set .
tsl::hat_trie desde CMakeLists.txt.equal_prefix_range (útil para el autocompletado, por ejemplo) y borrados de prefijos a través de erase_prefix .longest_prefix .serialize/deserialize en la API para obtener más detalles).max_load_factor . Un factor de carga máximo más bajo aumentará la velocidad, uno más alto reducirá el uso de memoria. Su valor predeterminado está establecido en 8,0.burst_threshold .KeySizeT .Las garantías de excepción y seguridad de subprocesos son similares a las de los contenedores STL.
La función hash predeterminada utilizada por la estructura depende de la presencia de std::string_view . Si está disponible, se usa std::hash<std::string_view> ; de lo contrario, se usa una función hash FNV-1a simple para evitar cualquier dependencia.
Si no puede usar C++ 17 o posterior, le recomendamos reemplazar la función hash con algo como CityHash, MurmurHash, FarmHash, ... para obtener mejores rendimientos. En las pruebas que hicimos, CityHash64 ofrece una mejora de ~20 % en las lecturas en comparación con 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; El std::hash<std::string> no se puede utilizar de manera eficiente ya que la estructura no almacena ningún objeto std::string . Cada vez que se necesitara un hash, se tendría que crear un std::string temporal.
La prueba consiste en insertar todos los títulos del espacio de nombres principal del archivo Wikipedia en la estructura de datos, verificar el espacio de memoria utilizado después de la inserción (incluida la posible fragmentación de la memoria) y buscar todos los títulos nuevamente en la estructura de datos. El uso máximo de memoria durante el proceso de inserción también se mide con el tiempo (1).
Cada título está asociado a un int (32 bits). Todas las estructuras basadas en hash utilizan CityHash64 como función hash. Para las pruebas marcadas con reserve , la función reserve se llama de antemano para evitar cualquier repetición.
Tenga en cuenta que tsl::hopscotch_map , std::unordered_map , google::dense_hash_map y spp::sparse_hash_map usan std::string como clave que impone un tamaño mínimo de 32 bytes (en x64) incluso si la clave tiene solo un carácter. Es posible que otras estructuras puedan almacenar claves de un carácter con 1 byte + 8 bytes para un puntero (en x64).
El punto de referencia se compiló con GCC 6.3 y se ejecutó en Debian Stretch x64 con un Intel i5-5200u y 8Go de RAM. Se tomó el mejor de 20 carreras.
El código del punto de referencia se puede encontrar en Gist.
El conjunto de datos enwiki-20170320-all-titles-in-ns0.gz está ordenado alfabéticamente. Para este punto de referencia, primero mezclamos el conjunto de datos mediante shuf(1) para evitar un conjunto de datos ordenados sesgados.
| Biblioteca | estructura de datos | Memoria máxima (MiB) | Memoria (MiB) | Insertar (ns/clave) | Leer (ns/clave) |
|---|---|---|---|---|---|
| tsl::htrie_map | SOMBRERO | 405.22 | 402.25 | 643.10 | 250,87 |
| tsl::htrie_map factor_carga_max=4 | SOMBRERO | 471.85 | 468.50 | 638,66 | 212.90 |
| tsl::htrie_map factor_carga_max=2 | SOMBRERO | 569,76 | 566,52 | 630.61 | 201.10 |
| tsl::htrie_map factor_carga_max=1 | SOMBRERO | 713.44 | 709.81 | 645,76 | 190,87 |
| cedro::da | Trie de doble matriz | 1269.68 | 1254.41 | 1102.93 | 557.20 |
| cedro::da ORDENADO=falso | Trie de doble matriz | 1269.80 | 1254.41 | 1089,78 | 570.13 |
| cedro::da | Trie reducido de doble matriz | 1183.07 | 1167,79 | 1076.68 | 645,79 |
| cedro::da ORDENADO=falso | Trie reducido de doble matriz | 1183.14 | 1167,85 | 1065.43 | 641,98 |
| cedro::da | Trie de prefijo de doble matriz | 498.69 | 496.54 | 1096.90 | 628.01 |
| cedro::da ORDENADO=falso | Trie de prefijo de doble matriz | 498.65 | 496.60 | 1048.40 | 628,94 |
| sombrero-trio 1 (C) | SOMBRERO | 504.07 | 501.50 | 917.49 | 261.00 |
| qp intento (C) | intento QP | 941.23 | 938.17 | 1349.25 | 1281.46 |
| Trie de bits críticos (C) | Trio de crítico | 1074,96 | 1071,98 | 2930.42 | 2869,74 |
| Judy SL (C) | matriz de judy | 631.09 | 628,37 | 884.29 | 803.58 |
| Judy HS (C) | matriz de judy | 723,44 | 719,47 | 476,79 | 417.15 |
| tsl::array_map | tabla hash de matriz | 823.54 | 678,73 | 603.94 | 138.24 |
| tsl::array_map con reserva | tabla hash de matriz | 564.26 | 555.91 | 249,52 | 128,28 |
| tsl::rayuela_map | tabla hash | 1325.83 | 1077,99 | 368,26 | 119,49 |
| tsl::rayuela_map con reserva | tabla hash | 1080.51 | 1077,98 | 240.58 | 119,91 |
| google::dense_hash_map | tabla hash | 2319.40 | 1677.11 | 466.60 | 138,87 |
| google::dense_hash_map con reserva | tabla hash | 1592.51 | 1589.99 | 259,56 | 120.40 |
| spp::sparse_hash_map | tabla hash dispersa | 918.67 | 917.10 | 769.00 | 175,59 |
| spp::sparse_hash_map con reserva | tabla hash dispersa | 913.35 | 910.65 | 427.22 | 159.08 |
| std::mapa_desordenado | tabla hash | 1249.05 | 1246.60 | 590,88 | 173,58 |
| std::mapa_desordenado con reserva | tabla hash | 1212.23 | 1209.71 | 350.33 | 178,70 |
Las claves se insertan y leen en orden alfabético.
| Biblioteca | estructura de datos | Memoria máxima (MiB) | Memoria (MiB) | Insertar (ns/clave) | Leer (ns/clave) |
|---|---|---|---|---|---|
| tsl::htrie_map | SOMBRERO | 396.10 | 393.22 | 255,76 | 68.08 |
| tsl::htrie_map factor_carga_max=4 | SOMBRERO | 465.02 | 461.80 | 248,88 | 59,23 |
| tsl::htrie_map factor_carga_max=2 | SOMBRERO | 543,99 | 541.21 | 230.13 | 53,50 |
| tsl::htrie_map factor_carga_max=1 | SOMBRERO | 692,29 | 689,70 | 243,84 | 49.22 |
| cedro::da | Trie de doble matriz | 1269.58 | 1254.41 | 278,51 | 54,72 |
| cedro::da ORDENADO=falso | Trie de doble matriz | 1269.66 | 1254.41 | 264,43 | 56.02 |
| cedro::da | Trie reducido de doble matriz | 1183.01 | 1167,78 | 254,60 | 69.18 |
| cedro::da ORDENADO=falso | Trie reducido de doble matriz | 1183.03 | 1167,78 | 241,45 | 69,67 |
| cedro::da | Trie de prefijo de doble matriz | 621.59 | 619.38 | 246,88 | 57,83 |
| cedro::da ORDENADO=falso | Trie de prefijo de doble matriz | 621.59 | 619.38 | 187,98 | 58,56 |
| hat-trie 2 (C) | SOMBRERO | 521.25 | 518.52 | 503.01 | 86,40 |
| qp intento (C) | intento QP | 940.65 | 937,66 | 392,86 | 190.19 |
| Trie de bits críticos (C) | Trio de crítico | 1074.87 | 1071,98 | 430.04 | 347,60 |
| Judy SL (C) | matriz de judy | 616.95 | 614.27 | 279.07 | 114,47 |
| Judy HS (C) | matriz de judy | 722.29 | 719,47 | 439,66 | 372,25 |
| tsl::array_map | tabla hash de matriz | 826,98 | 682,99 | 612.31 | 139.16 |
| tsl::array_map con reserva | tabla hash de matriz | 565.37 | 555.35 | 246,55 | 126,32 |
| tsl::rayuela_map | tabla hash | 1331.87 | 1078.02 | 375.19 | 118.08 |
| tsl::rayuela_map con reserva | tabla hash | 1080.51 | 1077,97 | 238,93 | 117.20 |
| google::dense_hash_map | tabla hash | 2325.27 | 1683.07 | 483.95 | 137.09 |
| google::dense_hash_map con reserva | tabla hash | 1592.54 | 1589.99 | 257,22 | 113,71 |
| spp::sparse_hash_map | tabla hash dispersa | 920.96 | 918.70 | 772.03 | 176,64 |
| spp::sparse_hash_map con reserva | tabla hash dispersa | 914.84 | 912.47 | 422.85 | 158,73 |
| std::mapa_desordenado | tabla hash | 1249.09 | 1246.65 | 594,85 | 173,54 |
| std::mapa_desordenado con reserva | tabla hash | 1212.21 | 1209.71 | 347,40 | 176,49 |
El benchmark consiste en insertar todas las palabras del conjunto de datos "Distinct Strings" del Dr. Askitis en la estructura de datos, verificar el espacio de memoria utilizado y buscar todas las palabras del conjunto de datos "Skew String Set 1" (donde una cadena puede ser presente varias veces) en la estructura de datos. Tenga en cuenta que las cadenas de este conjunto de datos tienen una longitud de clave promedio y mediana bastante corta (lo que puede no ser un caso de uso realista en comparación con el conjunto de datos de Wikipedia utilizado anteriormente). Es similar al de la página de inicio de Cedar.
El protocolo de referencia es el mismo que el del conjunto de datos de Wikipedia.
| Biblioteca | estructura de datos | Memoria máxima (MiB) | Memoria (MiB) | Insertar (ns/clave) | Leer (ns/clave) |
|---|---|---|---|---|---|
| tsl::htrie_map | SOMBRERO | 604.76 | 601.79 | 485.45 | 77,80 |
| tsl::htrie_map factor_carga_max=4 | SOMBRERO | 768.10 | 764,98 | 491,78 | 75,48 |
| tsl::htrie_map factor_carga_max=2 | SOMBRERO | 1002.42 | 999,34 | 496,78 | 72,53 |
| tsl::htrie_map factor_carga_max=1 | SOMBRERO | 1344,98 | 1341,97 | 520.66 | 72,45 |
| cedro::da | Trie de doble matriz | 1105.45 | 1100.05 | 682,25 | 71,98 |
| cedro::da ORDENADO=falso | Trie de doble matriz | 1105.47 | 1100.05 | 668,75 | 71,95 |
| cedro::da | Trie reducido de doble matriz | 941.16 | 926.04 | 684,38 | 79.11 |
| cedro::da ORDENADO=falso | Trie reducido de doble matriz | 941.16 | 925.98 | 672.14 | 79.02 |
| cedro::da | Trie de prefijo de doble matriz | 714,58 | 712.59 | 831.71 | 75,83 |
| cedro::da ORDENADO=falso | Trie de prefijo de doble matriz | 714,66 | 712.31 | 786,93 | 75,89 |
| triplete 3 (C) | SOMBRERO | 786,93 | 784,32 | 743.34 | 93,58 |
| qp intento (C) | intento QP | 1800.02 | 1797.21 | 987,95 | 428.51 |
| Trie de bits críticos (C) | Trio de crítico | 2210.52 | 2207.64 | 1986.19 | 1109.88 |
| Judy SL (C) | matriz de judy | 1025.59 | 1023.11 | 535.02 | 202.36 |
| Judy HS (C) | matriz de judy | 1002.50 | 999,97 | 456.09 | 148,36 |
| tsl::array_map | tabla hash de matriz | 1308.08 | 1031.67 | 545.82 | 46,41 |
| tsl::array_map con reserva | tabla hash de matriz | 979,44 | 921.363 | 244.19 | 45,74 |
| tsl::rayuela_map | tabla hash | 2336.39 | 1611.54 | 288.70 | 47.05 |
| tsl::rayuela_map con reserva | tabla hash | 1614.22 | 1611.64 | 220.67 | 46,39 |
| google::dense_hash_map | tabla hash | 3913.64 | 2636.31 | 317,66 | 43,62 |
| google::dense_hash_map con reserva | tabla hash | 2638.19 | 2635.68 | 227,58 | 43.09 |
| spp::sparse_hash_map | tabla hash dispersa | 1419.69 | 1417.61 | 586.26 | 56.00 |
| spp::sparse_hash_map con reserva | tabla hash dispersa | 1424.21 | 1421.69 | 392,76 | 55,73 |
| std::mapa_desordenado | tabla hash | 2112.66 | 2110.19 | 554.02 | 105.05 |
| std::mapa_desordenado con reserva | tabla hash | 2053.95 | 2051.67 | 309.06 | 109,89 |
Para usar la biblioteca, simplemente agregue el directorio de inclusión a su ruta de inclusión. Es una biblioteca de solo encabezados .
Si usa CMake, también puede usar el destino exportado tsl::hat_trie desde CMakeLists.txt con 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) El código debería funcionar con cualquier compilador compatible con el estándar C++ 11 y ha sido probado con GCC 4.8.4, Clang 3.5.0 y Visual Studio 2015.
Para ejecutar las pruebas necesitará la biblioteca Boost Test y 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 La API se puede encontrar aquí. Si std::string_view está disponible, la API cambia ligeramente y se puede encontrar aquí.
# 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 biblioteca proporciona una forma eficaz de serializar y deserializar un mapa o un conjunto para poder guardarlo en un archivo o enviarlo a través de la red. Para hacerlo, requiere que el usuario proporcione un objeto de función tanto para la serialización como para la deserialización.
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);
};Tenga en cuenta que la implementación deja la compatibilidad binaria (endianidad, representación binaria flotante, tamaño de int, ...) de los tipos que serializa/deserializa en manos de los objetos de función proporcionados si se requiere compatibilidad.
Se pueden encontrar más detalles sobre los métodos serialize y deserialize en la 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);
}
}Es posible utilizar una biblioteca de serialización para evitar parte del texto repetitivo si los tipos a serializar son más complejos.
El siguiente ejemplo utiliza Boost Serialization con el flujo de compresión Boost zlib para reducir el tamaño del archivo serializado resultante.
# 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);
}
}El código tiene la licencia MIT; consulte el archivo LICENCIA para obtener más detalles.
