程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> Go語言實現跳表(SkipList)

Go語言實現跳表(SkipList)

編輯:C++入門知識

Go語言實現跳表(SkipList)


跳表(skiplist)在redis/levelDB中屬於核心數據結構,我簡單粗暴的用Golang實現了下。

就我的簡單理解來說,就一個普通的鏈表,在insert時,通過Random_level(),把一層變成很多層,

越上數據越小,跨度越大。 查找時從上往下找,用空間換時間。

記下測試代碼:

 

package main

import (
	"fmt"
	//"github.com/xclpkg/algorithm"
	"math/rand"
)

func main() {

	slt := NewSkipList()
	for i := 100; i > 0; i-- {
		slt.Insert(i)
	}

	slt.PrintSkipList()

	slt.Search(20)

	slt.Search(36)

	slt.Search(93)

	slt.Delete(55)

	slt.PrintSkipList()

}

const SKIPLIST_MAXLEVEL = 8 //32
const SKIPLIST_P = 4

type SkipList struct {
	Header []List
	Level  int
}

func NewSkipList() *SkipList {
	return &SkipList{Level: 1, Header: make([]List, SKIPLIST_MAXLEVEL)}

}

func (skipList *SkipList) Insert(key int) {
	update := make(map[int]*Node)

	for i := len(skipList.Header) - 1; i >= 0; i-- {
		if skipList.Header[i].Len() > 0 {
			for e := skipList.Header[i].Front(); e != nil; e = e.Next() {
				if e.Value.(int) >= key {
					update[i] = e
					break
				}
			}
		} //Heaer[lv].List
	} //Header Level

	level := skipList.Random_level()
	if level > skipList.Level {
		skipList.Level = level
	}

	for i := 0; i < level; i++ {
		if v, ok := update[i]; ok {
			skipList.Header[i].InsertBefore(key, v)
		} else {
			skipList.Header[i].PushBack(key)
		}
	}

}

func (skipList *SkipList) Search(key int) *Node {

	for i := len(skipList.Header) - 1; i >= 0; i-- {
		if skipList.Header[i].Len() > 0 {
			for e := skipList.Header[i].Front(); e != nil; e = e.Next() {
				switch {
				case e.Value.(int) == key:
					fmt.Println("Found level=", i, " key=", key)
					return e
				case e.Value.(int) > key:
					break
				}
			} //end for

		} //end if

	} //end for
	return nil
}

func (skipList *SkipList) Delete(key int) {
	for i := len(skipList.Header) - 1; i >= 0; i-- {
		if skipList.Header[i].Len() > 0 {
			for e := skipList.Header[i].Front(); e != nil; e = e.Next() {
				switch {
				case e.Value.(int) == key:
					fmt.Println("Delete level=", i, " key=", key)
					skipList.Header[i].remove(e)

				case e.Value.(int) > key:
					break
				}
			} //end for

		} //end if

	} //end for

}

func (skipList *SkipList) PrintSkipList() {

	fmt.Println("\nSkipList-------------------------------------------")
	for i := SKIPLIST_MAXLEVEL - 1; i >= 0; i-- {
		fmt.Println("level:", i)
		if skipList.Header[i].Len() > 0 {
			for e := skipList.Header[i].Front(); e != nil; e = e.Next() {
				fmt.Printf("%d ", e.Value)
			} //end for
		} //end if
		fmt.Println("\n--------------------------------------------------------")
	} //end for
}

func (skipList *SkipList) Random_level() int {

	level := 1
	for (rand.Int31()&0xFFFF)%SKIPLIST_P == 0 {
		level += 1
	}
	if level < SKIPLIST_MAXLEVEL {
		return level
	} else {
		return SKIPLIST_MAXLEVEL
	}
}

//////////////////////////////////////////////////////

type Node struct {
	next, prev *Node
	list       *List

	Value interface{}
}

type List struct {
	root Node
	len  int
}

func (node *Node) Next() *Node {
	if p := node.next; node.list != nil && p != &node.list.root {
		return p
	}
	return nil
}

func (node *Node) Prev() *Node {
	if p := node.prev; node.list != nil && p != &node.list.root {
		return p
	}
	return nil
}

func (list *List) Init() *List {
	list.root.next = &list.root
	list.root.prev = &list.root
	list.len = 0
	return list
}

func New() *List {
	return new(List).Init()
}

func (list *List) lazyInit() {
	if list.root.next == nil {
		list.Init()
	}
}

func (list *List) Len() int {
	return list.len
}

func (list *List) remove(e *Node) *Node {
	e.prev.next = e.next
	e.next.prev = e.prev
	e.next = nil
	e.prev = nil
	e.list = nil
	list.len--
	return e
}

func (list *List) Remove(e *Node) interface{} {
	if e.list == list {
		list.remove(e)
	}
	return e.Value
}

func (list *List) Front() *Node {
	if list.len == 0 {
		return nil
	}
	return list.root.next
}

func (list *List) Back() *Node {
	if list.len == 0 {
		return nil
	}
	return list.root.prev
}

func (list *List) insert(e, at *Node) *Node {
	n := at.next
	at.next = e
	e.prev = at
	e.next = n
	n.prev = e
	e.list = list

	list.len++
	return e
}

func (list *List) insertValue(v interface{}, at *Node) *Node {

	return list.insert(&Node{Value: v}, at)
}

func (list *List) InsertBefore(v interface{}, mark *Node) *Node {
	if mark.list != list {
		return nil
	}
	return list.insertValue(v, mark.prev)
}

func (list *List) PushBack(v interface{}) *Node {
	list.lazyInit()
	return list.insertValue(v, list.root.prev)
}

效果:

SkipList-------------------------------------------
level: 7

--------------------------------------------------------
level: 6

--------------------------------------------------------
level: 5

--------------------------------------------------------
level: 4

--------------------------------------------------------
level: 3
93
--------------------------------------------------------
level: 2
36 93
--------------------------------------------------------
level: 1
6 10 22 23 25 36 42 47 48 54 55 61 72 75 78 82 89 93
--------------------------------------------------------
level: 0
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30
 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 5
7 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83
84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100
--------------------------------------------------------
Found level= 0  key= 20
Found level= 2  key= 36
Found level= 3  key= 93
Delete level= 1  key= 55
Delete level= 0  key= 55

SkipList-------------------------------------------
level: 7

--------------------------------------------------------
level: 6

--------------------------------------------------------
level: 5

--------------------------------------------------------
level: 4

--------------------------------------------------------
level: 3
93
--------------------------------------------------------
level: 2
36 93
--------------------------------------------------------
level: 1
6 10 22 23 25 36 42 47 48 54 61 72 75 78 82 89 93
--------------------------------------------------------
level: 0
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30
 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 56 57 5
8 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84
85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100
--------------------------------------------------------
搞定。

 

 

 

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved