Package yfast implements a y-fast trie. Instead of a red-black BBST for the leaves, this implementation uses a simple ordered list. This package should have searches that are as performant as the x-fast trie while having faster inserts/deletes and linear space consumption.
Performance characteristics: Space: O(n) Get: O(log log M) Search: O(log log M) Insert: O(log log M) Delete: O(log log M)
where n is the number of items in the trie and M is the size of the universe, ie, 2^m where m is the number of bits in the specified key size.
This particular implementation also uses fixed bucket sizes as this should aid in multithreading these functions for performance optimization.
*/ package yfast import "sort"
*/ package yfast import (
*/ package yfast // Entry defines items that can be inserted into the y-fast
yfast is referenced in 4 repositoriesgithub.com/Workiva/go-datastructures
- 1 reference in trie/yfast/entries.go
- 1 reference in trie/yfast/entries_test.go
- 1 reference in trie/yfast/interface.go
- 1 reference in trie/yfast/iterator.go
- 1 reference in trie/yfast/mock_test.go
- 3 references in clientutil/filereader.go
- 3 references in ext/filetree/reader/filereader/filereader.go