Golang 中国
func (this *SkipList) SearchByIndex(n int) *Node {
    if n < 0 || n >= this.long {
        return nil
    }
    n = n+1 // 换成n++就会出错,n+=1也出错
    for i, p := 0, this.root; p != nil; {
        if n == 0 {
            return p
        }
        if q := p.rgt; q != nil && q.cnt <= n {
            p, n = q, n-q.cnt
        } else {
            i, p = i+1, p.dad
        }
    }
    return nil
}

如题。很奇怪啊。
n=n+1时执行正确;
n++时执行失败;
n+=1时执行失败,但失败位置和n++不同。

go的优化是不是出现了啥bug啊?我用的go1.10


snake117 于 2018-03-14 02:16 修改
3 回复
heimeil
#1 heimeil • 2018-03-14 23:46

我在docker里用1.10试了一下,没问题。

这个不应该会有问题,再仔细debug一下吧,这要是真的有问题就非常致命了,排查出来真的有问题就及早向官方提issue

snake117
#2 snake117 • 2018-03-15 09:23

@heimeil

是真的,我用的win10-64bit系统,go1.10。

两个文件如下
skiplist.go

package skiplist

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

var (
    rd = rand.New(rand.NewSource(time.Now().Unix()))
    er = errors.New("skiplist: out of range")
)

type key struct {
    N int64
    S string
}

// 代表一个元素
type Node struct {
    cnt int
    key
    val *interface{}
    lft *Node
    rgt *Node
    dwn *Node
}

// 跳表类型
type SkipList struct {
    root *Node
    line []*Node
    path []int
    long int
}

func (x *key) cmp(y *key) int8 {
    switch {
    case x.N < y.N:
        return -1
    case x.N > y.N:
        return +1
    }
    switch {
    case x.S < y.S:
        return -1
    case x.S > y.S:
        return +1
    }
    return 0
}

// 创建一个跳表
func New() *SkipList {
    return &SkipList{new(Node), make([]*Node, 1), make([]int, 1), 0}
}

// 返回跳表长度
func (this *SkipList) Len() int {
    return this.long
}

// 清空重置跳表
func (this *SkipList) Reset() {
    var p, q, a, b *Node
    for p = this.root; p != nil; p = q {
        q = p.dwn
        for a = p; a != nil; a = b {
            b = a.rgt
            a.lft, a.rgt, a.dwn, a.val = nil, nil, nil, nil
        }
    }
    this.root = new(Node)
    this.line = make([]*Node, 1)
    this.path = make([]int, 1)
    this.long = 0
}

func (this *SkipList) search(x *key) (i int, c int) {
    for i, p := 0, this.root; p != nil; {
        t, q := int8(1), p.rgt
        if q != nil {
            t = q.key.cmp(x)
        }
        switch t {
        case -1:
            p, c = q, c+q.cnt
        case +1:
            this.line[i] = p
            this.path[i] = c
            i, p = i+1, p.dwn
        default:
            c += q.cnt
            this.line[i] = q
            this.path[i] = c
            return i, c
        }
    }
    return -1, c
}

func (this *SkipList) member(n int) (i int, c int) {
    n++
    c = n
    for i, p := 0, this.root; p != nil; {
        if n == 0 {
            this.line[i] = p
            this.path[i] = c
            return i, c
        }
        if q := p.rgt; q != nil && q.cnt <= n {
            p, n = q, n-q.cnt
            continue
        }
        this.line[i] = p
        this.path[i] = c - n
        i, p = i+1, p.dwn
    }
    return -1, c
}

func (this *SkipList) insert(i int, c int, k *key, v interface{}) {
    var p, q *Node
    t := int(rd.ExpFloat64()) + 1
    l := len(this.line)
    if t > l {
        u := make([]*Node, t)
        v := make([]int, t)
        copy(u[t-l:], this.line)
        copy(v[t-l:], this.path)
        for i := t - l - 1; i >= 0; i-- {
            p = new(Node)
            p.dwn = this.root
            this.root = p
            u[i] = p
        }
        this.line = u
        this.path = v
        l = t
    }
    i, c = 0, c+1
    for i = 0; i < l-t; i++ {
        if p = this.line[i].rgt; p != nil {
            p.cnt++
        }
    }
    q = &Node{}
    x := *k
    y := new(interface{})
    for ; i < l; i++ {
        p = this.line[i]
        q.dwn = new(Node)
        q = q.dwn
        q.cnt = c - this.path[i]
        q.key, q.val = x, y
        q.lft, q.rgt = p, p.rgt
        p.rgt = q
        if q.rgt != nil {
            q.rgt.lft = q
            q.rgt.cnt -= q.cnt - 1
        }
    }
    *y = v
    this.long++
}

