README
¶
ranklist
A high-performance real-time ranking data structure implemented using a Skip List in Golang.
Features
- Thread-Safe Operations: Provides safe concurrent access.
- Generic Support: Works seamlessly with various comparable data types.
- O(log n) Time Complexity: Efficient insertion, deletion, and query operations.
- Real-Time Ranking Queries: Optimized for fast ranking updates.
- Secondary Sorting: Supports tie-breaking for equal scores.
- Built-In Key-Value Dictionary: Enables O(1) key-value lookups.
Exceptional Performance
Whether for real-time ranking systems or as a high-performance key-value storage, ranklist delivers outstanding efficiency, achieving millions of writes and reads per second effortlessly.
- Write Performance: Capable of handling over a million write requests per second.
- Read Performance: Can handle up to tens of millions of read operations per second.
- Ranking Query: Supports real-time ranking queries, with the ability to process millions of ranking queries per second.
goos: windows
goarch: amd64
pkg: github.com/werbenhu/ranklist
cpu: AMD Ryzen 5 5600H with Radeon Graphics
BenchmarkRankListSet-12 2084486 572.5 ns/op 375 B/op 5 allocs/op
BenchmarkRankListGet-12 16147806 73.13 ns/op 0 B/op 0 allocs/op
BenchmarkRankListRank-12 5512027 220.5 ns/op 0 B/op 0 allocs/op
BenchmarkRankListRange-12 4931600 227.0 ns/op 496 B/op 5 allocs/op
BenchmarkFastSkipListSet-12 1000000 1542 ns/op 68 B/op 2 allocs/op
BenchmarkFastSkipListGet-12 12766310 90.00 ns/op 0 B/op 0 allocs/op
BenchmarkMapSet-12 4263243 355.6 ns/op 124 B/op 1 allocs/op
PASS
ok github.com/werbenhu/ranklist 19.546s
Usage
package main
import (
"fmt"
"github.com/werbenhu/ranklist"
)
func main() {
// Create a new rank list where keys are strings and scores are integers.
// The rank list uses a skip list internally for efficient ranking operations.
r := ranklist.New[string, int]()
// Add elements to the rank list with their respective scores.
// Keys "a", "b", "c", "d", and "e" are assigned scores 1, 2, 3, 4, and 5, respectively.
r.Set("a", 1)
r.Set("b", 2)
r.Set("c", 3)
r.Set("d", 4)
r.Set("e", 5)
// Delete the key "e" from the rank list.
// The Del method returns true if the key existed and was successfully removed.
if ok := r.Del("e"); ok {
fmt.Printf("Successfully deleted 'e'\n")
}
// Get the rank of the key "c".
// The Rank method returns the rank of the key (1-based) and a boolean indicating success.
if rank, ok := r.Rank("c"); ok {
fmt.Printf("The rank of 'c' is: %d\n", rank)
}
// Get the score associated with the key "d".
// The Get method returns the score and a boolean indicating success.
if score, ok := r.Get("d"); ok {
fmt.Printf("The score of 'd' is: %d\n", score)
}
// Retrieve the top 3 keys and their scores from the rank list.
ranks := r.Range(1, 4)
startRank := 1
for k := range ranks {
fmt.Printf("Key: %s, Score: %d, Rank: %d\n", ranks[k].Key, ranks[k].Value, startRank)
startRank++
}
}
Documentation
¶
Index ¶
Constants ¶
This section is empty.
Variables ¶
var ( // 跳表的最大层数。对于1000万数据量，根据公式 h = log₂(n)/2， // 大约需要 log₂(10⁷)/2 ≈ 12 层。请根据实际业务需求和数据量大小适当调整该值，以优化性能和空间利用。 // Maximum number of levels in the skip list. For 10 million elements, // using formula h = log₂(n)/2, we need approximately log₂(10⁷)/2 ≈ 12 levels. // Please adjust this value based on your actual business needs and data size to optimize performance and space utilization. MaxLevel = 12 // 用于随机层级生成的概率值，设置为0.25 // Probability used for random level generation, set to 0.25 Probability = 0.25 )
Functions ¶
Types ¶
type Ordered ¶
type Ordered interface {
~int | ~int8 | ~int16 | ~int32 | ~int64 |
~uint | ~uint8 | ~uint16 | ~uint32 | ~uint64 | ~uintptr |
~float32 | ~float64 |
~string
}
Ordered 接口定义了可用作键或值的类型约束 Ordered interface defines type constraints for keys and values
type RankList ¶
type RankList[K Ordered, V Ordered] struct { sync.RWMutex // contains filtered or unexported fields }
RankList 定义跳表的核心结构 提供线程安全的节点管理，支持插入、删除、查找、排名等功能 RankList defines the core structure of the skip list Provides thread-safe node management and supports insertion, deletion, retrieval, and ranking functionalities
func (*RankList[K, V]) Del ¶
Del 从跳表中删除指定键的节点。 如果键存在并且节点被删除，返回true；如果键不存在，返回false。 Del removes the node with the specified key from the skip list. Returns true if the key exists and the node is deleted, false if the key does not exist.
func (*RankList[K, V]) Get ¶
Get 根据键获取节点的值 如果键存在并且节点被删除，返回true；如果键不存在，返回false。 Get retrieves the value associated with the key Returns true if the key exists and the node is deleted, false if the key does not exist.
func (*RankList[K, V]) Length ¶ added in v1.0.1
Length 返回跳表中当前元素的数量。 Length returns the current number of elements in the skip list.
func (*RankList[K, V]) Range ¶ added in v1.0.1
Range 获取指定排名区间内的榜单项（不包含END） 返回指定范围内的条目列表。 Range retrieves the entries within the specified rank range (excluding END) Returns a list of entries within the specified range.
Source Files