hat trie
v0.6.0
Implementasi Trie berdasarkan "HAT-trie: Struktur Data Berbasis Trie yang Sadar Cache untuk String." (Askitis Nikolas dan Sinha Ranjan, 2007) makalah. Untuk saat ini, hanya HAT-trie murni yang telah diterapkan, versi hybrid mungkin akan hadir nanti. Detail mengenai struktur data HAT-trie dapat ditemukan di sini.
Pustaka menyediakan cara yang efisien dan ringkas untuk menyimpan kumpulan atau peta string dengan mengompresi awalan umum. Hal ini juga memungkinkan untuk mencari kunci yang cocok dengan awalan. Perhatikan bahwa parameter default struktur diarahkan untuk mengoptimalkan pencarian yang tepat, jika Anda melakukan banyak pencarian awalan, Anda mungkin ingin mengurangi ambang batas burst melalui metode burst_threshold .
Ini adalah struktur yang disesuaikan dengan baik untuk menyimpan string dalam jumlah besar.
Untuk bagian hash array, proyek array-hash digunakan dan disertakan dalam repositori.
Perpustakaan menyediakan dua kelas: tsl::htrie_map dan tsl::htrie_set .
tsl::hat_trie dari CMakeLists.txt.equal_prefix_range (berguna untuk pelengkapan otomatis misalnya) dan penghapusan awalan melalui erase_prefix .longest_prefix .serialize/deserialize di API untuk detailnya).max_load_factor . Faktor beban maksimal yang lebih rendah akan meningkatkan kecepatan, sedangkan faktor beban yang lebih tinggi akan mengurangi penggunaan memori. Nilai defaultnya diatur ke 8.0.burst_threshold .KeySizeT .Jaminan keamanan thread dan pengecualian serupa dengan wadah STL.
Fungsi hash default yang digunakan oleh struktur bergantung pada keberadaan std::string_view . Jika tersedia, std::hash<std::string_view> digunakan, jika tidak, fungsi hash FNV-1a sederhana digunakan untuk menghindari ketergantungan apa pun.
Jika Anda tidak dapat menggunakan C++17 atau lebih baru, kami menyarankan untuk mengganti fungsi hash dengan sesuatu seperti CityHash, MurmurHash, FarmHash, ... untuk performa yang lebih baik. Pada pengujian yang kami lakukan, CityHash64 menawarkan peningkatan ~20% pada pembacaan dibandingkan dengan 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> tidak dapat digunakan secara efisien karena strukturnya tidak menyimpan objek std::string apa pun. Kapan pun hash diperlukan, std::string sementara harus dibuat.
Tolok ukurnya terdiri dari memasukkan semua judul dari ruang nama utama arsip Wikipedia ke dalam struktur data, memeriksa ruang memori yang digunakan setelah penyisipan (termasuk potensi fragmentasi memori) dan mencari kembali semua judul dalam struktur data. Penggunaan memori puncak selama proses penyisipan juga diukur dengan waktu (1).
Setiap judul dikaitkan dengan int (32 bit). Semua struktur berbasis hash menggunakan CityHash64 sebagai fungsi hash. Untuk pengujian yang ditandai dengan cadangan , fungsi reserve dipanggil terlebih dahulu untuk menghindari pengulangan apa pun.
Perhatikan bahwa tsl::hopscotch_map , std::unordered_map , google::dense_hash_map dan spp::sparse_hash_map menggunakan std::string sebagai kunci yang menerapkan ukuran minimum 32 byte (pada x64) meskipun panjang kunci hanya satu karakter. Struktur lain mungkin dapat menyimpan kunci satu karakter dengan 1 byte + 8 byte untuk sebuah pointer (pada x64).
Benchmark ini dikompilasi dengan GCC 6.3 dan dijalankan pada Debian Stretch x64 dengan Intel i5-5200u dan RAM 8Go. 20 run terbaik telah dilakukan.
Kode benchmark dapat ditemukan di Gist.
Kumpulan data enwiki-20170320-all-titles-in-ns0.gz diurutkan berdasarkan abjad. Untuk tolok ukur ini, pertama-tama kita mengacak kumpulan data melalui shuf(1) untuk menghindari kumpulan data yang diurutkan secara bias.
| Perpustakaan | Struktur data | Memori puncak (MiB) | Memori (MiB) | Sisipkan (ns/kunci) | Baca (ns/kunci) |
|---|---|---|---|---|---|
| tsl::htrie_map | TOPI-coba | 405.22 | 402.25 | 643.10 | 250,87 |
| tsl::htrie_map faktor_beban_maks=4 | TOPI-coba | 471,85 | 468.50 | 638.66 | 212.90 |
| tsl::htrie_map faktor_beban_maks=2 | TOPI-coba | 569.76 | 566.52 | 630.61 | 201.10 |
| tsl::htrie_map faktor_beban_maks=1 | TOPI-coba | 713.44 | 709.81 | 645.76 | 190,87 |
| pohon cedar::da | Percobaan array ganda | 1269.68 | 1254.41 | 1102.93 | 557.20 |
| cedar::da ORDERED=false | Percobaan array ganda | 1269.80 | 1254.41 | 1089.78 | 570.13 |
| pohon cedar::da | Percobaan tereduksi array ganda | 1183.07 | 1167.79 | 1076.68 | 645.79 |
| cedar::da ORDERED=false | Percobaan tereduksi array ganda | 1183.14 | 1167.85 | 1065.43 | 641,98 |
| pohon cedar::da | Awalan array ganda dicoba | 498.69 | 496.54 | 1096,90 | 628.01 |
| cedar::da ORDERED=false | Awalan array ganda dicoba | 498.65 | 496.60 | 1048.40 | 628.94 |
| topi-coba 1 (C) | TOPI-coba | 504.07 | 501.50 | 917.49 | 261.00 |
| qp mencoba (C) | QP mencoba | 941.23 | 938.17 | 1349.25 | 1281.46 |
| percobaan bit kritis (C) | Coba sedikit kritis | 1074.96 | 1071,98 | 2930.42 | 2869.74 |
| JudySL (C) | susunan Judy | 631.09 | 628.37 | 884.29 | 803.58 |
| JudyHS (C) | susunan Judy | 723.44 | 719.47 | 476,79 | 417.15 |
| tsl::array_map | Tabel hash array | 823.54 | 678.73 | 603.94 | 138.24 |
| tsl::array_map dengan cadangan | Tabel hash array | 564.26 | 555.91 | 249.52 | 128.28 |
| tsl::hopscotch_map | Tabel hash | 1325.83 | 1077,99 | 368.26 | 119.49 |
| tsl::hopscotch_map dengan cadangan | Tabel hash | 1080.51 | 1077,98 | 240,58 | 119.91 |
| google::dense_hash_map | Tabel hash | 2319.40 | 1677.11 | 466.60 | 138.87 |
| google::dense_hash_map dengan cadangan | Tabel hash | 1592.51 | 1589,99 | 259.56 | 120.40 |
| spp::sparse_hash_map | Tabel hash jarang | 918.67 | 917.10 | 769.00 | 175.59 |
| spp::sparse_hash_map dengan cadangan | Tabel hash jarang | 913.35 | 910.65 | 427.22 | 159.08 |
| std::unordered_map | Tabel hash | 1249.05 | 1246.60 | 590,88 | 173,58 |
| std::unordered_map dengan cadangan | Tabel hash | 1212.23 | 1209.71 | 350.33 | 178,70 |
Kuncinya dimasukkan dan dibaca sesuai abjad.
| Perpustakaan | Struktur data | Memori puncak (MiB) | Memori (MiB) | Sisipkan (ns/kunci) | Baca (ns/kunci) |
|---|---|---|---|---|---|
| tsl::htrie_map | TOPI-coba | 396.10 | 393.22 | 255.76 | 68.08 |
| tsl::htrie_map faktor_beban_maks=4 | TOPI-coba | 465.02 | 461.80 | 248.88 | 59.23 |
| tsl::htrie_map faktor_beban_maks=2 | TOPI-coba | 543,99 | 541.21 | 230.13 | 53.50 |
| tsl::htrie_map faktor_beban_maks=1 | TOPI-coba | 692.29 | 689,70 | 243.84 | 49.22 |
| pohon cedar::da | Percobaan array ganda | 1269.58 | 1254.41 | 278.51 | 54.72 |
| cedar::da ORDERED=false | Percobaan array ganda | 1269.66 | 1254.41 | 264.43 | 56.02 |
| pohon cedar::da | Percobaan tereduksi array ganda | 1183.01 | 1167.78 | 254.60 | 69.18 |
| cedar::da ORDERED=false | Percobaan tereduksi array ganda | 1183.03 | 1167.78 | 241.45 | 69.67 |
| pohon cedar::da | Awalan array ganda dicoba | 621.59 | 619.38 | 246.88 | 57.83 |
| cedar::da ORDERED=false | Awalan array ganda dicoba | 621.59 | 619.38 | 187,98 | 58.56 |
| topi-trie 2 (C) | TOPI-coba | 521.25 | 518.52 | 503.01 | 86.40 |
| qp mencoba (C) | QP mencoba | 940,65 | 937.66 | 392.86 | 190.19 |
| percobaan bit kritis (C) | Coba sedikit kritis | 1074.87 | 1071,98 | 430.04 | 347.60 |
| JudySL (C) | susunan Judy | 616,95 | 614.27 | 279.07 | 114.47 |
| JudyHS (C) | susunan Judy | 722.29 | 719.47 | 439.66 | 372.25 |
| tsl::array_map | Tabel hash array | 826.98 | 682,99 | 612.31 | 139.16 |
| tsl::array_map dengan cadangan | Tabel hash array | 565.37 | 555.35 | 246.55 | 126.32 |
| tsl::hopscotch_map | Tabel hash | 1331.87 | 1078.02 | 375.19 | 118.08 |
| tsl::hopscotch_map dengan cadangan | Tabel hash | 1080.51 | 1077,97 | 238.93 | 117.20 |
| google::dense_hash_map | Tabel hash | 2325.27 | 1683.07 | 483,95 | 137.09 |
| google::dense_hash_map dengan cadangan | Tabel hash | 1592.54 | 1589,99 | 257.22 | 113.71 |
| spp::sparse_hash_map | Tabel hash jarang | 920,96 | 918.70 | 772.03 | 176.64 |
| spp::sparse_hash_map dengan cadangan | Tabel hash jarang | 914.84 | 912.47 | 422,85 | 158.73 |
| std::unordered_map | Tabel hash | 1249.09 | 1246.65 | 594,85 | 173,54 |
| std::unordered_map dengan cadangan | Tabel hash | 1212.21 | 1209.71 | 347.40 | 176.49 |
Tolok ukurnya terdiri dari memasukkan semua kata dari kumpulan data "String Berbeda" dari Dr. Askitis ke dalam struktur data, memeriksa ruang memori yang digunakan dan mencari semua kata dari kumpulan data "Skew String Set 1" (di mana sebuah string dapat berada hadir beberapa kali) dalam struktur data. Perhatikan bahwa string dalam kumpulan data ini memiliki rata-rata dan panjang kunci median yang cukup pendek (yang mungkin bukan kasus penggunaan yang realistis dibandingkan dengan kumpulan data Wikipedia yang digunakan di atas). Ini mirip dengan yang ada di beranda cedar.
Protokol benchmarknya sama dengan kumpulan data Wikipedia.
| Perpustakaan | Struktur data | Memori puncak (MiB) | Memori (MiB) | Sisipkan (ns/kunci) | Baca (ns/kunci) |
|---|---|---|---|---|---|
| tsl::htrie_map | TOPI-coba | 604.76 | 601.79 | 485.45 | 77,80 |
| tsl::htrie_map faktor_beban_maks=4 | TOPI-coba | 768.10 | 764.98 | 491.78 | 75.48 |
| tsl::htrie_map faktor_beban_maks=2 | TOPI-coba | 1002.42 | 999.34 | 496,78 | 72.53 |
| tsl::htrie_map faktor_beban_maks=1 | TOPI-coba | 1344.98 | 1341.97 | 520.66 | 72.45 |
| pohon cedar::da | Percobaan array ganda | 1105.45 | 1100,05 | 682.25 | 71,98 |
| cedar::da ORDERED=false | Percobaan array ganda | 1105.47 | 1100,05 | 668,75 | 71,95 |
| pohon cedar::da | Percobaan tereduksi array ganda | 941.16 | 926.04 | 684.38 | 79.11 |
| cedar::da ORDERED=false | Percobaan tereduksi array ganda | 941.16 | 925,98 | 672.14 | 79.02 |
| pohon cedar::da | Awalan array ganda dicoba | 714.58 | 712.59 | 831.71 | 75.83 |
| cedar::da ORDERED=false | Awalan array ganda dicoba | 714.66 | 712.31 | 786.93 | 75,89 |
| topi-coba 3 (C) | TOPI-coba | 786.93 | 784.32 | 743.34 | 93,58 |
| qp mencoba (C) | QP mencoba | 1800.02 | 1797.21 | 987,95 | 428.51 |
| percobaan bit kritis (C) | Coba sedikit kritis | 2210.52 | 2207.64 | 1986.19 | 1109.88 |
| JudySL (C) | susunan Judy | 1025.59 | 1023.11 | 535.02 | 202.36 |
| JudyHS (C) | susunan Judy | 1002,50 | 999,97 | 456.09 | 148.36 |
| tsl::array_map | Tabel hash array | 1308.08 | 1031.67 | 545.82 | 46.41 |
| tsl::array_map dengan cadangan | Tabel hash array | 979.44 | 921.363 | 244.19 | 45.74 |
| tsl::hopscotch_map | Tabel hash | 2336.39 | 1611.54 | 288.70 | 47.05 |
| tsl::hopscotch_map dengan cadangan | Tabel hash | 1614.22 | 1611.64 | 220.67 | 46.39 |
| google::dense_hash_map | Tabel hash | 3913.64 | 2636.31 | 317.66 | 43.62 |
| google::dense_hash_map dengan cadangan | Tabel hash | 2638.19 | 2635.68 | 227.58 | 43.09 |
| spp::sparse_hash_map | Tabel hash jarang | 1419.69 | 1417.61 | 586.26 | 56.00 |
| spp::sparse_hash_map dengan cadangan | Tabel hash jarang | 1424.21 | 1421.69 | 392.76 | 55.73 |
| std::unordered_map | Tabel hash | 2112.66 | 2110.19 | 554.02 | 105.05 |
| std::unordered_map dengan cadangan | Tabel hash | 2053.95 | 2051.67 | 309.06 | 109,89 |
Untuk menggunakan perpustakaan, cukup tambahkan direktori penyertaan ke jalur penyertaan Anda. Ini adalah perpustakaan khusus header .
Jika Anda menggunakan CMake, Anda juga dapat menggunakan target yang diekspor tsl::hat_trie dari CMakeLists.txt dengan 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) Kode ini harus bekerja dengan kompiler yang memenuhi standar C++11 dan telah diuji dengan GCC 4.8.4, Clang 3.5.0, dan Visual Studio 2015.
Untuk menjalankan pengujian, Anda memerlukan pustaka Boost Test dan 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 dapat ditemukan di sini. Jika std::string_view tersedia, API sedikit berubah dan dapat ditemukan di sini.
# 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;
}
} Pustaka menyediakan cara yang efisien untuk membuat serialisasi dan deserialisasi peta atau kumpulan sehingga dapat disimpan ke file atau dikirim melalui jaringan. Untuk melakukannya, pengguna harus menyediakan objek fungsi untuk serialisasi dan deserialisasi.
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);
};Perhatikan bahwa implementasinya meninggalkan kompatibilitas biner (endianness, representasi biner float, ukuran int, ...) dari tipe yang diserialkan/deserialisasi di tangan objek fungsi yang disediakan jika kompatibilitas diperlukan.
Detail lebih lanjut mengenai metode serialize dan deserialize dapat ditemukan di 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);
}
}Dimungkinkan untuk menggunakan perpustakaan serialisasi untuk menghindari beberapa boilerplate jika tipe yang akan diserialkan lebih kompleks.
Contoh berikut menggunakan Boost Serialization dengan aliran kompresi Boost zlib untuk mengurangi ukuran file serial yang dihasilkan.
# 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);
}
}Kode ini dilisensikan di bawah lisensi MIT, lihat file LISENSI untuk detailnya.
