golang 提供了几个简单的容器供我们使用,本文在介绍几种Golang 容器的基础上,实现一个基于Golang 容器的LRU算法。
容器介绍 Golang 容器位于 container 包下,提供了三种包供我们使用,heap、list、ring. 下面我们分别学习。
heap heap 是一个堆的实现。一个堆正常保证了获取/弹出最大(最小)元素的时间为log n、插入元素的时间为log n. golang的堆实现接口如下:
1 2 3 4 5 6 type Interface interface {sort.Interface Push(x interface {}) Pop() interface {} }
heap 是基于 sort.Interface 实现的。
1 2 3 4 5 6 7 8 9 10 type Interface interface {Len() int Less(i, j int ) bool Swap(i, j int ) }
因此,如果要使用官方提供的heap,需要我们实现如下几个接口 :
1 2 3 4 5 Len() int {} Less(i, j int ) bool {} Swap(i, j int ) Push(x interface {}){} Pop() interface {}
然后在使用时,我们可以使用如下几种方法 :
1 2 3 4 5 6 7 8 9 10 func Init (h Interface) {}func Push (h Interface, x interface {}) {}func Pop (h Interface) interface {} {}func Remove (h Interface, i int ) interface {} {}func Fix (h Interface, i int ) {}
list 链表 list 实现了一个双向链表,链表不需要实现heap 类似的接口,可以直接使用。
链表的构造和使用:
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 func New () *List {}func (l *List) Len () int {}func (l *List) Front () *Element {}func (l *List) Back () *Element {}func (l *List) Remove (e *Element) interface {} {}func (l *List) PushFront (v interface {}) *Element {}func (l *List) PushBack (v interface {}) *Element {}func (l *List) InsertBefore (v interface {}, mark *Element) *Element {}func (l *List) InsertAfter (v interface {}, mark *Element) *Element {}func (l *List) MoveToFront (e *Element) {}func (l *List) MoveToBack (e *Element) {}func (l *List) MoveBefore (e, mark *Element) {}func (l *List) MoveAfter (e, mark *Element) {}func (l *List) PushBackList (other *List) {}func (l *List) PushFrontList (other *List) {}
我们可以通过 Value 方法访问 Element 中的元素。除此之外,我们还可以用下面方法做链表遍历:
1 2 3 4 func (e *Element) Next () *Element {}func (e *Element) Prev () *Element {}
队列的遍历:
1 2 3 4 for e := l.Front(); e != nil ; e = e.Next() { }
ring 循环列表 container 中的循环列表是采用链表实现的。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 func New (n int ) *Ring {}func (r *Ring) Next () *Ring {}func (r *Ring) Prev () *Ring {}func (r *Ring) Move (n int ) *Ring {}func (r *Ring) Link (s *Ring) *Ring {}func (r *Ring) Unlink (n int ) *Ring {}func (r *Ring) Len () int {}func (r *Ring) Do (f func (interface {}) ) {}
访问Ring 中元素,直接 Ring.Value 即可。
容器的使用 LRU 算法 (Least Recently Used),在做缓存置换时用的比较多。逐步淘汰最近未使用的cache,而使我们的缓存中持续保持着最近使用的数据。下面,我们通过map 和 官方包中的双向链表实现一个简单的lru 算法,用来熟悉golang 容器的使用。
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 57 package mainimport "fmt" import "container/list" type Node struct { K, V interface {} } type LRU struct { list *list.List cacheMap map [interface {}]*list.Element Size int } func NewLRU (cap int ) *LRU { return &LRU{ Size: cap , list: list.New(), cacheMap: make (map [interface {}]*list.Element, cap ), } } func (lru *LRU) Get (k interface {}) (v interface {}, ret bool ) { if ele, ok := lru.cacheMap[k]; ok { lru.list.MoveToFront(ele) return ele.Value.(*Node).V, true } return nil , false } func (lru *LRU) Set (k, v interface {}) { if ele, ok := lru.cacheMap[k]; ok { lru.list.MoveToFront(ele) ele.Value.(*Node).V = v return } if lru.list.Len() == lru.Size { last := lru.list.Back() node := last.Value.(*Node) delete (lru.cacheMap, node.K) lru.list.Remove(last) } ele := lru.list.PushFront(&Node{K: k, V: v}) lru.cacheMap[k] = ele }
其他
上述的容器都不是goroutines 安全的
上面的lr 也不是goroutines 安全的
Ring 中不建议在Do 方法中修改Ring 的指针,行为是未定义的