skiplist

README

Skip List implement in Go

What is Skip List

Skip List is a data structure that allows fast search within an ordered sequence of elements. Fast search is made possible by maintaining a linked hierarchy of subsequences, each skipping over fewer elements.

(from wiki)

Install

go get github.com/byte-mug/golibs/concurrent/skiplist

Usage

    package main
    
    import (
	"fmt"
	
	. "github.com/byte-mug/golibs/concurrent/skiplist"
	"github.com/emirpasic/gods/utils"
    )

    func main() {
        //New a skiplist
        sl := skiplist.NewSkipList(utils.IntComparator)

        //Insert search key 50, value "5", value could be anything.
        sl.Insert(50, "5")
        sl.Insert(40, "4")
        sl.Insert(70, "7")
        sl.Insert(100, "10")

        //Search key, which time complexity O(log n)
        ret, err := sl.Search(50)
        if err == nil {
            fmt.Println("key 50: val->", ret)
        } else {
            fmt.Println("Not found, ", err)
        }

        //Delete by search key
        err = sl.Delete(70)
        if err != nil {
            fmt.Println("Delete not found")
        }

        //Display all skip list content.
        sl.DisplayAll()

    //head->[key:0][val:header]->[key:40][val:4]->[key:50][val:5]->[key:100][val:10]->nil
    //---------------------------------------------------------
    //[node:0], val:header, level:4  fw[3]:40 fw[2]:40 fw[1]:40 fw[0]:40
    //[node:40], val:4, level:4  fw[3]:nil fw[2]:nil fw[1]:50 fw[0]:50
    //[node:50], val:5, level:2  fw[1]:100 fw[0]:100
    //[node:100], val:10, level:2
    }    

Inspired By:

• Skip List bookbook
• SkipList Wiki
• 大数据日知录：架构与算法
• https://github.com/surge/skiplist
• https://github.com/huandu/skiplist
• https://github.com/gansidui/skiplist

Benchmark

Here is the benchmark list:

Note: The slice search op base on worst case.

//Slice Operations
BenchmarkSliceInsert-4   	100000000	        34.4  ns/op
BenchmarkSliceSearch-4   	   20000	     80149.0  ns/op

//Sliplist Operations
BenchmarkSkiplistInsert-4	  100000	     20881.0  ns/op
BenchmarkSkiplistSearch-4	10000000	       137.0  ns/op

It is very obviousily the skiplist search is much faster than slice iterator.

The map operation for reference.

//Map Operations
BenchmarkMapInsert-4     	 5000000	       283.0  ns/op
BenchmarkMapSearch-4     	30000000	        42.4  ns/op

Project52

It is one of my project 52.

License

This package is licensed under MIT license. See LICENSE for details.

Documentation

Overview

Skip List implement in Go.

A Skip List is a data structure that allows fast search within an ordered sequence of elements. Fast search is made possible by maintaining a linked hierarchy of subsequences, each skipping over fewer elements.

This Implementation is Partially Concurrent: It supports a single writer and multiple concurrent readers. Readers can access the Skiplist without locking.

Index

• Constants
• Variables
• type Skiplist
  • func NewSkipList(comparator utils.Comparator) *Skiplist
  • func (b *Skiplist) Delete(searchKey interface{}) error
  • func (b *Skiplist) DisplayAll()
  • func (b *Skiplist) Insert(searchKey interface{}, value interface{})
  • func (b *Skiplist) RandomLevel() int
  • func (b *Skiplist) Search(searchKey interface{}) (interface{}, error)
  • func (b *Skiplist) SetMaxLevel(maxLevel int)
• type Skipnode
  • func NewHeader(createLevel int, maxLevel int) *Skipnode
  • func NewNode(searchKey interface{}, value interface{}, createLevel int, maxLevel int) *Skipnode

Constants

const (
	DefaultMaxLevel    int     = 15   //Maximal level allow to create in this skip list
	DefaultPropability float32 = 0.25 //Default Propability
)

Variables

var (
	ErrNotFound = errors.New("Not found.")
)

Types

type Skiplist

type Skiplist struct {
	Header *Skipnode

	// List configuration
	MaxLevel    int
	Propability float32

	// List Comparison
	Comparator utils.Comparator

	// List status
	Level int //current level of whole skiplist

	Random *rand.Rand
}

func NewSkipList

func NewSkipList(comparator utils.Comparator) *Skiplist

NewSkipList : Init structure for Skit List.

func (*Skiplist) Delete

func (b *Skiplist) Delete(searchKey interface{}) error

Delete: Delete element by search key

func (*Skiplist) DisplayAll

func (b *Skiplist) DisplayAll()

DisplayAll: Display current SkipList content in console, will also print out the linked pointer.

func (*Skiplist) Insert

func (b *Skiplist) Insert(searchKey interface{}, value interface{})

Insert: Insert a search key and its value which could be interface.

func (*Skiplist) RandomLevel

func (b *Skiplist) RandomLevel() int

func (*Skiplist) Search

func (b *Skiplist) Search(searchKey interface{}) (interface{}, error)

Search: Search a element by search key and return the interface{}

func (*Skiplist) SetMaxLevel

func (b *Skiplist) SetMaxLevel(maxLevel int)

Change SkipList default maxlevel is 4.

type Skipnode

type Skipnode struct {
	Key interface{}
	Val interface{}

	Level int
	// contains filtered or unexported fields
}

func NewHeader

func NewHeader(createLevel int, maxLevel int) *Skipnode

func NewNode

func NewNode(searchKey interface{}, value interface{}, createLevel int, maxLevel int) *Skipnode