hat trie
v0.6.0
Реализация Trie основана на «HAT-trie: структура данных на основе Trie с учетом кэша для строк». (Аскитис Николас и Синха Ранджан, 2007). На данный момент реализована только чистая HAT-трия, гибридная версия может появиться позже. Подробности о структуре данных HAT-trie можно найти здесь.
Библиотека предоставляет эффективный и компактный способ хранения набора или карты строк путем сжатия общих префиксов. Это также позволяет искать ключи, соответствующие префиксу. Однако обратите внимание, что параметры структуры по умолчанию предназначены для оптимизации точного поиска. Если вы выполняете много префиксных поисков, вы можете уменьшить порог пакета с помощью burst_threshold .
Это хорошо адаптированная структура для хранения большого количества строк.
Для части хэша массива используется проект array-hash, который включен в репозиторий.
Библиотека предоставляет два класса: tsl::htrie_map и tsl::htrie_set .
tsl::hat_trie из файла CMakeLists.txt.equal_prefix_range (полезно, например, для автозаполнения) и стирание префиксов через erase_prefix .longest_prefix .serialize/deserialize в API).max_load_factor . Более низкий максимальный коэффициент загрузки увеличит скорость, более высокий уменьшит использование памяти. Его значение по умолчанию установлено на 8.0.burst_threshold .KeySizeT .Гарантии потокобезопасности и исключений аналогичны контейнерам STL.
Хэш-функция по умолчанию, используемая структурой, зависит от наличия std::string_view . Если он доступен, используется std::hash<std::string_view> , в противном случае используется простая хеш-функция FNV-1a, чтобы избежать каких-либо зависимостей.
Если вы не можете использовать C++17 или более позднюю версию, мы рекомендуем заменить хэш-функцию чем-то вроде CityHash, MurmurHash, FarmHash,... для повышения производительности. В проведенных нами тестах CityHash64 обеспечивает улучшение чтения примерно на 20% по сравнению с 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; std::hash<std::string> не может использоваться эффективно, поскольку структура не хранит какой-либо объект std::string . Каждый раз, когда понадобится хеш, необходимо будет создать временный std::string .
Бенчмарк заключается во вставке всех заголовков из основного пространства имен архива Википедии в структуру данных, проверке использованного пространства памяти после вставки (включая возможную фрагментацию памяти) и повторном поиске всех заголовков в структуре данных. Пиковое использование памяти во время процесса вставки также измеряется по времени (1).
Каждый заголовок связан с целым числом (32 бита). Все структуры на основе хэша используют CityHash64 в качестве хэш-функции. Для тестов, помеченных резервом , функция reserve вызывается заранее, чтобы избежать перефразирования.
Обратите внимание, что tsl::hopscotch_map , std::unordered_map , google::dense_hash_map и spp::sparse_hash_map используют std::string в качестве ключа, который устанавливает минимальный размер 32 байта (на x64), даже если длина ключа составляет всего один символ. Другие структуры могут хранить односимвольные ключи размером 1 байт + 8 байт для указателя (на x64).
Тест был скомпилирован с помощью GCC 6.3 и запускался на Debian Stretch x64 с процессором Intel i5-5200u и 8 ГБ оперативной памяти. Был взят лучший из 20 заездов.
Код теста можно найти на Gist.
Набор данных enwiki-20170320-all-titles-in-ns0.gz отсортирован в алфавитном порядке. Для этого теста мы сначала перетасовываем набор данных с помощью shuf(1), чтобы избежать смещения отсортированного набора данных.
| Библиотека | Структура данных | Пиковая память (МиБ) | Память (МиБ) | Вставка (нс/ключ) | Чтение (нс/ключ) |
|---|---|---|---|---|---|
| тсл::htrie_map | HAT-трие | 405,22 | 402,25 | 643,10 | 250,87 |
| тсл::htrie_map max_load_factor=4 | HAT-трие | 471,85 | 468,50 | 638,66 | 212,90 |
| тсл::htrie_map max_load_factor=2 | HAT-трие | 569,76 | 566,52 | 630,61 | 201.10 |
| тсл::htrie_map max_load_factor=1 | HAT-трие | 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 (К) | HAT-трие | 504.07 | 501,50 | 917,49 | 261.00 |
| qp три (С) | QP-трие | 941,23 | 938,17 | 1349,25 | 1281,46 |
| крит-битное дерево (C) | Критическая попытка | 1074,96 | 1071,98 | 2930.42 | 2869,74 |
| ДжудиСЛ (К) | Массив Джуди | 631,09 | 628,37 | 884,29 | 803,58 |
| ДжудиХС (К) | Массив Джуди | 723,44 | 719,47 | 476,79 | 417,15 |
| тсл::array_map | Хэш-таблица массива | 823,54 | 678,73 | 603,94 | 138,24 |
| тсл::array_map с запасом | Хэш-таблица массива | 564,26 | 555,91 | 249,52 | 128,28 |
| tsl::hopscotch_map | Хэш-таблица | 1325,83 | 1077,99 | 368,26 | 119,49 |
| tsl::hopscotch_map с запасом | Хэш-таблица | 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::unordered_map | Хэш-таблица | 1249.05 | 1246,60 | 590,88 | 173,58 |
| std::unordered_map с запасом | Хэш-таблица | 1212,23 | 1209,71 | 350,33 | 178,70 |
Ключ вставляется и читается в алфавитном порядке.
| Библиотека | Структура данных | Пиковая память (МиБ) | Память (МиБ) | Вставка (нс/ключ) | Чтение (нс/ключ) |
|---|---|---|---|---|---|
| тсл::htrie_map | HAT-трие | 396,10 | 393,22 | 255,76 | 68.08 |
| тсл::htrie_map max_load_factor=4 | HAT-трие | 465.02 | 461,80 | 248,88 | 59,23 |
| тсл::htrie_map max_load_factor=2 | HAT-трие | 543,99 | 541,21 | 230,13 | 53,50 |
| тсл::htrie_map max_load_factor=1 | HAT-трие | 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 (К) | HAT-трие | 521,25 | 518,52 | 503.01 | 86.40 |
| qp три (С) | QP-трие | 940,65 | 937,66 | 392,86 | 190,19 |
| крит-битное дерево (C) | Критическая попытка | 1074,87 | 1071,98 | 430.04 | 347,60 |
| ДжудиСЛ (К) | Массив Джуди | 616,95 | 614,27 | 279.07 | 114,47 |
| ДжудиХС (К) | Массив Джуди | 722,29 | 719,47 | 439,66 | 372,25 |
| тсл::array_map | Хэш-таблица массива | 826,98 | 682,99 | 612,31 | 139,16 |
| тсл::array_map с запасом | Хэш-таблица массива | 565,37 | 555,35 | 246,55 | 126,32 |
| tsl::hopscotch_map | Хэш-таблица | 1331,87 | 1078.02 | 375,19 | 118.08 |
| tsl::hopscotch_map с запасом | Хэш-таблица | 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::unordered_map | Хэш-таблица | 1249,09 | 1246,65 | 594,85 | 173,54 |
| std::unordered_map с запасом | Хэш-таблица | 1212,21 | 1209,71 | 347,40 | 176,49 |
Тест заключается во вставке всех слов из набора данных «Distinct Strings» доктора Аскитиса в структуру данных, проверке используемого пространства памяти и поиске всех слов из набора данных «Skew String Set 1» (где строка может быть присутствовать несколько раз) в структуре данных. Обратите внимание, что строки в этом наборе данных имеют довольно короткую среднюю и медианную длину ключа (что может быть нереалистичным вариантом использования по сравнению с набором данных Википедии, использованным выше). Он похож на тот, что на домашней странице кедра.
Протокол тестирования тот же, что и для набора данных Википедии.
| Библиотека | Структура данных | Пиковая память (МиБ) | Память (МиБ) | Вставка (нс/ключ) | Чтение (нс/ключ) |
|---|---|---|---|---|---|
| тсл::htrie_map | HAT-трие | 604,76 | 601,79 | 485,45 | 77,80 |
| тсл::htrie_map max_load_factor=4 | HAT-трие | 768,10 | 764,98 | 491,78 | 75,48 |
| тсл::htrie_map max_load_factor=2 | HAT-трие | 1002,42 | 999,34 | 496,78 | 72,53 |
| тсл::htrie_map max_load_factor=1 | HAT-трие | 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 (К) | HAT-трие | 786,93 | 784,32 | 743,34 | 93,58 |
| qp три (С) | QP-трие | 1800.02 | 1797,21 | 987,95 | 428,51 |
| крит-битное дерево (C) | Критическая попытка | 2210.52 | 2207,64 | 1986.19 | 1109,88 |
| ДжудиСЛ (К) | Массив Джуди | 1025,59 | 1023,11 | 535.02 | 202,36 |
| ДжудиХС (К) | Массив Джуди | 1002,50 | 999,97 | 456,09 | 148,36 |
| тсл::array_map | Хэш-таблица массива | 1308.08 | 1031,67 | 545,82 | 46,41 |
| тсл::array_map с запасом | Хэш-таблица массива | 979,44 | 921,363 | 244,19 | 45,74 |
| tsl::hopscotch_map | Хэш-таблица | 2336,39 | 1611,54 | 288,70 | 47.05 |
| tsl::hopscotch_map с запасом | Хэш-таблица | 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::unordered_map | Хэш-таблица | 2112,66 | 2110.19 | 554.02 | 105.05 |
| std::unordered_map с запасом | Хэш-таблица | 2053,95 | 2051,67 | 309.06 | 109,89 |
Чтобы использовать библиотеку, просто добавьте каталог включения в свой путь включения. Это библиотека только для заголовков .
Если вы используете CMake, вы также можете использовать экспортированную цель tsl::hat_trie из CMakeLists.txt с помощью 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) Код должен работать с любым компилятором, соответствующим стандарту 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_tests API можно найти здесь. Если 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 используется с потоком сжатия Boost zlib, чтобы уменьшить размер результирующего сериализованного файла.
# 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.
