skiplist

README

Fast Skiplist Implementation

This Go-library implements a very fast and efficient Skiplist that can be used as direct substitute for a balanced tree or linked list. All basic operations ( Find, Insert and Delete) have approximate runtimes of O(log(n)) that prove real in benchmarks.

For detailed API documentation, see the official docs: godoc.org/github.com/MauriceGit/skiplist.

This implementation introduces a minimum amount of overhead and is tailored for maximum performance across all operations. In benchmarks, this skiplist is currently the fastest implementation in Go known to me. See a thorough benchmark of multiple skiplist implementations at: github.com/MauriceGit/skiplist-survey.

Find, Insert, Delete at both ends of the SkipList

Y-Axis is measured in nanoseconds per operation for all charts

All functions, be it Find, Insert or Delete that operate on first or last elements in the skiplist behave in near Constant time, no matter how many elements are already inserted in the skiplist.

For real-world cases where elements are inserted or removed at random positions in the skiplist, we can clearly see the approximate O(log(n)) behaviour of the implementation which approximates to a constant value around 1800ns for Delete and 2200ns for Insert.

Comparison to other Skiplist implementations

The following graphs are taken from github.com/MauriceGit/skiplist-survey. Please visit this skiplist survey for a much more detailed comparison over several benchmarks between different skiplist implementations.

Overall, this implementation is the fastest skiplist for nearly all operations. Especially for real-world applications.

If we compare random insertions of this skiplist to other implementations, it is clearly the fastest by up to 800ns per insertion for up to 3m elements.

If we compare random deletions of this skiplist to other implementations, it is clearly the fastest by up to 300ns per deletion for up to 3m elements.

Usage

import (
    "github.com/MauriceGit/skiplist"
    "fmt"
)

type Element int
// Implement the interface used in skiplist
func (e Element) ExtractKey() float64 {
    return float64(e)
}
func (e Element) String() string {
    return fmt.Sprintf("%03d", e)
}

func main() {
    list := New()

    // Insert some elements
    for i := 0; i < 100; i++ {
        list.Insert(Element(i))
    }

    // Find an element
    if e, ok := list.Find(Element(53)); ok {
        fmt.Println(e)
    }

    // Delete all elements
    for i := 0; i < 100; i++ {
        list.Delete(Element(i))
    }
}

Convenience functions

Other than the classic Find, Insert and Delete, some more convenience functions are implemented that makes this skiplist implementation very easy and straight forward to use in real applications. All complexity values are approximates, as skiplist can only approximate runtime complexity.

Function	Complexity	Description
Find	O(log(n))	Finds an element in the skiplist
FindGreaterOrEqual	O(log(n))	Finds the first element that is greater or equal the given value in the skiplist
Insert	O(log(n))	Inserts an element into the skiplist
Delete	O(log(n))	Deletes an element from the skiplist
GetSmallestNode	O(1)	Returns the smallest element in the skiplist
GetLargestNode	O(1)	Returns the largest element in the skiplist
Prev	O(1)	Given a skiplist-node, it returns the previous element (Wraps around and allows to linearly iterate the skiplist)
Next	O(1)	Given a skiplist-node, it returns the next element (Wraps around and allows to linearly iterate the skiplist)
ChangeValue	O(1)	Given a skiplist-node, the actual value can be changed, as long as the key stays the same (Example: Change a structs data)

Documentation

Overview

Package skiplist is an implementation of a skiplist to store elements in increasing order. It allows finding, insertion and deletion operations in approximately O(n log(n)). Additionally, there are methods for retrieving the next and previous element as well as changing the actual value without the need for re-insertion (as long as the key stays the same!) Skiplist is a fast alternative to a balanced tree.

Index

• type ListElement
• type SkipList
  • func New() SkipList
  • func NewEps(eps float64) SkipList
  • func NewSeed(seed int64) SkipList
  • func NewSeedEps(seed int64, eps float64) SkipList
  • func (t *SkipList) ChangeValue(e *SkipListElement, newValue ListElement) (ok bool)
  • func (t *SkipList) Delete(e ListElement)
  • func (t *SkipList) Find(e ListElement) (elem *SkipListElement, ok bool)
  • func (t *SkipList) FindGreaterOrEqual(e ListElement) (elem *SkipListElement, ok bool)
  • func (t *SkipList) GetLargestNode() *SkipListElement
  • func (t *SkipList) GetNodeCount() int
  • func (t *SkipList) GetSmallestNode() *SkipListElement
  • func (t *SkipList) Insert(e ListElement)
  • func (t *SkipList) IsEmpty() bool
  • func (t *SkipList) Next(e *SkipListElement) *SkipListElement
  • func (t *SkipList) Prev(e *SkipListElement) *SkipListElement
  • func (t *SkipList) String() string