func (this *SkipList) remove(t int) {
    i, l := 0, len(this.line)
    for ; i < t; i++ {
        p := this.line[i]
        if p.rgt != nil {
            p.rgt.cnt--
        }
    }
    for p := this.line[i]; i < l; i++ {
        q := p.dwn
        if p.lft != nil {
            p.lft.rgt = p.rgt
        }
        if p.rgt != nil {
            p.rgt.cnt += p.cnt - 1
            p.rgt.lft = p.lft
        }
        p.lft, p.rgt, p.dwn = nil, nil, nil
        p = q
    }
    this.long--
}

// 插入跳表新的值,如已存在相同键的值,不作修改并返回假
func (this *SkipList) Insert(n int64, s string, v interface{}) bool {
    k := &key{n, s}
    i, c := this.search(k)
    if i >= 0 {
        return false
    } else {
        this.insert(i, c, k, v)
    }
    return true
}

// 如该键不存在值则插入新值,如已存在则更新旧值
func (this *SkipList) InsertUpdate(n int64, s string, v interface{}) {
    k := &key{n, s}
    i, c := this.search(k)
    if i < 0 {
        this.insert(i, c, k, v)
    } else {
        *this.line[i].val = v
    }
}

// 删除跳表已有的值,如该键不存在值,返回假
func (this *SkipList) Delete(n int64, s string) bool {
    t, _ := this.search(&key{n, s})
    if t < 0 {
        return false
    } else {
        this.remove(t)
    }
    return true
}

// 删除跳表第n个值
func (this *SkipList) DeleteByIndex(n int) bool {
    if n < 0 || n >= this.long {
        return false
    }
    t, _ := this.member(n)
    if t < 0 {
        return false
    } else {
        this.remove(t)
    }
    return true
}

// 从跳表中搜索int64和string的参数为键
func (this *SkipList) Search(n int64, s string) *Node {
    c, k := 0, &key{n, s}
    for i, p := 0, this.root; p != nil; {
        t, q := int8(1), p.rgt
        if q != nil {
            t = q.key.cmp(k)
        }
        switch t {
        case -1:
            p, c = q, c+q.cnt
        case +1:
            i, p = i+1, p.dwn
        default:
            return q.rgt
        }
    }
    return nil
}

// 返回跳表中第n个值(下标从0开始)
func (this *SkipList) SearchByIndex(n int) *Node {
    if n < 0 || n >= this.long {
        return nil
    }
    n = n + 1 // 就是这一行
    for i, p := 0, this.root; p != nil; {
        if n == 0 {
            return p
        }
        if q := p.rgt; q != nil && q.cnt <= n {
            p, n = q, n-q.cnt
        } else {
            i, p = i+1, p.dwn
        }
    }
    return nil
}

// 获得前驱节点,用于简单迭代
func (this *Node) Prev() *Node {
    return this.lft
}

// 获得后继节点,用于简单迭代
func (this *Node) Next() *Node {
    return this.rgt
}

// 返回当前元素的键
func (this *Node) Key() (int64, string) {
    return this.N, this.S
}

// 返回当前元素的值
func (this *Node) Val() interface{} {
    return *this.val
}

// 设置当前元素的值
func (this *Node) Set(v interface{}) {
    *this.val = v
}

另一个文件是skiplist-try.go

package main

import (
    "fmt"
    "skiplist" // 这个根据你把shiplit放置的位置来改动
    "os"
)

type Void = struct{}

func main() {
    t := skiplist.New()
    for i := 2; i < 6; i++ {
        t.Insert(int64(i), "", Void{})
    }
    p := t.SearchByIndex(0)
    xs := [10000]int64{}
    for i := 0; i < 10000; i++ {
        k, _ := p.Key()
        xs[i] = k
        t.Insert(k*2, "", Void{})
        t.Insert(k*3, "", Void{})
        t.Insert(k*5, "", Void{})
        p = p.Next()
    }
    file, _ := os.Create("output2.txt")
    defer file.Close()
    fmt.Fprintln(file, xs)
}

你可以测试一下。

heimeil
#3 heimeil • 2018-03-15 22:02

我用go1.9.2 windows/amd64简单跑了一下你的代码,多跑几次发现有几率会出现空指针异常,可以肯定你的实现是有问题的,debug断点定位到main的for循环里的p.Key(),p为nil,没时间帮你看细节,你还是自己梳理一下逻辑吧,问题应该不是在n怎么+1上面。

需要 登录 后方可回复, 如果你还没有账号你可以 注册 一个帐号。