Description

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.

skip is referenced in 1 repository

github.com/Workiva/go-datastructures