golang高性能跳表数据结构实现插件库skiplist的使用

Golang高性能跳表数据结构实现插件库skiplist的使用

快速跳表实现

这个Go库实现了一个非常快速高效的跳表，可以直接替代平衡树或链表。所有基本操作(Find、Insert和Delete)的运行时间大约为O(log(n))，这在基准测试中得到了验证。

性能表现

Y轴在所有图表中均以纳秒/操作为单位测量

Find, Insert, Delete 所有操作跳表首尾元素的函数，无论是Find、Insert还是Delete，都表现出接近常数时间的行为，无论跳表中已经插入了多少元素。

Random insert, random delete 对于在跳表中随机位置插入或删除元素的真实场景，我们可以清楚地看到实现的近似O(log(n))行为，Delete操作大约稳定在1800ns左右，Insert操作大约稳定在2200ns左右。

与其他跳表实现的比较

总体而言，这个实现对于几乎所有操作都是最快的跳表实现，特别是在实际应用中。

Random insert 如果我们将这个跳表的随机插入与其他实现进行比较，它显然是最快的，对于多达300万个元素，每次插入最多快800ns。

Random delete 如果我们将这个跳表的随机删除与其他实现进行比较，它显然是最快的，对于多达300万个元素，每次删除最多快300ns。

使用示例

import (
    "github.com/MauriceGit/skiplist"
    "fmt"
)

type Element int
// 实现skiplist中使用的接口
func (e Element) ExtractKey() float64 {
    return float64(e)
}
func (e Element) String() string {
    return fmt.Sprintf("%03d", e)
}

func main() {
    list := skiplist.New()

    // 插入一些元素
    for i := 0; i < 100; i++ {
        list.Insert(Element(i))
    }

    // 查找一个元素
    if e, ok := list.Find(Element(53)); ok {
        fmt.Println(e)
    }

    // 删除所有元素
    for i := 0; i < 100; i++ {
        list.Delete(Element(i))
    }
}

便捷函数

除了经典的Find、Insert和Delete外，还实现了一些更便捷的函数，使得这个跳表实现在实际应用中非常容易和直接使用。所有复杂度值都是近似值，因为跳表只能近似运行时复杂度。

函数 复杂度 描述
Find O(log(n)) 在跳表中查找元素
FindGreaterOrEqual O(log(n)) 查找跳表中第一个大于或等于给定值的元素
Insert O(log(n)) 向跳表中插入元素
Delete O(log(n)) 从跳表中删除元素
GetSmallestNode O(1) 返回跳表中最小的元素
GetLargestNode O(1) 返回跳表中最大的元素
Prev O(1) 给定一个跳表节点，返回前一个元素(可以环绕并允许线性迭代跳表)
Next O(1) 给定一个跳表节点，返回下一个元素(可以环绕并允许线性迭代跳表)
ChangeValue O(1) 给定一个跳表节点，可以更改实际值，只要键保持不变(例如：更改结构体数据)

更多关于golang高性能跳表数据结构实现插件库skiplist的使用的实战教程也可以访问 https://www.itying.com/category-94-b0.html

1 回复

更多关于golang高性能跳表数据结构实现插件库skiplist的使用的实战系列教程也可以访问 https://www.itying.com/category-94-b0.html


Golang 高性能跳表实现 - skiplist 使用指南

跳表(Skip List)是一种概率性的有序数据结构，它通过多级索引实现了类似平衡树的查询效率(O(log n))，但实现更为简单。下面介绍一个流行的 Golang 跳表实现库 github.com/sean-public/skiplist 的使用方法。

安装

go get github.com/sean-public/skiplist

基本使用

1. 创建跳表

package main

import (
	"fmt"
	"github.com/sean-public/skiplist"
)

func main() {
	// 创建一个新的跳表实例
	sl := skiplist.New()
	
	// 带自定义比较函数的跳表
	// sl := skiplist.NewWithOpts(skiplist.LessThanFunc(func(a, b interface{}) bool {
	//     return a.(int) < b.(int)
	// }))
}

2. 插入元素

// 插入键值对
sl.Set(3, "three")
sl.Set(1, "one")
sl.Set(2, "two")
sl.Set(4, "four")

// 批量插入
items := []struct {
	key   interface{}
	value interface{}
}{
	{5, "five"},
	{6, "six"},
}

for _, item := range items {
	sl.Set(item.key, item.value)
}

3. 查找元素

// 查找元素
value, ok := sl.Get(2)
if ok {
	fmt.Printf("Found value: %v\n", value) // 输出: Found value: two
}

// 检查是否存在
exists := sl.Has(3) // true

4. 删除元素

// 删除元素
removed := sl.Delete(1) // 返回是否成功删除
if removed {
	fmt.Println("Key 1 removed")
}

5. 遍历元素

// 正向迭代
for it := sl.Iterator(); it.Next(); {
	fmt.Printf("Key: %v, Value: %v\n", it.Key(), it.Value())
}

// 反向迭代
for it := sl.Iterator().ToReverse(); it.Next(); {
	fmt.Printf("Key: %v, Value: %v\n", it.Key(), it.Value())
}

// 范围查询
for it := sl.Range(2, 5); it.Next(); {
	fmt.Printf("Key: %v, Value: %v\n", it.Key(), it.Value())
}

高级功能

1. 获取跳表信息

// 获取跳表长度
length := sl.Len()

// 获取跳表层级
levels := sl.Levels()

fmt.Printf("Length: %d, Levels: %d\n", length, levels)

2. 元素排名

// 获取元素的排名(从1开始)
rank := sl.GetRank(3)
fmt.Printf("Rank of key 3: %d\n", rank)

3. 获取最大/最小值

// 获取最小值
minKey, minValue := sl.Min()
fmt.Printf("Min - Key: %v, Value: %v\n", minKey, minValue)

// 获取最大值
maxKey, maxValue := sl.Max()
fmt.Printf("Max - Key: %v, Value: %v\n", maxKey, maxValue)

性能特点

  1. 时间复杂度:

    • 查找: O(log n)
    • 插入: O(log n)
    • 删除: O(log n)
    • 范围查询: O(log n + m) (m为范围内元素数量)

  2. 空间复杂度: O(n)

使用场景

  1. 需要有序数据结构的场景
  2. 需要频繁插入、删除和查找的场景
  3. 需要范围查询的场景
  4. 替代平衡树的更简单实现

完整示例

package main

import (
	"fmt"
	"github.com/sean-public/skiplist"
)

func main() {
	sl := skiplist.New()
	
	// 插入数据
	sl.Set(3, "three")
	sl.Set(1, "one")
	sl.Set(2, "two")
	sl.Set(4, "four")
	
	// 查找
	if val, ok := sl.Get(2); ok {
		fmt.Println("Found:", val) // two
	}
	
	// 遍历
	fmt.Println("All elements:")
	for it := sl.Iterator(); it.Next(); {
		fmt.Printf("%v: %v\n", it.Key(), it.Value())
	}
	
	// 删除
	sl.Delete(1)
	
	// 检查长度
	fmt.Println("Length after deletion:", sl.Len()) // 3
}

这个库提供了简单易用的API，同时保持了跳表的高效特性，是Golang中实现有序集合的一个不错选择。

回到顶部