skiplist

README

SkipList Implement in Go

A Basically implement of skiplist, which doesn't consider courrency in go. skip lists： A probabilistaic alternative to balanced treees阐述了实现伪代码和设计上的工作

skip lists 的优点：

• 结构简单，每个节点占用的非信息空间少
• 查询速度和非递归自动调整树更快
• 每个节点的指针组创建之后就不必改动大小，只在插入或者删除后修改指向
• 有概率 P(Level=K)=1/(2^k)的概率，每个该节点的期望指针数是 2，修改和创建期望数也是如此

设立首次搜索 level= L(n)= log_2(n)，获取避免从当前最大 level 进行搜索，优化搜索次数。之后发现该条对性能没有明显提升，而且容易破坏更新值内容，故舍弃。

the feature of mu Implement

• Use simple element interface to pick up keys
• Implement skipItem instead of the iterator
• Use the tailing-zeros of a self-increasing seed to replace random level generator, which is slower and unstable. In my mac, the optimization surprisingly save about 20% time.
• Faster than most of skip-list structure
• I mantain this🤨

Drawback

limited by the lack of go generics, I have to use float64 to compare SkipItem. It's terrible, since you never know when you code will collision even if there is two rather different objet.

how to solve it? The answer is go2.

Test and Benchmark

 go clean -cache && go test -v
 go clean -cache && go test   -bench=. -v  # please don't use --race without runned parallel
 go clean -cache && go test   -bench=.  -v -cpuprofile=cpu.out -benchtime=100000000x
 go tool pprof -http localhost:8000 ./cpu.out
 go test -run=TestMonkey 

Results of benchmark:

#v0.0.2
// go clean -cache && go test  -run=NOTEST  -bench=.  -v -benchtime=1000000x -count=20 > x.out
// benchstat x.out
goos: darwin
goarch: amd64
pkg: github.com/MiniSkipList/skiplist
cpu: Intel(R) Core(TM) i7-9750H CPU @ 2.60GHz

// -benchtime=1000000x  -count=20
name                          time/op
SkipListInsert-12              121ns ±10%
SkipListFind-12               89.1ns ±14%
SkipListFindBiggerOrEqual-12  96.7ns ±12%
SkipListDelete-12             2.91ns ±14%
BucketmapInsert-12             132ns ± 6%
BucketmapFind-12               135ns ±32%
BucketmapDelete-12            2.61ns ±18%

// -benchtime=10000000x -count=20
name                          time/op
SkipListInsert-12              142ns ± 6%
SkipListFind-12                112ns ± 8%
SkipListFindBiggerOrEqual-12   114ns ± 7%
SkipListDelete-12             2.52ns ± 1%
BucketmapInsert-12             152ns ± 3%
BucketmapFind-12               150ns ± 4%
BucketmapDelete-12            2.38ns ±13%

// -benchtime=100000000x -count=5
name                          time/op
SkipListInsert-12              146ns ± 1%
SkipListFind-12                119ns ± 3%
SkipListFindBiggerOrEqual-12   113ns ± 2%
SkipListDelete-12             2.40ns ± 1%
BucketmapInsert-12             170ns ± 1%
BucketmapFind-12               176ns ± 3%
BucketmapDelete-12            2.20ns ± 2%

operations / comparation times:

BenchmarkSkipListInsert findtime/ops: 4845312580 / 100000001 :48.453125
BenchmarkSkipListFind  findtime/ops: 5022697254 / 100000001 :50.226972
BenchmarkSkipListFindBiggerOrEqual findtime/ops: 5022697254 / 100000001 :50.226972
BenchmarkSkipListDelete findtime/ops: 2520589160 / 100000001 :25.205891

Reference

Skip Lists: A Probabilistic Alternative to Balanced Trees

A Contention-Friendly, Non-Blocking Skip List

SkipList in C++

A another implement of skiplist in go And open API

The repo request you take a trunck of courage to read this codeeeeee.

Documentation

Index

• Constants
• type Element
• type EmptyElement
  • func (e EmptyElement) ExtendedKey() float64
• type SkipItem
• type SkipList
  • func NewSkipList(eps float64) SkipList
  • func (list *SkipList) Before(item *SkipItem) *SkipItem
  • func (list *SkipList) Delete(key float64) bool
  • func (list *SkipList) Empty() bool
  • func (list *SkipList) Find(key float64) (Element, bool)
  • func (list *SkipList) FindBiggerOrEqual(key float64) (Element, bool)
  • func (list *SkipList) FindBiggerOrEqualItem(key float64) (*SkipItem, bool)
  • func (list *SkipList) FindItem(key float64) (*SkipItem, bool)
  • func (list *SkipList) Insert(element Element)
  • func (list *SkipList) Maximal() *SkipItem
  • func (list *SkipList) Minimal() *SkipItem
  • func (list *SkipList) Next(item *SkipItem) *SkipItem
  • func (list *SkipList) Size() int
  • func (list *SkipList) String() string

Constants

const (
	RecommendedEps = 1e-9
	MaxLevel       = 40
)

const (
	FormatLen  = 5
	FormatBits = 64
)

Types

type Element

type Element interface {
	ExtendedKey() float64
}

type EmptyElement

type EmptyElement int

func (EmptyElement) ExtendedKey

func (e EmptyElement) ExtendedKey() float64

type SkipItem

type SkipItem struct {
	Element
	// contains filtered or unexported fields
}

type SkipList

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

func NewSkipList

func NewSkipList(eps float64) SkipList

func (*SkipList) Before

func (list *SkipList) Before(item *SkipItem) *SkipItem

func (*SkipList) Delete

func (list *SkipList) Delete(key float64) bool

func (*SkipList) Empty

func (list *SkipList) Empty() bool

func (*SkipList) Find

func (list *SkipList) Find(key float64) (Element, bool)

func (*SkipList) FindBiggerOrEqual

func (list *SkipList) FindBiggerOrEqual(key float64) (Element, bool)

func (*SkipList) FindBiggerOrEqualItem

func (list *SkipList) FindBiggerOrEqualItem(key float64) (*SkipItem, bool)

func (*SkipList) FindItem

func (list *SkipList) FindItem(key float64) (*SkipItem, bool)

func (*SkipList) Insert

func (list *SkipList) Insert(element Element)

func (*SkipList) Maximal

func (list *SkipList) Maximal() *SkipItem

func (*SkipList) Minimal

func (list *SkipList) Minimal() *SkipItem

func (*SkipList) Next

func (list *SkipList) Next(item *SkipItem) *SkipItem

func (*SkipList) Size

func (list *SkipList) Size() int

func (*SkipList) String

func (list *SkipList) String() string