sortedset

package module
Version: v1.1.1 Latest Latest
Warning

This package is not in the latest version of its module.

Go to latest
Published: Jul 31, 2022 License: MIT Imports: 2 Imported by: 0

README

Sorted Set in Golang with Generics

Sorted Set is a data-struct inspired by the one from Redis. It allows fast access by key or score.

Property Type Description
key constraints.Ordered The identifier of the node. It must be unique within the set.
value any value associated with this node
score constraints.Ordered score determines the position of the item within the sorted set.

Each node in the set is associated with a key. While keys are unique, scores may be repeated. Nodes are taken in order instead of ordered afterwards, from low score to high score. If scores are the same, the node is ordered by its key in lexicographic order. Each node in the set is associated with rank, which represents the position of the node in the sorted set. The rank is 1-based, i.e. rank 1 is the item with the lowest score.

Sorted Set is implemented based on skip list and hash map internally. With sorted sets you can add, remove, or update nodes very efficiently with log(N) complexity. You can also get ranges by score or by rank (position) in a very fast way. Accessing the middle of a sorted set is also very fast, so you can use Sorted Sets as a smart list of non repeating nodes where you have quick access to everything you need: nodes in order, existence test, access to nodes in the middle.

A typical use case of sorted set is a leaderboard in a massive online game, where every time a new score is submitted you update it using AddOrUpdate(). You can easily take the top users using GetRangeByRank(), you can also, given an user id, return its rank in the list using FindRank(). Using FindRank() and GetRangeByRank() together you can show users with a score similar to a given user.

Documentation

https://godoc.org/github.com/zavitax/sortedset-go

Documentation

Overview

Package sortedset was inspired by SortedSet in Redis: it provides fast access to elements in sorted set by key or score(order).

Introduction

Every node in the set is associated with these properties.

type SortedSetNode[K constraints.Ordered, SCORE constraints.Ordered, V any] struct {
    key      K       // unique key of this node
    Value    V       // associated data
    score    SCORE   // int64 score to determine the order of this node in the set
}

Each node in the set is associated with a key. While keys are unique, scores may repeat. Nodes are kept ordered by score and key. Each node in the set can be also accessed by rank: the position of the node in the sorted set.

With sorted sets you can add, remove or update nodes in a very efficient way (O(N) = log(N)). You can also retrieve ranges of nodes by score or by rank in a very efficient way. Accessing the middle of a sorted set is also very efficient, so you can use Sorted Sets as smart lists of non repeating nodes, where you can quickly access everything you need: nodes in order, fast existence test, fast access to nodes in the middle.

Use Case

A typical use case of sorted set is a leaderboard in a massive online game, where you update the player's position every time a new score is submitted. You can easily take the top players using GetRangeByRank() method. You can also, given an user id, return their rank in the listing using FindRank() method. Using FindRank() and GetRangeByRank() together you can show users with a score similar to a given user.

Examples

// create a new set
set := sortedset.New[string, int64, string]()

// fill in new node
set.AddOrUpdate("a", 89, "Kelly")
set.AddOrUpdate("b", 100, "Staley")
set.AddOrUpdate("c", 100, "Jordon")
set.AddOrUpdate("d", -321, "Park")
set.AddOrUpdate("e", 101, "Albert")
set.AddOrUpdate("f", 99, "Lyman")
set.AddOrUpdate("g", 99, "Singleton")
set.AddOrUpdate("h", 70, "Audrey")

// update an existing node by key
set.AddOrUpdate("e", 99, "ntrnrt")

// get the node by key
set.GetByKey("b")

// remove node by key
set.Remove("b")

// get the number of nodes in this set
set.GetCount()

// find the rank(postion) in the set.
set.FindRank("d") // return 1 here

// get and remove the node with minimum score
set.PopMin()

// get the node with maximum score
set.PeekMax()

// get the node at rank 1 (the node with minimum score)
set.GetByRank(1, false)

// get & remove the node at rank -1 (the node with maximum score)
set.GetByRank(-1, true)

// get the node with the 2nd highest maximum score
set.GetByRank(-2, false)

// get nodes with in rank range [1, -1],  that is all nodes actually
set.GetRangeByRank(1, -1, false)

// get & remove the 2nd/3rd nodes in reserve order
set.GetRangeByRank(-2, -3, true)

// get the nodes whose score are within the interval [60,100]
set.GetRangeByScore(60, 100, nil)

// get the nodes whose score are within the interval (60,100]
set.GetRangeByScore(60, 100, &GetRangeByScoreOptions{
    ExcludeStart: true,
})

// get the nodes whose score are within the interval [60,100)
set.GetRangeByScore(60, 100, &GetRangeByScoreOptions{
    ExcludeEnd: true,
})

// get the nodes whose score are within the interval [60,100] in reverse order
set.GetRangeByScore(100, 60, nil)

// get the top 2 nodes with lowest scores within the interval [60,100]
set.GetRangeByScore(60, 100, &GetRangeByScoreOptions{
    Limit: 2,
})

// get the top 2 nodes with highest scores within the interval [60,100]
set.GetRangeByScore(100, 60, &GetRangeByScoreOptions{
    Limit: 2,
})

// get the top 2 nodes with highest scores within the interval (60,100)
set.GetRangeByScore(100, 60, &GetRangeByScoreOptions{
    Limit: 2,
    ExcludeStart: true,
    ExcludeEnd: true,
})

Index

Constants

View Source
const SKIPLIST_MAXLEVEL = 32 /* Should be enough for 2^32 elements */
View Source
const SKIPLIST_P = 0.25 /* Skiplist P = 1/4 */

