golang 提供了幾個簡單的容器供我們使用，本文在介紹幾種Golang 容器的基礎上，實作一個基于Golang 容器的LRU演算法，
容器介紹
Golang 容器位于 container 包下，提供了三種包供我們使用，heap、list、ring. 下面我們分別學習，
heap
heap 是一個堆的實作，一個堆正常保證了獲取/彈出最大（最小）元素的時間為log n、插入元素的時間為log n.
golang的堆實作介面如下：
// src/container/heap.go
type Interface interface {
sort.Interface
Push(x interface{}) // add x as element Len()
Pop() interface{} // remove and return element Len() - 1.
}
heap 是基于 sort.Interface 實作的，
// src/sort/
type Interface interface {
// Len is the number of elements in the collection.
Len() int
// Less reports whether the element with
// index i should sort before the element with index j.
Less(i, j int) bool
// Swap swaps the elements with indexes i and j.
Swap(i, j int)
}
因此，如果要使用官方提供的heap，需要我們實作如下幾個介面：
Len() int {} // 獲取元素個數
Less(i, j int) bool {} // 比較方法
Swap(i, j int) // 元素交換方法
Push(x interface{}){} // 在末尾追加元素
Pop() interface{} // 回傳末尾元素
然后在使用時，我們可以使用如下幾種方法：
// 初始化一個堆
func Init(h Interface){}
// push一個元素倒堆中
func Push(h Interface, x interface{}){}
// pop 堆頂元素
func Pop(h Interface) interface{} {}
// 洗掉堆中某個元素，時間復雜度 log n
func Remove(h Interface, i int) interface{} {}
// 調整i位置的元素位置（位置I的資料變更后）
func Fix(h Interface, i int){}
list 鏈表
list 實作了一個雙向鏈表，鏈表不需要實作heap 類似的介面，可以直接使用，
鏈表的構造：
// 回傳一個鏈表物件
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{} {}
// 在表頭插入值為 v 的元素
func (l *List) PushFront(v interface{}) *Element {}
// 在表尾插入值為 v 的元素
func (l *List) PushBack(v interface{}) *Element {}
// 在mark之前插入值為v 的元素
func (l *List) InsertBefore(v interface{}, mark *Element) *Element {}
// 在mark 之后插入值為 v 的元素
func (l *List) InsertAfter(v interface{}, mark *Element) *Element {}
// 移動e某個元素到表頭
func (l *List) MoveToFront(e *Element) {}
// 移動e到隊尾
func (l *List) MoveToBack(e *Element) {}
// 移動e到mark之前
func (l *List) MoveBefore(e, mark *Element) {}
// 移動e 到mark 之后
func (l *List) MoveAfter(e, mark *Element) {}
// 追加到隊尾
func (l *List) PushBackList(other *List) {}
// 將鏈表list放在佇列前
func (l *List) PushFrontList(other *List) {}
我們可以通過 Value 方法訪問 Element 中的元素，除此之外，我們還可以用下面方法做鏈表遍歷：
// 回傳下一個元素
func (e *Element) Next() *Element {}
// 回傳上一個元素
func (e *Element) Prev() *Element {}
下面是佇列的遍歷的例子：
// l 為佇列，
for e := l.Front(); e != nil; e = e.Next() {
//通過 e.Value 做資料訪問
}
ring 回圈串列
container 中的回圈串列是采用鏈表實作的，
// 構造一個包含N個元素的回圈串列
func New(n int) *Ring {}
// 回傳串列下一個元素
func (r *Ring) Next() *Ring {}
// 回傳串列上一個元素
func (r *Ring) Prev() *Ring {}
// 移動n個元素 （可以前移，可以后移）
func (r *Ring) Move(n int) *Ring {}
// 把 s 鏈接到 r 后面，如果s 和r 在一個ring 里面，會把r到s的元素從ring 中刪掉
func (r *Ring) Link(s *Ring) *Ring {}
// 洗掉n個元素 （內部就是ring 移動n個元素，然后呼叫Link)
func (r *Ring) Unlink(n int) *Ring {}
// 回傳Ring 的長度，時間復雜度 n
func (r *Ring) Len() int {}
// 遍歷Ring，執行 f 方法 （不建議內部修改ring）
func (r *Ring) Do(f func(interface{})) {}
訪問Ring 中元素，直接 Ring.Value 即可，
容器的使用
下面，我們通過map 和 官方包中的雙向鏈表實作一個簡單的lru 演算法，用來熟悉golang 容器的使用，
LRU 演算法 (Least Recently Used)，在做快取置換時用的比較多，逐步淘汰最近未使用的cache，而使我們的快取中持續保持著最近使用的資料，
package main
import "fmt"
import "container/list"
// lru 中的資料
type Node struct {
K, V interface{}
}
// 鏈表 + map
type LRU struct {
list *list.List
cacheMap map[interface{}]*list.Element
Size int
}
// 初始化一個LRU
func NewLRU(cap int) *LRU {
return &LRU{
Size: cap,
list: list.New(),
cacheMap: make(map[interface{}]*list.Element, cap),
}
}
// 獲取LRU中資料
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
}
// 設定LRU中資料
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 的指標，行為是未定義的
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/13821.html
標籤：Go