sortedset

package module
v0.0.0-...-af6d6d2 Latest Latest
Warning

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

 Go to latest Published: Feb 9, 2022 License: BSD-2-Clause Imports: 1 Imported by: 12

README

Sorted Set in Golang

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

Property Type Description
key string The identifier of the node. It must be unique within the set.
value interface {} value associated with this node
score int64 score is in order to take the sorted set ordered. It may be repeated.

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, that is to say, rank 1 is the node with minimum score.

Sorted Set is implemented basing on skip list and hash map internally. With sorted sets you can add, remove, or update nodes in a very fast way (in a time proportional to the logarithm of the number of nodes). 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 can quickly access everything you need: nodes in order, fast existence test, fast access to nodes in the middle!

A typical use case of sorted set is a leader board 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 GetByRankRange(), you can also, given an user id, return its rank in the listing using FindRank(). Using FindRank() and GetByRankRange() together you can show users with a score similar to a given user. All very quickly.

Documentation

https://godoc.org/github.com/wangjia184/sortedset

Documentation

Overview

Package sortedset provides the data-struct allows fast access the element in set by key or by score(order). It is inspired by Sorted Set from Redis.

Introduction

Every node in the set is associated with these properties. 

type SortedSetNode struct {
    key      string      // unique key of this node
    Value    interface{} // 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 be repeated. Nodes are taken in order (from low score to high score) instead of ordered afterwards. If scores are the same, the node is ordered by its key in lexicographic order. Each node in the set also can be accessed by rank, which represents the position in the sorted set.

Sorted Set is implemented basing on skip list and hash map internally. With sorted sets you can add, remove, or update nodes in a very fast way (in a time proportional to the logarithm of the number of nodes). 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 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 leader board in a massive online game, where every time a new score is submitted you update it using AddOrUpdate() method. You can easily take the top users using GetByRankRange() method, you can also, given an user id, return its rank in the listing using FindRank() method. Using FindRank() and GetByRankRange() together you can show users with a score similar to a given user. All very quickly.

Examples 

// create a new set
set := sortedset.New()

// 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.GetByRankRange(1, -1, false)

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

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

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

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

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

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

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

// get the top 2 nodes with highest scores within the interval (60,100)
set.GetByScoreRange(100, 60, &GetByScoreRangeOptions{
    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 GetByScoreRangeOptions 

type GetByScoreRangeOptions 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 SCORE 

type SCORE int64 // the type of score

type SortedSet 

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

func New 

func New() *SortedSet

Create a new SortedSet

func (*SortedSet) AddOrUpdate 

func (this *SortedSet) AddOrUpdate(key string, score SCORE, value interface{}) 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) FindRank 

func (this *SortedSet) FindRank(key string) 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) GetByKey 

func (this *SortedSet) GetByKey(key string) *SortedSetNode

Get node by key

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

func (*SortedSet) GetByRank 

func (this *SortedSet) GetByRank(rank int, remove bool) *SortedSetNode

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) GetByRankRange 

func (this *SortedSet) GetByRankRange(start int, end int, remove bool) []*SortedSetNode

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) GetByScoreRange 

func (this *SortedSet) GetByScoreRange(start SCORE, end SCORE, options *GetByScoreRangeOptions) []*SortedSetNode

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) GetCount 

func (this *SortedSet) GetCount() int

Get the number of elements

func (*SortedSet) IterFuncByRankRange 

func (this *SortedSet) IterFuncByRankRange(start int, end int, fn func(key string, value interface{}) bool)

IterFuncByRankRange 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) PeekMax 

func (this *SortedSet) PeekMax() *SortedSetNode

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

func (*SortedSet) PeekMin 

func (this *SortedSet) PeekMin() *SortedSetNode

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

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

func (*SortedSet) PopMax 

func (this *SortedSet) PopMax() *SortedSetNode

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) PopMin 

func (this *SortedSet) PopMin() *SortedSetNode

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) Remove 

func (this *SortedSet) Remove(key string) *SortedSetNode

Delete element specified by key

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

type SortedSetLevel 

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

type SortedSetNode 

type SortedSetNode struct {
	Value interface{} // associated data
	// contains filtered or unexported fields
}

Node in skip list

func (*SortedSetNode) Key 

func (this *SortedSetNode) Key() string

Get the key of the node

func (*SortedSetNode) Score 

func (this *SortedSetNode) Score() SCORE

Get the node of the node

Source Files

View all Source files

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.