skip

Documentation

Overview

Package skip defines a skiplist datastructure. That is, a data structure that probabilistically determines relationships between keys. By doing so, it becomes easier to program than a binary search tree but maintains similar speeds.

Performance characteristics: Insert: O(log n) Search: O(log n) Delete: O(log n) Space: O(n)

Recently added is the capability to address, insert, and replace an entry by position. This capability is acheived by saving the width of the "gap" between two nodes. Searching for an item by position is very similar to searching by value in that the same basic algorithm is used but we are searching for width instead of value. Because this avoids the overhead associated with Golang interfaces, operations by position are about twice as fast as operations by value. Time complexities listed below.

SearchByPosition: O(log n) InsertByPosition: O(log n)

More information here: http://cglab.ca/~morin/teaching/5408/refs/p90b.pdf

Benchmarks: BenchmarkInsert-8 2000000 930 ns/op BenchmarkGet-8 2000000 989 ns/op BenchmarkDelete-8 3000000 600 ns/op BenchmarkPrepend-8 1000000 1468 ns/op BenchmarkByPosition-8 10000000 202 ns/op BenchmarkInsertAtPosition-8 3000000 485 ns/op

CPU profiling has shown that the most expensive thing we do here is call Compare. A potential optimization for gets only is to do a binary search in the forward/width lists instead of visiting every value. We could also use generics if Golang had them and let the consumer specify primitive types, which would speed up these operation dramatically.

Index

• type Comparator
• type Comparators
• type Iterator
• type SkipList
  • func New(ifc interface{}) *SkipList
  • func (sl *SkipList) ByPosition(position uint64) Comparator
  • func (sl *SkipList) Delete(comparators ...Comparator) Comparators
  • func (sl *SkipList) Get(comparators ...Comparator) Comparators
  • func (sl *SkipList) GetWithPosition(cmp Comparator) (Comparator, uint64)
  • func (sl *SkipList) Insert(comparators ...Comparator) Comparators
  • func (sl *SkipList) InsertAtPosition(position uint64, cmp Comparator)
  • func (sl *SkipList) Iter(cmp Comparator) Iterator
  • func (sl *SkipList) IterAtPosition(pos uint64) Iterator
  • func (sl *SkipList) Len() uint64
  • func (sl *SkipList) ReplaceAtPosition(position uint64, cmp Comparator)
  • func (sl *SkipList) SplitAt(index uint64) (*SkipList, *SkipList)

Types

type Comparator

type Comparator interface {
	// Compare compares this interface with another.  Returns a positive
	// number if this interface is greater, 0 if equal, negative number
	// if less.
	Compare(Comparator) int
}

Comparator is a generic interface that represents items that can be compared.

type Comparators

type Comparators []Comparator

Comparators is a typed list of type Comparator.

type Iterator

type Iterator interface {
	// Next returns a bool indicating if there is future value
	// in the iterator and moves the iterator to that value.
	Next() bool
	// Prev returns a bool indicating if there is Previous value
	// in the iterator and moves the iterator to that value.
	Prev() bool
	// Value returns a Comparator representing the iterator's current
	// position.  If there is no value, this returns nil.
	Value() Comparator
	// contains filtered or unexported methods
}

Iterator defines an interface that allows a consumer to iterate all results of a query. All values will be visited in-order.

type SkipList

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

Skip list is a datastructure that probabalistically determines relationships between nodes. This results in a structure that performs similarly to a BST but is much easier to build from a programmatic perspective (no rotations).

func New

func New(ifc interface{}) *SkipList

New will allocate, initialize, and return a new skiplist. The provided parameter should be of type uint and will determine the maximum possible level that will be created to ensure a random and quick distribution of levels. Parameter must be a uint type.

func (*SkipList) ByPosition

func (sl *SkipList) ByPosition(position uint64) Comparator

ByPosition returns the Comparator at the given position.

func (*SkipList) Delete

func (sl *SkipList) Delete(comparators ...Comparator) Comparators

Delete will remove the provided keys from the skiplist and return a list of in-order Comparators that were deleted. This is a no-op if an associated key could not be found. This is an O(log n) operation.

func (*SkipList) Get

func (sl *SkipList) Get(comparators ...Comparator) Comparators

Get will retrieve values associated with the keys provided. If an associated value could not be found, a nil is returned in its place. This is an O(log n) operation.

func (*SkipList) GetWithPosition

func (sl *SkipList) GetWithPosition(cmp Comparator) (Comparator, uint64)

GetWithPosition will retrieve the value with the provided key and return the position of that value within the list. Returns nil, 0 if an associated value could not be found.

func (*SkipList) Insert

func (sl *SkipList) Insert(comparators ...Comparator) Comparators

Insert will insert the provided comparators into the list. Returned is a list of comparators that were overwritten. This is expected to be an O(log n) operation.

func (*SkipList) InsertAtPosition

func (sl *SkipList) InsertAtPosition(position uint64, cmp Comparator)

InsertAtPosition will insert the provided Comparator at the provided position. If position is greater than the length of the skiplist, the Comparator is appended. This method bypasses order checks and checks for duplicates so use with caution.

func (*SkipList) Iter

func (sl *SkipList) Iter(cmp Comparator) Iterator

Iter will return an iterator that can be used to iterate over all the values with a key equal to or greater than the key provided.

func (*SkipList) IterAtPosition

func (sl *SkipList) IterAtPosition(pos uint64) Iterator

IterAtPosition is the sister method to Iter only the user defines a position in the skiplist to begin iteration instead of a value.

func (*SkipList) Len

func (sl *SkipList) Len() uint64

Len returns the number of items in this skiplist.

func (*SkipList) ReplaceAtPosition

func (sl *SkipList) ReplaceAtPosition(position uint64, cmp Comparator)

Replace at position will replace the Comparator at the provided position with the provided Comparator. If the provided position does not exist, this operation is a no-op.

func (*SkipList) SplitAt

func (sl *SkipList) SplitAt(index uint64) (*SkipList, *SkipList)

SplitAt will split the current skiplist into two lists. The first skiplist returned is the "left" list and the second is the "right." The index defines the last item in the left list. If index is greater then the length of this list, only the left skiplist is returned and the right will be nil. This is a mutable operation and modifies the content of this list.