Trie is the library that implements the trie.
Trie is a generic data structure, written Trie<T, U> where T is node key type and U is a
value type.
Trie may be faster than other data structures in some cases.
For example, Trie may be used as a replacement for std::HashMap in case of a dictionary where
the number of words in dictionary is significantly less than number of different words in the
input and matching probability is low.
```rust use gtrie::Trie;
let mut t = Trie::new();
t.insert("this".chars(), 1); t.insert("trie".chars(), 2); t.insert("contains".chars(), 3); t.insert("a".chars(), 4); t.insert("number".chars(), 5); t.insert("of".chars(), 6); t.insert("words".chars(), 7);
asserteq!(t.containskey("number".chars()), true); asserteq!(t.containskey("notexistingkey".chars()), false); asserteq!(t.getvalue("words".chars()), Some(7)); asserteq!(t.getvalue("none".chars()), None); ```
Benchmark std::HashMap<String, String> vs gtrie::Trie shows that Trie is
significantly faster in the case of key mismatch but significantly slower in the case of
matching key.
$ cargo bench
test hash_map_massive_match ... bench: 150,127 ns/iter (+/- 12,986)
test hash_map_massive_mismatch_on_0 ... bench: 93,246 ns/iter (+/- 5,108)
test hash_map_massive_mismatch_on_0_one_symbol_key ... bench: 93,706 ns/iter (+/- 5,908)
test hash_map_match ... bench: 24 ns/iter (+/- 3)
test hash_map_mismatch ... bench: 20 ns/iter (+/- 0)
test trie_massive_match ... bench: 231,343 ns/iter (+/- 4,940)
test trie_massive_mismatch_on_0 ... bench: 28,743 ns/iter (+/- 8,401)
test trie_massive_mismatch_on_1 ... bench: 28,734 ns/iter (+/- 1,839)
test trie_massive_mismatch_on_2 ... bench: 28,760 ns/iter (+/- 2,582)
test trie_massive_mismatch_on_3 ... bench: 28,829 ns/iter (+/- 2,504)
test trie_match ... bench: 10 ns/iter (+/- 1)
test trie_mismatch ... bench: 5 ns/iter (+/- 0)
Search performance is highly dependent on the data stored in Trie and may be
as significantly faster than std::HashMap as significantly slower.
Source code and issues are hosted on GitHub:
https://github.com/aserebryakov/trie-rs
std::HashMapstd::HashMap