A Go library for an efficient implementation of a skip list: https://godoc.org/github.com/MauriceGit/skiplist

Overview

Go Report Card cover.run

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

Find, Insert, Delete 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.

Random insert, random delete 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.

Random insert 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.

Random delete 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)
Comments
  • Update README.md

    Update README.md

    Changed "as direct substitute for" to "to replace" Moved links into text Edited and divided the run-on sentence before comparison section into two sentences Removed avoidable words such as "Overall"

    opened by ovidr 2
  • Incorrect min. element.

    Incorrect min. element.

    Tried to use the library just now with string keys that should be lexicographically ordered, though noticed that the minimum value returned was incorrect.

    Might there be a preferred way to have arbitrary-length string keys in this case? The keys I'm looking to use are 256-bit strings, so this current solution additionally would fail for my use case.

    Test case:

    package testbed
    
    import (
    	"github.com/MauriceGit/skiplist"
    	"math/big"
    	"testing"
    	"fmt"
    )
    
    type WrappedString struct {
    	Id string
    }
    
    func (w WrappedString) ExtractKey() float64 {
    	num := new(big.Int)
    	num.SetBytes([]byte(w.Id))
    
    	fmt.Println(w.Id, " ", float64(num.Uint64()))
    
    	return float64(num.Uint64())
    }
    
    func (w WrappedString) String() string {
    	return w.Id
    }
    
    func TestSkiplist(t *testing.T) {
    	list := new(skiplist.SkipList)
    
    	ids := []string{"a", "b", "c", "d"}
    
    	for _, id := range ids {
    		list.Insert(WrappedString{Id: id})
    	}
    
    	t.Log("min: ", list.GetSmallestNode().GetValue())
    	t.Log("max: ", list.GetLargestNode().GetValue())
    }
    

    Log:

    === RUN   TestSkiplist
    a   97
    b   98
    c   99
    d   100
    --- PASS: TestSkiplist (0.00s)
        skiplist_test.go:36: min:  b
        skiplist_test.go:37: max:  d
    PASS
    ok      github.com/iwasaki-kenta/testbed/inmem 0.002s
    
    opened by iwasaki-kenta 1
  • Fix infinite loop bug

    Fix infinite loop bug

    Problem

    Using Find method on list can cause infinite loop. I think the reason is this d865d03eefc1f2e097e01466c22b2bb4f9fb543e commit, just misplaced return statement.

    Fix

    return has been moved outside the condition, I also added test that fails due to timeout

    Thank you.

    opened by cheetah 0
  • Specify behaviour when dealing with duplicate keys

    Specify behaviour when dealing with duplicate keys

    I've been trying to find what the behaviour of different methods is with respect to duplicate keys, but can't find anything official or obvious.

    Some limited testing has shown that duplicates are added to the list rather than replacing existing entries, but without it written into the specification I'm not sure whether I can rely on this or not. I've also noticed that Finding using a key that is duplicated seems to return the SkipListElement at the start of the duplicated block (so you can call Next to get the next, etc), again not sure I can rely on this behaviour or not.

    For the record, I'd like duplicates to continue to be added.

    opened by mattnathan 0
  • maybe your test dataset range is too small.

    maybe your test dataset range is too small.

    go test   . -bench=. -run=NOTEST  -v -cpuprofile=cpu.out -benchtime=1000000x
    goos: darwin
    goarch: amd64
    pkg: github.com/skiplist
    cpu: Intel(R) Core(TM) i7-9750H CPU @ 2.60GHz
    BenchmarkSkipListInsert
    BenchmarkSkipListInsert-12                       1000000               224.7 ns/op
    BenchmarkSkipListFind
    BenchmarkSkipListFind-12                         1000000               151.9 ns/op
    BenchmarkSkipListFindBiggerOrEqual
    BenchmarkSkipListFindBiggerOrEqual-12            1000000               140.7 ns/op
    BenchmarkSkipListDelete
    BenchmarkSkipListDelete-12                       1000000                72.63 ns/op
    
    go test   . -bench=. -run=NOTEST  -v -cpuprofile=cpu.out -benchtime=10000000x 
    goos: darwin
    goarch: amd64
    pkg: github.com/skiplist
    cpu: Intel(R) Core(TM) i7-9750H CPU @ 2.60GHz
    BenchmarkSkipListInsert
    BenchmarkSkipListInsert-12                      10000000               224.0 ns/op
    BenchmarkSkipListFind
    BenchmarkSkipListFind-12                        10000000               163.9 ns/op
    BenchmarkSkipListFindBiggerOrEqual
    BenchmarkSkipListFindBiggerOrEqual-12           10000000               156.8 ns/op
    BenchmarkSkipListDelete
    BenchmarkSkipListDelete-12                      10000000                80.16 ns/op
    
    
    go test   . -bench=. -run=NOTEST  -v -cpuprofile=cpu.out -benchtime=100000000x 
    goos: darwin
    goarch: amd64
    pkg: github.com/skiplist
    cpu: Intel(R) Core(TM) i7-9750H CPU @ 2.60GHz
    BenchmarkSkipListInsert
    BenchmarkSkipListInsert-12                      100000000              329.4 ns/op
    BenchmarkSkipListFind
    BenchmarkSkipListFind-12                        100000000              369.1 ns/op
    BenchmarkSkipListFindBiggerOrEqual
    BenchmarkSkipListFindBiggerOrEqual-12           100000000              318.8 ns/op
    BenchmarkSkipListDelete
    BenchmarkSkipListDelete-12                      100000000              269.6 ns/op
    

    relative code

    opened by Ruth-Seven 0
  • bugs

    bugs

    hi, i saw the lastest bug you submitted, but i believe that bug still exists, when i test a mutil insert. some of the nodes disappear. I'm trying to solve it

    opened by jacksoom 1
