关于skiplist,我也分享一个我的实现

https://github.com/gansidui/skiplist的实现用起来不太舒服,也分享一个我的实现。

我的实现特别之处在于添加了根据索引访问元素的功能。当然跳表比二叉树优越的连续遍历功能也不例外,提供一个迭代器。再一个,规定键为int64和string的组合,但是键和值是分开输入的,无接口要求。

具体文档如下:

package skiplist

import "github.com/hydra13142/container/skiplist"

TYPES

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

跳表类型

func New() *SkipList

创建一个跳表

func (this *SkipList) Len() int

返回跳表长度

func (this *SkipList) Reset()

清空重置跳表

func (this *SkipList) Insert(n int64, s string, v interface{}) bool

插入跳表新的值,如已存在相同键的值,不作修改并返回假

func (this *SkipList) InsertUpdate(n int64, s string, v interface{})

如该键不存在值则插入新值,如已存在则更新旧值

func (this *SkipList) Delete(n int64, s string) bool

删除跳表已有的值,如该键不存在值,返回假

func (this *SkipList) DeleteByIndex(n int) bool

删除跳表第n个值

func (this *SkipList) Search(n int64, s string) *Element

从跳表中搜索int64和string的参数为键

func (this *SkipList) SearchByIndex(n int) *Element

返回跳表中第n个值(下标从0开始)

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

遍历器

func (this *Element) Next() bool

向后遍历

func (this *Element) Prev() bool

向前遍历

func (this *Element) Key() (int64, string)

返回当前元素的键

func (this *Element) Val() interface{}

返回当前元素的值

func (this *Element) Set(v interface{})

设置当前元素的值

共 9 个回复


darksword

刚刚想起STL中有set和multiset,以及map,multimap之分, 我实现的那个恰好是multiset,当然也可以满足multimap的功能。 楼主实现的是set。 有个槽点就是C++可以运算符重载,Go没有,只能用接口来替代了。强制用户使用 “规定键为int64和string的组合” 这个貌似不太合适。 另外楼主的代码中按下标访问元素的函数的时间复杂度是O(n)。 另外楼主告诉我哪里用的不舒服了啊,我好去改改

# 0

snake117

@darksword 这个实现,按下标访问的时间复杂度也是O(log(n))。

set、map之类的,我个人觉得用skiplist就是用它的"有序",set有更好的办法,没必要用skiplist,我这个算是map。当然是限定了键类型的map。

# 1

snake117

@darksword 这个实现,按下标访问的时间复杂度也是O(log(n))。

set、map之类的,我个人觉得用skiplist就是用它的"有序",set有更好的办法,没必要用skiplist,我这个算是map。当然是限定了键类型的map。

# 2

darksword

楼主说的有道理,我那个也改了下,不过相当于c++ 的set, key是唯一的,可以把value都放到key里面存储就行了,实现Less接口接口,原因是考虑有些用途比如key就是value的情况,这样就没必要浪费内存来预留value interface{}了。 楼主的按下标访问实际上也解决了一个问题,就是获得指定rank的元素,当然还可以加一个函数,就是获取指定元素的rank,游戏排名常用。redis中这两个都有,我把它直接抄过来改为go了,哈哈

# 3

facat

@darkword 记得在哪里看过,说是interface{}不占内存。不过自己没验证过。

# 4

snake117

@darksword 我想了下,做了些修改。取消掉了Update和UpdateByIndex两个函数,同时还取消掉了NewIterator函数。

舍弃Iterator类型,新增Element类型。同时修改Search和SearchByIndex函数使之返回*Element。

Element可以获取键、值、索引,可以设置值,可以前后向遍历。

这样虽然丢掉了NewIterator的限定范围遍历的优点,必须使用者自己控制,好处是遍历更加灵活了。

同时丢掉俩Update方法,API简化了,Search方法的效率也更好了。

关于我不用接口的原因:

skiplist的目的是方便进行查询、搜索的。但是接口这个东西,尤其是你用的那个接口,要保证可靠性就必须进行类型推断,这个可是一笔大开销。如果换我,我肯定会采用“具有生成键的方法”接口,但即使如此,我觉得还是太拖累效率。考虑键多是基本类型,用浮点数的几乎木有,那么一个整数+一个字符串肯定能满足大多数要求了。

# 5

darksword

@snake117 用interface{}是为了保证通用,不过一般而言通用的东西效率都很难达到最优,得放到具体的业务中再去优化。我不是很清楚类型断言的开销到底有多大?

@facat interface{}肯定是占用内存的,不然怎么去保存任意值,即使如C中的void*一样,那也是4或8个字节。

# 6

snake117

@darksword

我用testing包测试了一下。10000个无序int64整数直接比较或者采用Less方法比较。后者消耗的时间是前者的十多倍。

# 7

darksword

嗯,我刚刚也测试了下,确实是十多倍,类型断言慢了这么多,好惊悚。。 不过单纯的比较一条语句的效率没啥意思,在具体场景中才好分析。

# 8