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
faster in the case of key mismatch but significantly slower in the case of
matching key.
$ cargo bench
test hash_map_massive_match ... bench: 157,555 ns/iter (+/- 15,801)
test hash_map_massive_mismatch_on_0 ... bench: 95,770 ns/iter (+/- 5,632)
test hash_map_massive_mismatch_on_0_one_symbol_key ... bench: 97,157 ns/iter (+/- 5,428)
test hash_map_match ... bench: 24 ns/iter (+/- 1)
test hash_map_mismatch ... bench: 21 ns/iter (+/- 1)
test trie_massive_match ... bench: 332,543 ns/iter (+/- 15,031)
test trie_massive_mismatch_on_0 ... bench: 54,408 ns/iter (+/- 4,148)
test trie_massive_mismatch_on_1 ... bench: 54,255 ns/iter (+/- 4,052)
test trie_massive_mismatch_on_2 ... bench: 53,679 ns/iter (+/- 4,907)
test trie_massive_mismatch_on_3 ... bench: 54,131 ns/iter (+/- 3,305)
test trie_match ... bench: 42 ns/iter (+/- 2)
test trie_mismatch ... bench: 17 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