Owner
Maurice Tollmien
Maurice Tollmien
Fast and easy-to-use skip list for Go.

Skip List in Golang Skip list is an ordered map. See wikipedia page skip list to learn algorithm details about this data structure. Highlights in this

Huan Du 304 Dec 4, 2022
skipmap is a high-performance concurrent sorted map based on skip list. Up to 3x ~ 10x faster than sync.Map in the typical pattern.

Introduction skipmap is a high-performance concurrent map based on skip list. In typical pattern(one million operations, 90%LOAD 9%STORE 1%DELETE), th

ZhangYunHao 106 Jan 8, 2023
A skip list of arbitrary elements that can be filtered using roaring bitmaps stored in an LRU cache

Skipfilter This package provides a data structure that combines a skiplist with a roaring bitmap cache. This library was created to efficiently filter

Kevin Burns 22 Aug 4, 2022
A fast, threadsafe skip list in Go

fast-skiplist Purpose As the basic building block of an in-memory data structure store, I needed an implementation of skip lists in Go. It needed to b

sean 240 Dec 2, 2022
skiplist for golang

skiplist reference from redis zskiplist Usage package main import ( "fmt" "github.com/gansidui/skiplist" "log" ) type User struct { score float6

gansidui 80 Dec 6, 2022
High-performance minimalist queue implemented using a stripped-down lock-free ringbuffer, written in Go (golang.org)

This project is no longer maintained - feel free to fork the project! gringo A high-performance minimalist queue implemented using a stripped-down loc

Darren Elwood 129 Oct 24, 2022
A simple and efficient thread-safe sharded hashmap for Go

shardmap A simple and efficient thread-safe sharded hashmap for Go. This is an alternative to the standard Go map and sync.Map, and is optimized for w

Josh Baker 192 Dec 17, 2022
Package mafsa implements Minimal Acyclic Finite State Automata in Go, essentially a high-speed, memory-efficient, Unicode-friendly set of strings.

MA-FSA for Go Package mafsa implements Minimal Acyclic Finite State Automata (MA-FSA) with Minimal Perfect Hashing (MPH). Basically, it's a set of str

SmartyStreets (Archives) 293 Oct 27, 2022
Surprisingly space efficient trie in Golang(11 bits/key; 100 ns/get).

Slim - surprisingly space efficient data types in Golang Slim is collection of surprisingly space efficient data types, with corresponding serializati

null 1.8k Jan 2, 2023
A memory-efficient trie for testing the existence/prefixes of string only(for now).

Succinct Trie A memory-efficient trie for testing the existence/prefixes of string only(for now). Install go get -u github.com/nobekanai/sutrie Docume

野辺かない 2 Mar 10, 2022
Novel, efficient, and practical image compression with visually appealing results. 🤏 ✨

Tiny Thumb ?? ✨ A novel, efficient, and practical method for lossy image compression, that produces visually appealing thumbnails. This technique is u

Slack 8 Nov 1, 2022
Most comprehensive list :clipboard: of tech interview questions :blue_book: of companies scraped from Geeksforgeeks, CareerCup and Glassdoor.

Companies* Companies E Expedia G Grab M MobiKwik N NEC Technologies P PayPal S Samsung Research Institute U Uber Y Yatra.com Z Zomato Announcements ??

Twowaits 6.4k Dec 29, 2022
The first generic linked list in go :dancer:

linkedlist.go The first generic linked list in go ?? gotip first of all you need to install the master version of golang. go install golang.org/dl/got

Parham Alvani 26 Dec 7, 2022
Advanced linked list package for go.

golib/list ライブラリ 可変長の連結リストを提供するライブラリーです。 状況によらず、メモリ開放処理を一貫性した書き方で実装できるので、メモリ解放をプログラマが管理しやすい作りになっています。 list.List 片方向連結リストを提供するモジュールです。 list.Nodeが使われていま

null 0 Jan 21, 2022
Go implementation of Count-Min-Log

Count-Min-Log Count-Min-Log sketch: Approximately counting with approximate counters - Guillaume Pitel & Geoffroy Fouquier TL;DR: Count-Min-Log Sketch

Seif Lotfy 59 Jan 4, 2023
A Go implementation of the Elias-Fano encoding

go-ef A Go implementation of the Elias-Fano encoding Example package main import ( "fmt" "github.com/amallia/go-ef" "os" ) func main() {

Antonio Mallia 27 Nov 23, 2022
Set is a useful collection but there is no built-in implementation in Go lang.

goset Set is a useful collection but there is no built-in implementation in Go lang. Why? The only one pkg which provides set operations now is golang

zoumo 50 Sep 26, 2022
Go implementation of C++ STL iterators and algorithms.

iter Go implementation of C++ STL iterators and algorithms. Less hand-written loops, more expressive code. README translations: 简体中文 Motivation Althou

disksing 170 Dec 19, 2022
Go implementation to calculate Levenshtein Distance.

levenshtein Go package to calculate the Levenshtein Distance The library is fully capable of working with non-ascii strings. But the strings are not n

Agniva De Sarker 253 Dec 14, 2022