xfast

Documentation

Overview

Package xfast provides access to a sorted tree that treats integers as if they were words of m bits, where m can be 8, 16, 32, or 64. The advantage to storing integers as a trie of words is that operations can be performed in constant time depending on the size of the universe and not on the number of items in the trie.

The time complexity is as follows: Space: O(n log M) Insert: O(log M) Delete: O(log M) Search: O(log log M) Get: O(1)

where n is the number of items in the trie and M is the size of the universe, ie, 2^63-1 for 64 bit ints.

As you can see, for 64 bit ints, inserts and deletes can be performed in O(64), constant time which provides very predictable behavior in the best case.

A get by key can be performed in O(1) time and searches can be performed in O(6) time for 64 bit integers.

While x-tries have relatively slow insert, deletions, and consume a large amount of space, they form the top half of a y-fast trie which can insert and delete in O(log log M) time and consumes O(n) space.

Index

• type Entries
• type Entry
• type Iterator
  • func (iter *Iterator) Next() bool
  • func (iter *Iterator) Value() Entry
• type XFastTrie
  • func New(ifc interface{}) *XFastTrie
  • func (xft *XFastTrie) Delete(keys ...uint64)
  • func (xft *XFastTrie) Exists(key uint64) bool
  • func (xft *XFastTrie) Get(key uint64) Entry
  • func (xft *XFastTrie) Insert(entries ...Entry)
  • func (xft *XFastTrie) Iter(key uint64) *Iterator
  • func (xft *XFastTrie) Len() uint64
  • func (xft *XFastTrie) Max() Entry
  • func (xft *XFastTrie) Min() Entry
  • func (xft *XFastTrie) Predecessor(key uint64) Entry
  • func (xft *XFastTrie) Successor(key uint64) Entry

Types

type Entries

type Entries []Entry

Entries is a typed list of Entry interfaces.

type Entry

type Entry interface {
	// Key is the key for this entry.  If the trie has been
	// given bit size n, only the last n bits of this key
	// will matter.  Use a bit size of 64 to enable all
	// 2^64-1 keys.
	Key() uint64
}

Entry defines items that can be inserted into the x-fast trie.

type Iterator

type Iterator struct {
	// contains filtered or unexported fields
}

Iterator will iterate of the results of a query.

func (*Iterator) Next

func (iter *Iterator) Next() bool

Next will return a bool indicating if another value exists in the iterator.

func (*Iterator) Value

func (iter *Iterator) Value() Entry

Value will return the Entry representing the iterator's current position. If no Entry exists at the present condition, the iterator is exhausted and this method will return nil.

type XFastTrie

type XFastTrie struct {
	// contains filtered or unexported fields
}

XFastTrie is a datastructure for storing integers in a known universe, where universe size is determined by the bit size of the desired keys. This structure should be faster than binary search tries for very large datasets and slower for smaller datasets.

func New

func New(ifc interface{}) *XFastTrie

New will construct a new X-Fast Trie with the given "size," that is the size of the universe of the trie. This expects a uint of some sort, ie, uint8, uint16, etc. The size of the universe will be 2^n-1 and will affect the speed of all operations. IFC MUST be a uint type.

func (*XFastTrie) Delete

func (xft *XFastTrie) Delete(keys ...uint64)

Delete will delete the provided keys from the trie. If an entry associated with a provided key cannot be found, that deletion is a no-op. Each deletion is an O(log M) operation.

func (*XFastTrie) Exists

func (xft *XFastTrie) Exists(key uint64) bool

Exists returns a bool indicating if the provided key exists in the trie. This is an O(1) operation.

func (*XFastTrie) Get

func (xft *XFastTrie) Get(key uint64) Entry

Get will return a value in the trie associated with the provided key if it exists. Returns nil if the key does not exist. This is expected to take O(1) time.

func (*XFastTrie) Insert

func (xft *XFastTrie) Insert(entries ...Entry)

Insert will insert the provided entries into the trie. Any entry with an existing key will cause an overwrite. This is an O(log M) operation, for each entry.

func (*XFastTrie) Iter

func (xft *XFastTrie) Iter(key uint64) *Iterator

Iter will return an iterator that will iterate over all values equal to or immediately greater than the provided key. Iterator will iterate successor relationships.

func (*XFastTrie) Len

func (xft *XFastTrie) Len() uint64

Len returns the number of items in this trie. This is an O(1) operation.

func (*XFastTrie) Max

func (xft *XFastTrie) Max() Entry

Max will return the highest keyed value in the trie. This is an O(1) operation.

func (*XFastTrie) Min

func (xft *XFastTrie) Min() Entry

Min will return the lowest keyed value in the trie. This is an O(1) operation.

func (*XFastTrie) Predecessor

func (xft *XFastTrie) Predecessor(key uint64) Entry

Predecessor will return an Entry which matches the provided key or its immediate predecessor. Will return nil if a predecessor does not exist. This is an O(log log M) operation.

func (*XFastTrie) Successor

func (xft *XFastTrie) Successor(key uint64) Entry

Successor will return an Entry which matches the provided key or its immediate successor. Will return nil if a successor does not exist. This is an O(log log M) operation.