Variables

This section is empty.

Functions

This section is empty.

Types

type GetRangeByScoreOptions added in v1.0.1

type GetRangeByScoreOptions struct {
	Limit        int  // limit the max nodes to return
	ExcludeStart bool // exclude start value, so it search in interval (start, end] or (start, end)
	ExcludeEnd   bool // exclude end value, so it search in interval [start, end) or (start, end)
}

type SortedSet

type SortedSet[K constraints.Ordered, SCORE constraints.Ordered, V any] struct {
	// contains filtered or unexported fields
}

func New

func New[K constraints.Ordered, SCORE constraints.Ordered, V any]() *SortedSet[K, SCORE, V]

Create a new SortedSet

func (*SortedSet[K, SCORE, V]) AddOrUpdate

func (this *SortedSet[K, SCORE, V]) AddOrUpdate(key K, score SCORE, value V) bool

Add an element into the sorted set with specific key / value / score. if the element is added, this method returns true; otherwise false means updated

Time complexity of this method is : O(log(N))

func (*SortedSet[K, SCORE, V]) FindRank

func (this *SortedSet[K, SCORE, V]) FindRank(key K) int

Find the rank of the node specified by key Note that the rank is 1-based integer. Rank 1 means the first node

If the node is not found, 0 is returned. Otherwise rank(> 0) is returned

Time complexity of this method is : O(log(N))

func (*SortedSet[K, SCORE, V]) GetByKey

func (this *SortedSet[K, SCORE, V]) GetByKey(key K) *SortedSetNode[K, SCORE, V]

Get node by key

If node is not found, nil is returned Time complexity : O(1)

func (*SortedSet[K, SCORE, V]) GetByRank

func (this *SortedSet[K, SCORE, V]) GetByRank(rank int, remove bool) *SortedSetNode[K, SCORE, V]

Get node by rank. Note that the rank is 1-based integer. Rank 1 means the first node; Rank -1 means the last node;

If remove is true, the returned nodes are removed If node is not found at specific rank, nil is returned

Time complexity of this method is : O(log(N))

func (*SortedSet[K, SCORE, V]) GetCount

func (this *SortedSet[K, SCORE, V]) GetCount() int

Get the number of elements

func (*SortedSet[K, SCORE, V]) GetRangeByRank added in v1.0.1

func (this *SortedSet[K, SCORE, V]) GetRangeByRank(start int, end int, remove bool) []*SortedSetNode[K, SCORE, V]

Get nodes within specific rank range [start, end] Note that the rank is 1-based integer. Rank 1 means the first node; Rank -1 means the last node;

If start is greater than end, the returned array is in reserved order If remove is true, the returned nodes are removed

Time complexity of this method is : O(log(N))

func (*SortedSet[K, SCORE, V]) GetRangeByScore added in v1.0.1

func (this *SortedSet[K, SCORE, V]) GetRangeByScore(start SCORE, end SCORE, options *GetRangeByScoreOptions) []*SortedSetNode[K, SCORE, V]

Get the nodes whose score within the specific range

If options is nil, it searchs in interval [start, end] without any limit by default

Time complexity of this method is : O(log(N))

func (*SortedSet[K, SCORE, V]) IterFuncRangeByRank added in v1.0.1

func (this *SortedSet[K, SCORE, V]) IterFuncRangeByRank(start int, end int, fn func(key K, value V) bool)

IterFuncRangeByRank apply fn to node within specific rank range [start, end] or until fn return false

Note that the rank is 1-based integer. Rank 1 means the first node; Rank -1 means the last node; If start is greater than end, apply fn in reserved order If fn is nil, this function return without doing anything

func (*SortedSet[K, SCORE, V]) PeekMax

func (this *SortedSet[K, SCORE, V]) PeekMax() *SortedSetNode[K, SCORE, V]

get the element with maximum score, nil if the set is empty Time Complexity : O(1)

func (*SortedSet[K, SCORE, V]) PeekMin

func (this *SortedSet[K, SCORE, V]) PeekMin() *SortedSetNode[K, SCORE, V]

get the element with minimum score, nil if the set is empty

Time complexity of this method is : O(log(N))

func (*SortedSet[K, SCORE, V]) PopMax

func (this *SortedSet[K, SCORE, V]) PopMax() *SortedSetNode[K, SCORE, V]

get and remove the element with maximum score, nil if the set is empty

Time complexity of this method is : O(log(N))

func (*SortedSet[K, SCORE, V]) PopMin

func (this *SortedSet[K, SCORE, V]) PopMin() *SortedSetNode[K, SCORE, V]

get and remove the element with minimal score, nil if the set is empty

// Time complexity of this method is : O(log(N))

func (*SortedSet[K, SCORE, V]) Remove

func (this *SortedSet[K, SCORE, V]) Remove(key K) *SortedSetNode[K, SCORE, V]

Delete element specified by key

Time complexity of this method is : O(log(N))

type SortedSetLevel

type SortedSetLevel[K constraints.Ordered, SCORE constraints.Ordered, V any] struct {
	// contains filtered or unexported fields
}

type SortedSetNode

type SortedSetNode[K constraints.Ordered, SCORE constraints.Ordered, V any] struct {
	Value V // associated data
	// contains filtered or unexported fields
}

Node in skip list

func (*SortedSetNode[K, SCORE, V]) Key

func (this *SortedSetNode[K, SCORE, V]) Key() K

Get the key of the node

func (*SortedSetNode[K, SCORE, V]) Score

func (this *SortedSetNode[K, SCORE, V]) Score() SCORE

Get the node of the node

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL