go 数据结构与算法

go 数据结构与算法

1.1 链表

链表是一种数据结构,单向列表每个元素后面都有一个next指向下一个元素，双向列表还有一个prev指向上一个元素
我们定义一个链表：

func main() {
	list := List{}
	list.Add(1)
	list.Add(8)
	list.Add(4)
	list.Add(3)
	list.Add(5)
	list.Travs()
}

//链表的一个元素
type Node struct{
	Info int
	Next *Node //自己套自己，形成链表
}

//链表
type List struct{
	Head *Node
	Len int
}
// 1 > 8 > 4 > 3 > 5
func (list *List) Add (ele int) {
	node := &Node{Info: ele,Next: nil} //取指针，因为需要放到List里面去的
	//如果长度为0，那么说明加的是第一个元素，直接用node赋值
	if list.Len == 0 {
		list.Head = node
	} else {
		head := list.Head
		for i := 1;i < list.Len;i++ {
			head = head.Next
		}
		head.Next = node
	}
	list.Len += 1
}

func (list List) Travs() {
	if list.Len == 0 {
		return
	}
	head := list.Head
	for i := 1;i < list.Len;i++{
		fmt.Printf("%d ",head.Info)
		head = head.Next
	}
	fmt.Printf("%d ",head.Info)
	fmt.Println()
}

链表的应用案例

链表的一个应用案例。LRU(Least Recently Used, 最近最少使用)缓存淘汰的总体思路：缓存的key放到链表中，头部的元素表示最近刚使用。

如果命中缓存，从链表中找到对应的key，移到链表头部。
如果没命中缓存：

  • 如果缓存容量没超，放入缓存，并把key放到链表头部。
  • 如果超出缓存容量，删除链表尾部元素，再把key放到链表头部。
//类似redis缓存，最新访问的元素放到最前面
// 1 > 8 > 7 >5
func (list *List) Visit (ele int) {
	//如果我们Visit查询一个元素，长度为0，说明缓存为0，直接return
	if list.Len == 0 {
		return
	}
	head := list.Head
	for {
		if head == nil{
			break
		}
		//如果不是我们要查的哪个ele
		if head.Info != ele {
			//就跳转到下一个head
			head = head.Next
		} else {
			break
		}
	}
	//这时候可能在列表中查到ele了，也可能没查到
	//如果没查到head应该是nil,这里我们假如查的数字是7
	if head == nil {
		return
	} else {
		post := head.Next //5  7的下一个元素就是5
		pre := head.Prev //8 7的上一个元素是8
		pre.Next = post //让8的下一个元素指向5，相当于把7移除了
		post.Prev = pre //让5的上一个元素指向8

		head.Next = list.Head //把7的下一个元素指向list.Head ,也就是指向开头的1
		list.Head.Prev = head //让1的前一个元素变成7  head=7
		list.Head = head //把list.Head改成7
	}
}

注：上面是我们自己写的一个双向链表，体验了他的工作状态，那我们实际工作中，可以调用go自带的双向链表完成上述功能

//官方自带的双向链表功能
package main
//官方自带的双向链表
import (
	"container/list"
	"fmt"
)

func main() {
	//用官方自带创建一个空的双向链表
	lst := list.New()
	//Pushback往链表末尾追加
	lst.PushBack(4)
	lst.PushBack(6)
	lst.PushBack(2)
	TravList(lst)
	lst.PushFront(3)
	TravList(lst)
}
func TravList(lst *list.List) {
	//我们上面的例子用的Head结构体，这里是Front
	head := lst.Front()
	for head.Next() != nil {
		//Value对应上面的Info,这个value是个interface
		fmt.Printf("%v ",head.Value)
		head = head.Next()
	}
	fmt.Printf("%v ",head.Value)
	fmt.Println()
}

RING回环链表


ring的应用：基于滑动窗口的统计。比如最近100次接口调用的平均耗时、最近10笔订单的平均值、最近30个交易日股票的最高点。ring的容量即为滑动窗口的大小，把待观察变量按时间顺序不停地写入ring即可。

func RingDaemon() {
        //定义单向链表回环的容量为10
	ring := ring.New(10)
        //插入100个元素，只会记录最后10个
	for i := 0;i < 100;i++ {
		ring.Value = i
		ring = ring.Next()
	}
	sum := 0
        //ring.Do遍历整个循环，对每个元素采取的处理措施由回调函数func(i interface{}) {}来定义
	ring.Do(func(i interface{}) {
		fmt.Printf("%v ",i)
		num := i.(int)
		sum += num
	})
	fmt.Println()
	fmt.Println(sum)
}

2.1 栈

栈是一种先进后出的数据结构，push把元素压入栈底，pop弹出栈顶的元素。编程语言的编译系统也用到了栈的思想

go自带的List已经包含了栈的功能，这里实现一个线程安全的栈。
这里可以用双向列表就可以实现了，比如斐波那契函数，用go写，使用栈和不使用栈，可以减少重复计算的部分几百倍

