hat trie
v0.6.0
Implementação de teste com base no "HAT-trie: uma estrutura de dados para strings baseada em Trie com consciência de cache". (Askitis Nikolas e Sinha Ranjan, 2007) artigo. Por enquanto, apenas o HAT-trie puro foi implementado, a versão híbrida pode chegar mais tarde. Detalhes sobre a estrutura de dados do HAT-trie podem ser encontrados aqui.
A biblioteca fornece uma maneira eficiente e compacta de armazenar um conjunto ou mapa de strings, compactando os prefixos comuns. Também permite procurar chaves que correspondam a um prefixo. Observe, porém, que os parâmetros padrão da estrutura são voltados para otimizar pesquisas exatas; se você fizer muitas pesquisas de prefixo, poderá reduzir o limite de intermitência por meio do método burst_threshold .
É uma estrutura bem adaptada para armazenar um grande número de strings.
Para a parte hash do array, o projeto array-hash é usado e incluído no repositório.
A biblioteca fornece duas classes: tsl::htrie_map e tsl::htrie_set .
tsl::hat_trie do CMakeLists.txt.equal_prefix_range (útil para preenchimento automático, por exemplo) e apagamentos de prefixo por meio de erase_prefix .longest_prefix .serialize/deserialize na API para obter detalhes).max_load_factor . Um fator de carga máximo mais baixo aumentará a velocidade, um fator mais alto reduzirá o uso de memória. Seu valor padrão é definido como 8,0.burst_threshold .KeySizeT .As garantias de segurança e exceção de thread são semelhantes aos contêineres STL.
A função hash padrão usada pela estrutura depende da presença de std::string_view . Se estiver disponível, std::hash<std::string_view> é usado, caso contrário, uma função hash simples FNV-1a é usada para evitar qualquer dependência.
Se você não puder usar C++17 ou posterior, recomendamos substituir a função hash por algo como CityHash, MurmurHash, FarmHash, ... para melhores desempenhos. Nos testes que fizemos, CityHash64 oferece uma melhoria de aproximadamente 20% nas leituras em comparação com 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; O std::hash<std::string> não pode ser usado de forma eficiente, pois a estrutura não armazena nenhum objeto std::string . Sempre que um hash fosse necessário, um std::string temporário teria que ser criado.
O benchmark consiste em inserir todos os títulos do namespace principal do arquivo da Wikipedia na estrutura de dados, verificar o espaço de memória utilizado após a inserção (incluindo potencial fragmentação de memória) e procurar novamente todos os títulos na estrutura de dados. O pico de uso de memória durante o processo de inserção também é medido com o tempo(1).
Cada título está associado a um int (32 bits). Todas as estruturas baseadas em hash usam CityHash64 como função hash. Para os testes marcados com reserve , a função reserve é chamada antecipadamente para evitar qualquer repetição.
Observe que tsl::hopscotch_map , std::unordered_map , google::dense_hash_map e spp::sparse_hash_map usam std::string como chave que impõe um tamanho mínimo de 32 bytes (em x64), mesmo que a chave tenha apenas um caractere. Outras estruturas podem armazenar chaves de um caractere com 1 byte + 8 bytes para um ponteiro (em x64).
O benchmark foi compilado com GCC 6.3 e rodado em Debian Stretch x64 com Intel i5-5200u e 8Go de RAM. Melhor de 20 corridas foi realizada.
O código do benchmark pode ser encontrado no Gist.
O conjunto de dados enwiki-20170320-all-titles-in-ns0.gz é classificado em ordem alfabética. Para este benchmark, primeiro embaralhamos o conjunto de dados por meio de shuf(1) para evitar um conjunto de dados classificado tendenciosamente.
| Biblioteca | Estrutura de dados | Memória de pico (MiB) | Memória (MiB) | Inserir (ns/chave) | Ler (ns/chave) |
|---|---|---|---|---|---|
| tsl::htrie_map | HAT-trie | 405.22 | 402,25 | 643,10 | 250,87 |
| tsl::htrie_map max_load_factor=4 | HAT-trie | 471,85 | 468,50 | 638,66 | 212,90 |
| tsl::htrie_map max_load_factor=2 | HAT-trie | 569,76 | 566,52 | 630,61 | 201.10 |
| tsl::htrie_map max_load_factor=1 | HAT-trie | 713,44 | 709.81 | 645,76 | 190,87 |
| cedro::da | Tentativa de matriz dupla | 1269,68 | 1254,41 | 1102.93 | 557,20 |
| cedro::da ORDERED=falso | Tentativa de matriz dupla | 1269,80 | 1254,41 | 1089,78 | 570,13 |
| cedro::da | Tentativa reduzida de matriz dupla | 1183.07 | 1167,79 | 1076,68 | 645,79 |
| cedro::da ORDERED=falso | Tentativa reduzida de matriz dupla | 1183.14 | 1167,85 | 1065,43 | 641,98 |
| cedro::da | Tentativa de prefixo de matriz dupla | 498,69 | 496,54 | 1.096,90 | 628.01 |
| cedro::da ORDERED=falso | Tentativa de prefixo de matriz dupla | 498,65 | 496,60 | 1048,40 | 628,94 |
| chapéu-trie 1 (C) | HAT-trie | 504.07 | 501,50 | 917.49 | 261,00 |
| qp tentativa (C) | Tentativa QP | 941,23 | 938.17 | 1349,25 | 1281,46 |
| tentativa de bit crítico (C) | Tentativa crítica | 1074,96 | 1071,98 | 2930,42 | 2.869,74 |
| JudySL (C) | Matriz Judy | 631.09 | 628,37 | 884,29 | 803.58 |
| JudyHS (C) | Matriz Judy | 723,44 | 719,47 | 476,79 | 417,15 |
| tsl::array_map | Tabela hash de matriz | 823,54 | 678,73 | 603,94 | 138,24 |
| tsl::array_map com reserva | Tabela hash de matriz | 564,26 | 555,91 | 249,52 | 128,28 |
| tsl::amarelinha_mapa | Tabela hash | 1325,83 | 1077,99 | 368,26 | 119,49 |
| tsl::amarelinha_mapa com reserva | Tabela hash | 1080,51 | 1077,98 | 240,58 | 119,91 |
| google::dense_hash_map | Tabela hash | 2319,40 | 1677.11 | 466,60 | 138,87 |
| google::dense_hash_map com reserva | Tabela hash | 1592,51 | 1589,99 | 259,56 | 120,40 |
| spp::sparse_hash_map | Tabela hash esparsa | 918,67 | 917.10 | 769,00 | 175,59 |
| spp::sparse_hash_map com reserva | Tabela hash esparsa | 913,35 | 910,65 | 427,22 | 159.08 |
| std::unordered_map | Tabela hash | 1249.05 | 1246,60 | 590,88 | 173,58 |
| std::unordered_map com reserva | Tabela hash | 1212.23 | 1209.71 | 350,33 | 178,70 |
As chaves são inseridas e lidas em ordem alfabética.
| Biblioteca | Estrutura de dados | Memória de pico (MiB) | Memória (MiB) | Inserir (ns/chave) | Ler (ns/chave) |
|---|---|---|---|---|---|
| tsl::htrie_map | HAT-trie | 396,10 | 393,22 | 255,76 | 68.08 |
| tsl::htrie_map max_load_factor=4 | HAT-trie | 465.02 | 461,80 | 248,88 | 59,23 |
| tsl::htrie_map max_load_factor=2 | HAT-trie | 543,99 | 541.21 | 230,13 | 53,50 |
| tsl::htrie_map max_load_factor=1 | HAT-trie | 692,29 | 689,70 | 243,84 | 49,22 |
| cedro::da | Tentativa de matriz dupla | 1269,58 | 1254,41 | 278,51 | 54,72 |
| cedro::da ORDERED=falso | Tentativa de matriz dupla | 1269,66 | 1254,41 | 264,43 | 56.02 |
| cedro::da | Tentativa reduzida de matriz dupla | 1183.01 | 1167,78 | 254,60 | 69,18 |
| cedro::da ORDERED=falso | Tentativa reduzida de matriz dupla | 1183.03 | 1167,78 | 241,45 | 69,67 |
| cedro::da | Tentativa de prefixo de matriz dupla | 621,59 | 619,38 | 246,88 | 57,83 |
| cedro::da ORDERED=falso | Tentativa de prefixo de matriz dupla | 621,59 | 619,38 | 187,98 | 58,56 |
| chapéu-trie 2 (C) | HAT-trie | 521,25 | 518,52 | 503.01 | 86,40 |
| qp tentativa (C) | Tentativa QP | 940,65 | 937,66 | 392,86 | 190,19 |
| tentativa de bit crítico (C) | Tentativa crítica | 1074,87 | 1071,98 | 430.04 | 347,60 |
| JudySL (C) | Matriz Judy | 616,95 | 614,27 | 279.07 | 114,47 |
| JudyHS (C) | Matriz Judy | 722,29 | 719,47 | 439,66 | 372,25 |
| tsl::array_map | Tabela hash de matriz | 826,98 | 682,99 | 612.31 | 139,16 |
| tsl::array_map com reserva | Tabela hash de matriz | 565,37 | 555,35 | 246,55 | 126,32 |
| tsl::amarelinha_mapa | Tabela hash | 1331,87 | 1078.02 | 375,19 | 118.08 |
| tsl::amarelinha_mapa com reserva | Tabela hash | 1080,51 | 1077,97 | 238,93 | 117,20 |
| google::dense_hash_map | Tabela hash | 2325.27 | 1683.07 | 483,95 | 137.09 |
| google::dense_hash_map com reserva | Tabela hash | 1592,54 | 1589,99 | 257,22 | 113,71 |
| spp::sparse_hash_map | Tabela hash esparsa | 920,96 | 918,70 | 772.03 | 176,64 |
| spp::sparse_hash_map com reserva | Tabela hash esparsa | 914,84 | 912.47 | 422,85 | 158,73 |
| std::unordered_map | Tabela hash | 1249.09 | 1246,65 | 594,85 | 173,54 |
| std::unordered_map com reserva | Tabela hash | 1212.21 | 1209.71 | 347,40 | 176,49 |
O benchmark consiste em inserir todas as palavras do conjunto de dados "Distinct Strings" do Dr. Askitis na estrutura de dados, verificar o espaço de memória utilizado e pesquisar todas as palavras do conjunto de dados "Skew String Set 1" (onde uma string pode ser presente várias vezes) na estrutura de dados. Observe que as strings neste conjunto de dados têm um comprimento de chave médio e mediano bastante curto (o que pode não ser um caso de uso realista em comparação com o conjunto de dados da Wikipedia usado acima). É semelhante ao da página inicial do cedro.
O protocolo de benchmark é o mesmo do conjunto de dados da Wikipedia.
| Biblioteca | Estrutura de dados | Memória de pico (MiB) | Memória (MiB) | Inserir (ns/chave) | Ler (ns/chave) |
|---|---|---|---|---|---|
| tsl::htrie_map | HAT-trie | 604,76 | 601,79 | 485,45 | 77,80 |
| tsl::htrie_map max_load_factor=4 | HAT-trie | 768,10 | 764,98 | 491,78 | 75,48 |
| tsl::htrie_map max_load_factor=2 | HAT-trie | 1002.42 | 999,34 | 496,78 | 72,53 |
| tsl::htrie_map max_load_factor=1 | HAT-trie | 1344,98 | 1341,97 | 520,66 | 72,45 |
| cedro::da | Tentativa de matriz dupla | 1105,45 | 1100,05 | 682,25 | 71,98 |
| cedro::da ORDERED=falso | Tentativa de matriz dupla | 1105.47 | 1100,05 | 668,75 | 71,95 |
| cedro::da | Tentativa reduzida de matriz dupla | 941.16 | 926.04 | 684,38 | 79.11 |
| cedro::da ORDERED=falso | Tentativa reduzida de matriz dupla | 941.16 | 925,98 | 672.14 | 79.02 |
| cedro::da | Tentativa de prefixo de matriz dupla | 714,58 | 712,59 | 831,71 | 75,83 |
| cedro::da ORDERED=falso | Tentativa de prefixo de matriz dupla | 714,66 | 712.31 | 786,93 | 75,89 |
| chapéu-trie 3 (C) | HAT-trie | 786,93 | 784,32 | 743,34 | 93,58 |
| qp tentativa (C) | Tentativa QP | 1800.02 | 1797.21 | 987,95 | 428,51 |
| tentativa de bit crítico (C) | Tentativa crítica | 2210.52 | 2207.64 | 1986.19 | 1109,88 |
| JudySL (C) | Matriz Judy | 1025,59 | 1023.11 | 535.02 | 202.36 |
| JudyHS (C) | Matriz Judy | 1002,50 | 999,97 | 456,09 | 148,36 |
| tsl::array_map | Tabela hash de matriz | 1308.08 | 1031,67 | 545,82 | 46,41 |
| tsl::array_map com reserva | Tabela hash de matriz | 979,44 | 921.363 | 244,19 | 45,74 |
| tsl::amarelinha_mapa | Tabela hash | 2336,39 | 1611.54 | 288,70 | 47.05 |
| tsl::amarelinha_mapa com reserva | Tabela hash | 1614.22 | 1611.64 | 220,67 | 46,39 |
| google::dense_hash_map | Tabela hash | 3913,64 | 2636,31 | 317,66 | 43,62 |
| google::dense_hash_map com reserva | Tabela hash | 2638.19 | 2635,68 | 227,58 | 43.09 |
| spp::sparse_hash_map | Tabela hash esparsa | 1419,69 | 1417.61 | 586,26 | 56,00 |
| spp::sparse_hash_map com reserva | Tabela hash esparsa | 1424.21 | 1421,69 | 392,76 | 55,73 |
| std::unordered_map | Tabela hash | 2112.66 | 2110.19 | 554.02 | 105,05 |
| std::unordered_map com reserva | Tabela hash | 2.053,95 | 2051,67 | 309.06 | 109,89 |
Para usar a biblioteca, basta adicionar o diretório include ao seu caminho de inclusão. É uma biblioteca somente de cabeçalho .
Se você usa o CMake, também pode usar o destino exportado tsl::hat_trie do CMakeLists.txt com 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) O código deve funcionar com qualquer compilador compatível com o padrão C++ 11 e foi testado com GCC 4.8.4, Clang 3.5.0 e Visual Studio 2015.
Para executar os testes você precisará da biblioteca Boost Test e do 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 A API pode ser encontrada aqui. Se std::string_view estiver disponível, a API muda ligeiramente e pode ser encontrada aqui.
# 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;
}
} A biblioteca fornece uma maneira eficiente de serializar e desserializar um mapa ou conjunto para que ele possa ser salvo em um arquivo ou enviado pela rede. Para fazer isso, é necessário que o usuário forneça um objeto de função para serialização e desserialização.
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);
};Observe que a implementação deixa a compatibilidade binária (endianness, representação binária flutuante, tamanho de int, ...) dos tipos que ela serializa/desserializa nas mãos dos objetos de função fornecidos, se a compatibilidade for necessária.
Mais detalhes sobre os métodos serialize e deserialize podem ser encontrados na 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);
}
}É possível usar uma biblioteca de serialização para evitar alguns clichês se os tipos a serem serializados forem mais complexos.
O exemplo a seguir usa Boost Serialization com o fluxo de compactação Boost zlib para reduzir o tamanho do arquivo 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);
}
}O código está licenciado sob a licença MIT, consulte o arquivo LICENSE para obter detalhes.
