-
Notifications
You must be signed in to change notification settings - Fork 4
Overview
jpountz edited this page Mar 5, 2011
·
1 revision
This table summarizes the complexity of every operation depending on the implementation:
- k is the length of a word,
- m is the maximum number of children for a single node,
- n is the number of nodes.
- r is the number of nodes of the equivalent [radix trie|http://en.wikipedia.org/wiki/Radix_tree].
| Storage | Lookup | |
|---|---|---|
| CompactArrayTrie | two int[], one char[] and one Object[] of size n | O(k*m) |
| FastArrayTrie | one int[], one char[], one Object[] of size n and one int[][] of size is ~ n*(m+1) | O(k) |
| CompactArrayRadixTrie | two int[] and one Object[] of size r and one char[][] of size n | O(k*m) |
In spite of the better complexity of FastArrayTrie, CompactArrayTrie is much more CPU-friendly.
- CompactArrayTrie is the fastest implementation for thin tries,
- FastArrayTrie is the fastest implementation for thick tries,
- CompactArrayRadixTrie is the most memory-efficient implementation for non-trivial dictionaries, but is less CPU-friendly than CompactArrayTrie.
- BloomFilteredTrie is a trie which wraps another trie as well as a bloom filter for lookups. This can be useful if you expect most of the keys you are looking up not to be present in the trie.
- CompositeTrie is a trie which uses one trie implementation for the first n levels on the trie and another implementation for the deeper nodes. This can be useful if the nodes of the first levels of your trie have much more children than deeper nodes.