README
¶
Trie
Implements:
- A trie, use it like a
map[string]interface{}. - A ternary search tree, like a
map[string]interface{}from which you cannot delete. - A trieset, use it like a
map[string]struct{}.
Performance
This benchmarks shows lookups only (Get):
| keys | map[string]bool |
trie.TernaryST |
trie.Trie |
|---|---|---|---|
| 4 | 7.36 ns/op | 24.1 ns/op | 28.4 ns/op |
| 8 | 7.37 ns/op | 24.3 ns/op | 28.3 ns/op |
| 16 | 28.6 ns/op | 33.4 ns/op | 35.0 ns/op |
| 32 | 24.6 ns/op | 33.7 ns/op | 35.3 ns/op |
| 64 | 25.1 ns/op | 33.2 ns/op | 35.2 ns/op |
| 512 | 24.4 ns/op | 38.5 ns/op | 42.0 ns/op |
| 1024 | 33.9 ns/op | 43.5 ns/op | 49.5 ns/op |
| 1M | 32.1 ns/op | 58.5 ns/op | 72.2 ns/op |
License
MIT, see ./LICENSE
Documentation
¶
Overview ¶
Package trie holds implementations of a simple trie and of a ternary search trie.
Package trie holds implementations of a simple trie and of a ternary search trie.
Index ¶
- type TernaryST
- func (t *TernaryST) Get(key string) (interface{}, bool)
- func (t *TernaryST) Keys() []string
- func (t *TernaryST) KeysMatching(key string) []string
- func (t *TernaryST) KeysWithPrefix(key string) []string
- func (t *TernaryST) Len() int
- func (t *TernaryST) LongestPrefix(key string) string
- func (t *TernaryST) Put(key string, val interface{})
- type Trie
- type TrieSet
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type TernaryST ¶
type TernaryST struct {
// contains filtered or unexported fields
}
TernaryST is a symbol table specifically for string indexed keys.
func (*TernaryST) KeysMatching ¶
KeysMatching returns all the keys that share prefix `key`, where `key` can contain a wildcard character `.`.
func (*TernaryST) KeysWithPrefix ¶
KeysWithPrefix returns all the keys starting with prefix `key`
func (*TernaryST) LongestPrefix ¶
LongestPrefix returns the longest string in this trie that has `key` for prefix
type Trie ¶
type Trie struct {
// contains filtered or unexported fields
}
Trie is a symbol table specifically for string indexed keys.
Source Files
Click to show internal directories.
Click to hide internal directories.