欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

golang 容器的学习与实践

程序员文章站 2022-03-20 15:40:27
golang 提供了几个简单的容器供我们使用,本文在介绍几种Golang 容器的基础上,实现一个基于Golang 容器的LRU算法。 容器介绍 Golang 容器位于 container 包下,提供了三种包供我们使用,heap、list、ring. 下面我们分别学习。 heap heap 是一个堆的 ......

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
}

其他

  1. 上述的容器都不是goroutines 安全的
  2. 上面的lr 也不是goroutines 安全的
  3. ring 中不建议在do 方法中修改ring 的指针,行为是未定义的