• type SkipListElement
  • func (e *SkipListElement) GetValue() ListElement

Types

type ListElement

type ListElement interface {
	// ExtractKey() returns a float64 representation of the key that is used for insertion/deletion/find. It needs to establish an order over all elements
	ExtractKey() float64
	// A string representation of the element. Can be used for pretty-printing the list. Otherwise just return an empty string.
	String() string
}

ListElement is the interface to implement for elements that are inserted into the skiplist.

type SkipList

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

SkipList is the actual skiplist representation. It saves all nodes accessible from the start and end and keeps track of element count, eps and levels.

func New

func New() SkipList

New returns a new empty, initialized Skiplist.

func NewEps

func NewEps(eps float64) SkipList

NewEps returns a new empty, initialized Skiplist. Eps is used to compare keys given by the ExtractKey() function on equality.

func NewSeed

func NewSeed(seed int64) SkipList

NewSeed returns a new empty, initialized Skiplist. Given a seed, a deterministic height/list behaviour can be achieved.

func NewSeedEps

func NewSeedEps(seed int64, eps float64) SkipList

NewSeedEps returns a new empty, initialized Skiplist. Given a seed, a deterministic height/list behaviour can be achieved. Eps is used to compare keys given by the ExtractKey() function on equality.

func (*SkipList) ChangeValue

func (t *SkipList) ChangeValue(e *SkipListElement, newValue ListElement) (ok bool)

ChangeValue can be used to change the actual value of a node in the skiplist without the need of Deleting and reinserting the node again. Be advised, that ChangeValue only works, if the actual key from ExtractKey() will stay the same! ok is an indicator, wether the value is actually changed.

func (*SkipList) Delete

func (t *SkipList) Delete(e ListElement)

Delete removes an element equal to e from the skiplist, if there is one. If there are multiple entries with the same value, Delete will remove one of them (Which one will change based on the actual skiplist layout) Delete runs in approx. O(log(n))

func (*SkipList) Find

func (t *SkipList) Find(e ListElement) (elem *SkipListElement, ok bool)

Find tries to find an element in the skiplist based on the key from the given ListElement. elem can be used, if ok is true. Find runs in approx. O(log(n))

func (*SkipList) FindGreaterOrEqual

func (t *SkipList) FindGreaterOrEqual(e ListElement) (elem *SkipListElement, ok bool)

FindGreaterOrEqual finds the first element, that is greater or equal to the given ListElement e. The comparison is done on the keys (So on ExtractKey()). FindGreaterOrEqual runs in approx. O(log(n))

func (*SkipList) GetLargestNode

func (t *SkipList) GetLargestNode() *SkipListElement

GetLargestNode returns the very last/largest node in the skiplist. GetLargestNode runs in O(1)

func (*SkipList) GetNodeCount

func (t *SkipList) GetNodeCount() int

GetNodeCount returns the number of nodes currently in the skiplist.

func (*SkipList) GetSmallestNode

func (t *SkipList) GetSmallestNode() *SkipListElement

GetSmallestNode returns the very first/smallest node in the skiplist. GetSmallestNode runs in O(1)

func (*SkipList) Insert

func (t *SkipList) Insert(e ListElement)

Insert inserts the given ListElement into the skiplist. Insert runs in approx. O(log(n))

func (*SkipList) IsEmpty

func (t *SkipList) IsEmpty() bool

IsEmpty checks, if the skiplist is empty.

func (*SkipList) Next

func (t *SkipList) Next(e *SkipListElement) *SkipListElement

Next returns the next element based on the given node. Next will loop around to the first node, if you call it on the last!

func (*SkipList) Prev

func (t *SkipList) Prev(e *SkipListElement) *SkipListElement

Prev returns the previous element based on the given node. Prev will loop around to the last node, if you call it on the first!

func (*SkipList) String

func (t *SkipList) String() string

String returns a string format of the skiplist. Useful to get a graphical overview and/or debugging.

type SkipListElement

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

SkipListElement represents one actual Node in the skiplist structure. It saves the actual element, pointers to the next nodes and a pointer to one previous node.

func (*SkipListElement) GetValue

func (e *SkipListElement) GetValue() ListElement

GetValue extracts the ListElement value from a skiplist node.