golang skiplist(跳表)实现

栏目: IT技术 · 发布时间: 4年前

内容简介:首先来了解一下跳表的概念,跳表中的表指的是链表,所以宏观上来看跳表是一种链表结构,那么它与传统的链表有什么不同呢?一般的单链表如果我们需要查找第n个元素,那么就需要从头节点开始一个一个的遍历n次,时间复杂读就是O(n),而跳表就是在单链表之上做了一些优化,使时间复杂度达到O(logn)。在O(logn)复杂度内查找元素,我们不难想到其他的数据结构,avl树,红黑树,b树,b+树之类。但是这些树状结构有个共性就是需要在元素数量发生变化的时候保持平衡才能继续维持性能,所以就需要做一个额外的操作,旋转。而旋转一方

前言

首先来了解一下跳表的概念,跳表中的表指的是链表,所以宏观上来看跳表是一种链表结构,那么它与传统的链表有什么不同呢?一般的单链表如果我们需要查找第n个元素,那么就需要从头节点开始一个一个的遍历n次,时间复杂读就是O(n),而跳表就是在单链表之上做了一些优化,使时间复杂度达到O(logn)。

在O(logn)复杂度内查找元素,我们不难想到其他的数据结构,avl树,红黑树,b树,b+树之类。但是这些树状结构有个共性就是需要在元素数量发生变化的时候保持平衡才能继续维持性能,所以就需要做一个额外的操作,旋转。而旋转一方面增加了代码实现的复杂性,同时也降低了在频繁做增删操作时,树的性能。

而跳表则是一种代码实现简单,效率相近的数据结构。既然跳表这么好,那么接下来看一下跳表在单链表的基础上做了什么优化?

跳表

golang skiplist(跳表)实现

1.png

跳表的结构如上图所示,可以看到跳表是分层的链表,底层是真正保存的数据,传统的单链表,而之上的层可以理解为下层节点的索引。所以这也是典型的空间换时间的优化方式。那么有人要问了,当插入节点的时候,什么时候分层呢?相隔几个节点的时候分层呢?这的确是一个很难的问题,我也不知道到底什么时候分层好,几个节点分层好?计算机可能也不知道。但是问题总得解决,其实当插入一个节点的时候,这时候不就是分层与不分层两个选择吗?那就“抛硬币”吧。

是的,跳表也觉得抛硬币是个好办法,简单有效。一般会设置一个概率值(0.5),满足概率就加层,不满足就什么都不做,另外跳表每一层的元素都是有序的。

so ,跳表 = 链表 + 有序 + 概率分层

接下来,简单描述一下跳表做增删查的流程:

ps:head 节点为左上第一个节点,tail 节点为右上第一个节点

Get:如上图,如果要查找12这个元素,那么就从head节点开始,如果下一个节点比12小继续在当前层向后移动,如果下一个节点比12大或者nil,那么就向下移动,从它的下一层开始查找,以此类推最终会落到底层,直到找到12.

Insert:插入15,首先找到离15最近,比15小的节点12,然后将节点插入底层(单链表的插入操作)。判断是否需要分层,不需要返回。需要的话自底向上一层一层插入节点

Remove:同样的删除15,首先找到离15最近,比15小的节点12,然后将节点在底层删除,如果有上层节点,继续删除。

talk is cheap,show you the code:

package skipList

import (
    "fmt"
    "math"
    "math/rand"
    "time"
)

const UP_LEVELS_ABILITY = 500
const UP_LEVELS_TOTAL = 1000

type skipListNode struct {
    score int64
    val   interface{}
    next  *skipListNode
    pre   *skipListNode
    up    *skipListNode
    down  *skipListNode
}

type skipList struct {
    head   *skipListNode
    tail   *skipListNode
    size   int
    levels int
}

func NewSkipList() *skipList {
    sl := new(skipList)
    sl.head = new(skipListNode)
    sl.tail = new(skipListNode)
    sl.head.score = math.MinInt64
    sl.tail.score = math.MaxInt64

    sl.head.next = sl.tail
    sl.tail.pre = sl.head

    sl.size = 0
    sl.levels = 1

    return sl
}

func (sl *skipList) Size() int {
    return sl.size
}

func (sl *skipList) Levels() int {
    return sl.levels
}

func (sl *skipList) Get(score int64) interface{} {
    node := sl.findNode(score)
    if node.score == score {
        return node.val
    } else {
        return nil
    }
}

