Skip to content

Latest commit

 

History

History
101 lines (82 loc) · 4.39 KB

README.md

File metadata and controls

101 lines (82 loc) · 4.39 KB

English | 简体中文

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                  2792992               396.0 ns/op           288 B/op          1 allocs/op
BenchmarkRankListRandSet-12              1000000              1546 ns/op             311 B/op          1 allocs/op
BenchmarkRankListGet-12                 16712578                72.03 ns/op            0 B/op          0 allocs/op
BenchmarkRankListRank-12                 6192979               196.8 ns/op             0 B/op          0 allocs/op
BenchmarkRankListRange-12                5647262               183.0 ns/op           496 B/op          5 allocs/op
BenchmarkZSetRandSet-12                  1000000              2905 ns/op             167 B/op          3 allocs/op
BenchmarkFastSkipListSet-12              6431894               200.3 ns/op            68 B/op          2 allocs/op
BenchmarkFastSkipListRandSet-12          1000000              1342 ns/op              68 B/op          2 allocs/op
BenchmarkFastSkipListGet-12             12885158                89.49 ns/op            0 B/op          0 allocs/op
BenchmarkMapSet-12                       4308596               338.7 ns/op           122 B/op          1 allocs/op
PASS
ok      github.com/werbenhu/ranklist    21.948s

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++
	}
}