Golang实践----跳表

栏目: Go · 发布时间: 4年前

内容简介:跳跃链表是对链表的改进,链表虽然节省空间,但是查找时间复杂度为O(n),效率比较低。 跳跃链表的查找、插入、删除等操作的期望时间复杂度为O(logn),效率比链表提高了很多。 跳表的基本性质skipList结构如下目前只实现了针对int类型数据的接口,若使用其他类型,需要实现下面这个接口

目录

跳表简介

跳跃链表是对链表的改进,链表虽然节省空间,但是查找时间复杂度为O(n),效率比较低。 跳跃链表的查找、插入、删除等操作的期望时间复杂度为O(logn),效率比链表提高了很多。 跳表的基本性质

  1. 有很多层结构组成
  2. 每一层都是一个有序的链表
  3. 最底层(level 0)的链表包含所有元素
  4. 如果一个元素出现在level i的链表中,则在level i之下的链表都会出现
  5. 每个节点包含两个指针,一个指向同一链表的下一个元素,一个指向下面一层的元素

skipList

跳表示意图

以int类型,最大4层的跳表示意图如下

Golang实践----跳表

跳表实现简要介绍

skipList结构如下

type Node struct {  
	O        SkipListObj  
	forward  []*Node  
	curLevel int  
}

type SkipList struct {  
	head     *Node  
	length   int  
	maxLevel int  
	lockType int  
	lock     sync.Locker  
}

目前只实现了针对int类型数据的接口,若使用其他类型,需要实现下面这个接口

type SkipListObj interface {  
	Compare(obj SkipListObj) bool  
	PrintObj()  
}

其中Compare()表示数据大小比较,

一开始本想用Compare(obj interface{}) bool作为接口,但是编译报错,提示type interface {} is interface with no methods,于是改用了上面的接口

由于 Go 内置类型用户不能新建接口(会编译失败,对于int类型提示cannot define new methods on non-local type int),可以通过type给int取个别名来实现接口

type myInt int  

func (a *myInt) Compare(b skipList.SkipListObj) bool {  
	return *a < *b.(*myInt)  
}

PrintObj()用于打印数据的,主要是用于遍历显示跳表的Traverse(),对于int类型如下

func (a *myInt) PrintObj() {  
	fmt.Print(*a)  
}

CreateSkipList用于创建一个skip list,需要传入一个对任意其他对象Compare()函数都返回false的对象(例如对于example的实现就是传入最小的int整数),

还需要传入一个表示skip list最大层数以及一个可选的参数mode表示创建的skip list的锁类型,若

mode = 1, 则为互斥锁

mode = 2, 则为读写锁

其他为无锁

func CreateSkipList(minObj SkipListObj, args ...int) (*SkipList, error)

lockList主要用于在操作skip list前上锁,可根据配置来决定使用:

  1. 无锁
  2. 互斥锁
  3. 读写锁
func (s *SkipList) lockList(mode int) {  
	if s.lockType == 0 {  
		return  
	}  
	switch mode {  
	case 1:  
		s.lock.Lock()  
	case 2:  
		if s.lockType == 1 {  
			s.lock.Lock()  
		} else if s.lockType == 2 {  
			s.lock.(*sync.RWMutex).RLock()  
		}  
	default:  
		return  
	}  
}

unLockList相应地解锁 func (s *SkipList) unLockList(mode int)

Search()用于在skip list中查找指定的对象

func (s *SkipList) Search(o SkipListObj) (SkipListObj, error)

SearchRange()用于在skip list中按照指定范围查找对象

func (s *SkipList) SearchRange(minObj, maxObj SkipListObj) ([]SkipListObj, error)

Insert()用于在skip list中插入一个对象

思路是从最高层开始遍历直到不满足Compare()条件,对于example即是找到最后一个小于目标的节点,然后将新节点插入这个节点的后面

func (s *SkipList) Insert(obj SkipListObj) (bool, error)

func (s *SkipList) Insert(obj SkipListObj) (bool, error) {
	v, err := checkSkipListValid(s)
	if v == false {
		return false, err
	}

	var p *Node = s.head
	newNode := new(Node)
	newNode.O = obj
	newNode.forward = make([]*Node, s.maxLevel)
	level := s.createNewNodeLevel()

	s.lockList(1)
	defer s.unLockList(1)

	for i := s.maxLevel - 1; i >= 0; i-- {
		for {
			if p.forward[i] != nil && p.forward[i].O.Compare(obj) {
				p = p.forward[i]
			} else {
				break
			}
		}
		//find the last Node which match user defined Compare() condition in i level
		//insert new Node after the node
		if i <= level {
			newNode.forward[i] = p.forward[i]
			p.forward[i] = newNode
		}
	}
	newNode.curLevel = level
	s.length++

	return true, nil
}

createNewNodeLevel()用于Insert()方法中,为新对象产生其所在的层级

func (s *SkipList) createNewNodeLevel() int {  
	var level int = 0  

        rand.Seed(time.Now().UnixNano())  
        for {  
                if rand.Intn(2) == 1 || level >= s.maxLevel-1 {  
                        break  
                }  
                level++  
        }  
        return level  
}

Traverse()用于遍历打印skip list

func (s *SkipList) Traverse()

func (s *SkipList) Traverse() {
	v, _ := checkSkipListValid(s)
	if v == false {
		return
	}

	var p *Node = s.head

	s.lockList(2)
	defer s.unLockList(2)

	for i := s.maxLevel - 1; i >= 0; i-- {
		for {
			if p != nil {
				p.O.PrintObj()
				if p.forward[i] != nil {
					fmt.Print("-->")
				}
				p = p.forward[i]
			} else {
				break
			}
		}
		fmt.Println()
		p = s.head
	}
}

跳表使用介绍

首先必须调用CreateSkipList()创建一个skip list

创建一个最大10层无锁skip list

s, err := skipList.CreateSkipList(minObj, 10)

创建一个最大10层使用互斥锁的skip list

s, err := skipList.CreateSkipList(minObj, 10, 1)

创建一个最大10层使用读写锁的skip list

s, err := skipList.CreateSkipList(minObj, 10, 2)

插入一个对象(以myInt为例)

insertObj := new(myInt)
*insertObj = myInt(30)
t, err := s.Insert(insertObj)
if t == true {
	fmt.Println("insert obj ", *insertObj, " success")
} else {
	fmt.Printf("insert obj %d failed: ", *insertObj, err)
}

范围搜索skip list示例(以myInt为例)

func searchRangeExample(s *skipList.SkipList) {
	var minObj, maxObj myInt
	minObj = 0
	maxObj = 30
	sliceObj, err := s.SearchRange(&minObj, &maxObj)
	if err != nil {
		fmt.Print(err)
		return
	}
	fmt.Println("search range result:")
	for _, sobj := range sliceObj {
		fmt.Printf("%d ", *sobj.(*myInt))
	}
	fmt.Println()
}

使用LiteIDE(一个轻量级的Go IDE)运行example结果如下: Golang实践----跳表

github code

  • github code链接 - [github code链接](https://github.com/GrassInWind2019/skipList)

以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持 码农网

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

经济学原理(第7版):微观经济学分册+宏观经济学分册(套装共2册)

经济学原理(第7版):微观经济学分册+宏观经济学分册(套装共2册)

曼昆 (N.Gregory Mankiw) / 梁小民、梁砾 / 北京大学出版社 / 2015-5-1 / 128

《经济学原理(第7版):微观经济学分册+宏观经济学分册》是目前国内市场上最受欢迎的引进版经济学教材之一,其最大特点是它的“学生导向”,它更多地强调经济学原理的应用和政策分析,而非经济学模型。第7版在延续该书一贯风格的同时,对第6版作了全面修订和改进。大幅更新了“新闻摘录”“案例研究”等专栏,拓展了章后习题。一起来看看 《经济学原理(第7版):微观经济学分册+宏观经济学分册(套装共2册)》 这本书的介绍吧!

CSS 压缩/解压工具
CSS 压缩/解压工具

在线压缩/解压 CSS 代码

JSON 在线解析
JSON 在线解析

在线 JSON 格式化工具

HSV CMYK 转换工具
HSV CMYK 转换工具

HSV CMYK互换工具