func (sl *skipList) Insert(score int64, val interface{}) {
    f := sl.findNode(score)
    if f.score == score {
        f.val = val
        return
    }
    curNode := new(skipListNode)
    curNode.score = score
    curNode.val = val

    sl.insertAfter(f, curNode)

    rander := rand.New(rand.NewSource(time.Now().UnixNano()))

    curlevels := 1
    for rander.Intn(UP_LEVELS_TOTAL) < UP_LEVELS_ABILITY {
        curlevels++
        if curlevels > sl.levels {
            sl.newlevels()
        }

        for f.up == nil {
            f = f.pre
        }
        f = f.up
        tmpNode := &skipListNode{score: score}

        curNode.up = tmpNode
        tmpNode.down = curNode
        sl.insertAfter(f, tmpNode)

        curNode = tmpNode
    }

    sl.size++
}

func (sl *skipList) Remove(score int64) interface{} {
    f := sl.findNode(score)
    if f.score != score {
        return nil
    }
    v := f.val

    for f != nil {
        f.pre.next = f.next
        f.next.pre = f.pre
        f = f.up
    }
    return v
}

func (sl *skipList) newlevels() {
    nhead := &skipListNode{score: math.MinInt64}
    ntail := &skipListNode{score: math.MaxInt64}
    nhead.next = ntail
    ntail.pre = nhead

    sl.head.up = nhead
    nhead.down = sl.head
    sl.tail.up = ntail
    ntail.down = sl.tail

    sl.head = nhead
    sl.tail = ntail
    sl.levels++
}

func (sl *skipList) insertAfter(pNode *skipListNode, curNode *skipListNode) {
    curNode.next = pNode.next
    curNode.pre = pNode
    pNode.next.pre = curNode
    pNode.next = curNode
}

func (sl *skipList) findNode(score int64) *skipListNode {
    p := sl.head

    for p != nil {
        if p.score == score {
            if p.down == nil {
                return p
            }
            p = p.down
        } else if p.score < score {
            if p.next.score > score {
                if p.down == nil {
                    return p
                }
                p = p.down
            } else {
                p = p.next
            }
        }
    }
    return p
}

func (sl *skipList) Print() {

    mapScore := make(map[int64]int)

    p := sl.head
    for p.down != nil {
        p = p.down
    }
    index := 0
    for p != nil {
        mapScore[p.score] = index
        p = p.next
        index++
    }
    p = sl.head
    for i := 0; i < sl.levels; i++ {
        q := p
        preIndex := 0
        for q != nil {
            s := q.score
            if s == math.MinInt64 {
                fmt.Printf("%s", "BEGIN")
                q = q.next
                continue
            }
            index := mapScore[s]
            c := (index - preIndex - 1) * 6
            for m := 0; m < c; m++ {
                fmt.Print("-")
            }
            if s == math.MaxInt64 {
                fmt.Printf("-->%s\n", "END")
            } else {
                fmt.Printf("-->%3d", s)
                preIndex = index
            }
            q = q.next
        }
        p = p.down
    }
}

最后的print加了一个打印,方便更直观的观察这个结构,效果如下:

package main

import (
    "skipList"
)

func main() {
    sk := skipList.NewSkipList()

    sk.Insert(100, "lala")
    sk.Insert(11, "sx")
    sk.Insert(22, "11")
    sk.Insert(3, "dd")
    sk.Insert(80, "bb")
    sk.Insert(77, "bb")
    sk.Insert(6, "bb")
    sk.Insert(88, "bb")
    sk.Insert(33, "bb")
    sk.Insert(44, "bb")

    //fmt.Println(sk.Get(22))
    //fmt.Println(sk.Get(55))
    //fmt.Println(sk.Remove(22))
    //fmt.Println(sk.Get(22))
    //fmt.Println(sk.Size())
    //fmt.Println(sk.Layout())
    sk.Print()
}
golang skiplist(跳表)实现

2.png

有用的话,动动小手,点个赞。

有疑问加站长微信联系

golang skiplist(跳表)实现

以上所述就是小编给大家介绍的《golang skiplist(跳表)实现》,希望对大家有所帮助,如果大家有任何疑问请给我留言,小编会及时回复大家的。在此也非常感谢大家对 码农网 的支持!

查看所有标签

猜你喜欢:

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

游戏编程模式

游戏编程模式

Robert Nystrom / GPP翻组 / 人民邮电出版社 / 2016-9-1 / 61.4

游戏开发一直是热门的领域,掌握良好的游戏编程模式是开发人员的应备技能。本书细致地讲解了游戏开发需要用到的各种编程模式,并提供了丰富的示例。 全书共分20章,通过三大部分内容全面介绍了与游戏编程模式相关的各类知识点。首部分介绍了基础知识和框架;第二部分深入探索设计模式,并介绍了模式与游戏开发之间的关联;第三部分介绍了13种有效的游戏设计模式。 本书提供了丰富的代码示例,通过理论和代码示例......一起来看看 《游戏编程模式》 这本书的介绍吧!

随机密码生成器
随机密码生成器

多种字符组合密码

html转js在线工具
html转js在线工具

html转js在线工具

HEX HSV 转换工具
HEX HSV 转换工具

HEX HSV 互换工具