3.1 堆

堆是一棵二叉树。大根堆即任意节点的值都大于等于其子节点。反之为小根堆。堆得底层就是数组
用数组来表示堆，下标为 i 的结点的父结点下标为(i-1)/2，其左右子结点分别为 (2i + 1)、(2i + 2)。
如图， 21+1就是3 21+2就是4 1的子节点是3和4

小根堆。父节点比子节点小

大根堆，父节点比子节点大

给我一个数组，把它调整为小根堆，这个过程称为堆的构建过程，构建过程遵循从右向左，从下到上
每当有元素调整下来时，要对以它为父节点的三角形区域进行调整。

删除堆顶

元素个数和层数有关系， 假如有x层， 元素个数是y， 2^x-1=y,例如有三层，那么就是 8-1=7个元素,相反 层数x=log2^n+1

下面讲几个堆的应用。
堆排序

  • 构建堆O(N)。
  • 不断地删除堆顶O(NlogN)。
    求集合中最大的K个元素
  • 用集合的前K个元素构建小根堆。
  • 逐一遍历集合的其他元素，如果比堆顶小直接丢弃；否则替换掉堆顶，然后向下调整堆。
    把超时的元素从缓存中删除
  • 按key的到期时间把key插入小根堆中。随时刷新
  • 周期扫描堆顶元素，如果它的到期时间早于当前时刻，则从堆和缓存中删除，然后向下调整堆。 ??golang中的container/heap实现了小根堆，但需要自己定义一个类，实现以下接口：
  • Len() int
  • Less(i, j int) bool
  • Swap(i, j int)
  • Push(x interface{})
  • Pop() x interface{}
func main() {
	testPriorityQueue()
}

type Item struct {
	Value    string
	priority int //优先级，数字越大，优先级越高
}
type PriorityQueue []*Item

func (pq PriorityQueue) Len() int {
	return len(pq)
}

func (pq PriorityQueue) Less(i, j int) bool {
	return pq[i].priority > pq[j].priority //golang默认提供的是小根堆，而优先队列是大根堆，所以这里要反着定义Less
}

func (pq PriorityQueue) Swap(i, j int) {
	pq[i], pq[j] = pq[j], pq[i]
}

//往slice里append,需要传slice指针
func (pq *PriorityQueue) Push(x interface{}) {
	item := x.(*Item)
	*pq = append(*pq, item)
}

//让slice指向新的子切片，需要传slice指针
func (pq *PriorityQueue) Pop() interface{} {
	old := *pq
	n := len(old)
	item := old[n-1]   //数组最后一个元素
	*pq = old[0 : n-1] //去掉最一个元素
	return item
}
func testPriorityQueue() {
	pq := make(PriorityQueue,0,10) //定义一个数组
	pq.Push(&Item{"A",3}) //往数组中添加元素
	pq.Push(&Item{"B",9}) //往数组中添加元素
	pq.Push(&Item{"C",6}) //往数组中添加元素
	heap.Init(&pq) //根据数组中的元素构建堆，这里默认是大根堆
	heap.Push(&pq,&Item{"D",5}) //通过heap添加元素
	for pq.Len() > 0 {
		fmt.Println(heap.Pop(&pq)) //通过heap删除堆顶元素
	}
}

4.1 代码总结

4.1.1 用map和链表实现LRU缓存

func main() {
	testUrl()
}
type UrlCache struct{
	cache map[int]int
	lst list.List
	Cap int //容量上限
}
//初始化函数
func NewUrlCache(cap int) *UrlCache {
	lru := new(UrlCache)
	lru.Cap = cap
	lru.cache = make(map[int]int,cap)
	lru.lst = list.List{}
	return lru
}
//开始写代码之前，我们要考虑，缓存我们需要增加和获取


func (url *UrlCache) Add(key,value int) {
		//先判断长度是否大于容量cap上限
	if len(url.cache) < url.Cap {
		url.cache[key] = value
		//添加到数组首位
		url.lst.PushFront(key)
	} else {
		//如果长度等于cap的时候，先从缓存中淘汰一个，再把key，value加到缓存中去
		//获取末尾最后一个map
		back := url.lst.Back()
		delete(url.cache,back.Value.(int))
		url.lst.Remove(back)
		//然后把新增的key，value加到map里面去
		url.cache[key] = value
		//添加到数组首位
		url.lst.PushFront(key)
	}
}

func (url *UrlCache) Get(key int) (int, bool) {
	value,exists := url.cache[key]
	ele := url.Find(key)
	if ele != nil {
		url.lst.MoveToFront(ele)
	}
	return value,exists
}

func (url *UrlCache) Find(key int) *list.Element {
	if url.lst.Len() == 0 {
		return nil
	}
	head := url.lst.Front()
	for {
		if head == nil {
			break
		}
		if head.Value.(int) == key {
			return head
		} else {
			head = head.Next()
		}
	}
	return nil
}

func testUrl() {
	//初始化一个容量为10的链表
	url := NewUrlCache(10)
	//for循环添加10个元素
	for i := 0;i < 10;i++{
		url.Add(i,i) //9 8 7 6 5 4 3 2 1
	}
	//for循环读取下
	for i := 0;i < 10;i += 2{
		url.Get(i) // 8 6 4 2 0 9 7 5 3 1
		fmt.Printf("Get:%d\n",i)
	}
	//for循环再插入10个
	for i := 10;i < 15;i++{
		fmt.Printf("Add %d : %d\n",i,i)
		url.Add(i,i) //14 13 12 11 10 8 6 4 2 0  最后5个没了 9 7 5 3 1
	}
	//for循环再读10个，这次可能有不存在的元素了
	for i := 0;i < 10;i ++{
		_,exists := url.Get(i)
		fmt.Printf("key %d exists %t\n",i,exists) //9 7 5 3 1 不存在了，因为最后5个被删除了
	}
}

4.1.2 用map和堆实现超时缓存

package main

import (
	"container/heap"
	"fmt"
	"time"
)

func main() {
	testTimeoutCache()
}

type HeapNode struct{
	value int //对应map里面的key
	deadline int //到期时间戳，精确到秒
}

type Heap []*HeapNode

func (heap Heap) Len() int{
	return len(heap)
}
//默认是小根堆，和我们的需求一致
func (heap Heap) Less(i,j int) bool{
	return heap[i].deadline < heap[j].deadline
}
//交换i和j的元素
func (heap Heap) Swap(i,j int){
	heap[i],heap[j] = heap[j],heap[i]
}
//添加元素
func (heap *Heap) Push(x interface{}){
	//node转换成HeapNode类型
	node := x.(*HeapNode)
	*heap = append(*heap,node)
}
func (heap *Heap) Pop() (x interface{}){
	//获取总长度
	n :=len(*heap)
	//获取最后一个元素
	last := (*heap)[n-1]
	//重新定义切片，和python一样，是包前不包后的
	*heap = (*heap)[0:n-1]
	//返回最后一个元素
	return last
}

type TimeoutCache struct{
	cache map[int]interface{}
	hp Heap
}

func NewTimeoutCache(cap int) *TimeoutCache {
	tc := new(TimeoutCache)
	tc.cache = make(map[int]interface{},cap)
	//初始化
	tc.hp = Heap{}
	heap.Init(&tc.hp) //包装升级，从一个常规的切片升级为堆
	return tc
}

func (tc *TimeoutCache) Add(key int,value interface{},life int) {
	//直接把key value加入map
	tc.cache[key] = value
	//计算deadline，然后把key和deadline放入堆
	deadline := int(time.Now().Unix()) + life
	tc.cache[key] = value
	node := &HeapNode{value:key,deadline:deadline}
	heap.Push(&tc.hp,node)
	fmt.Printf("heap len is %d\n",tc.hp.Len())
}

func (tc TimeoutCache) Get(key int) (interface{},bool) {
	value,exists := tc.cache[key]
	return value,exists
}

func (tc *TimeoutCache) Taotai() {
	for {
		if tc.hp.Len() == 0 {
			time.Sleep(100 * time.Millisecond)
			continue
		}
		now := int(time.Now().Unix())
		top := tc.hp[0]
		fmt.Printf("top value is %d\n",top.value)
		fmt.Println(top.deadline)
		fmt.Println(now)
		if top.deadline < now {
			fmt.Printf(">>>>>>>>>>>>>>>>>")
			heap.Remove(&tc.hp,0) //移除第i个元素
			//heap.Pop(&tc.hp)
			delete(tc.cache,top.value)
		} else { //堆顶还没有到期的
			time.Sleep(3 * time.Second) //休息1秒，避免耗尽cpu的一核
			fmt.Println("<<<<<<<<<<<<<<<<<<<<<")
		}
	}
}

func testTimeoutCache() {
	tc := NewTimeoutCache(10)
	go tc.Taotai() //在子协程里面执行，不影响主进程

	tc.Add(1,'1',1)
	tc.Add(2,'2',2)
	tc.Add(3,'3',3)

	time.Sleep(1)
	for  _,key := range []int{1,2,3} {
		_,exists := tc.Get(key)
		fmt.Printf("key %d exists %t\n",key,exists)
	}
	fmt.Printf("head last len is %d",tc.hp.Len())
}
Go

相关

MongoDB

expected Long (got Float)

Django url路由分配

Go中的fmt几种输出的区别和格式化方式

【Mysql学习】django.db.utils.OperationalError: (1045:Access denied for user 'roo

google icons 的使用 和 css 设置图标为 loading 状态

web框架们~Django~Flask~Tornado

Django Rest Framework的使用

Hugo 建站经验之谈

Go入门笔记-20 访问redis

MongoDB 数据类型

LevelDB Java&Go实践

标签