有趣的地方

有趣的地方

Go的数据结构与实现【LRU Cache】

介绍

在本文中,我们将用Go实现LRU Cache。

LRU Cache

最近最少使用(LRU)是一种缓存逐出算法,它按使用顺序组织元素。在LRU中,最长时间没有被使用的元素会被从缓存中逐出。

例如,如果我们有一个容量为三个项目的缓存:
在这里插入图片描述
最初,缓存是空的,我们将元素8放入缓存中,元素9和6像以前一样被缓存。但是现在,缓存容量已满,要放入下一个元素,我们必须驱逐缓存中最近最少使用的元素。
在我们用Go实现LRU缓存之前,最好了解一下缓存的一些方面:

  • 所有操作都应按O(1)的顺序运行
  • 缓存大小有限
  • 所有缓存操作都必须支持并发
  • 如果缓存已满,添加新项必须调用LRU策略

实现

首先定义一些相关数据结构:

type K int
type V int

type Cache struct {
	Key   K
	Value V
}

type LRUCache struct {
	size    int
	list    *list.List
	element map[K]*list.Element
}

其中含义如下:

  • size:可以存储在缓存中的元素数量
  • list:双向链表,使用Go的原生container/list实现
  • element:映射存储键和指向存储在列表中的值的指针 我们将实现以下的相关方法:
  • Get:获取一个key-value对,如果不存在则返回一个特定值,在这里暂定为-1
  • Put:插入一个key-value对
  • RecentlyUsed:获取最近使用的value
  • Remove:删除一个key-value对
  • Clear:清空缓存

Get

由于缓存将value存储在map中,key-value存储在列表中。首先检查key是否存在于map中,返回存储在双向链表中的key对应的value或返回-1。
在返回值的同时,还需要将它移到双向链表的前面,以保持最近最少使用的逻辑。

func (c *LRUCache) Get(key K) V {
	if node, ok := c.element[key]; ok {
		// hit LRU cache, fetch key value pair
		value := node.Value.(*list.Element).Value.(Cache).Value
		// move node to the front of list
		c.list.MoveToFront(node)

		return value
	}

	return V(-1)
}

Put
将key-value对插入缓存中遵循以下步骤:

  • 如果在缓存中找到key,则将其移动到双向链表的前面并更新value
  • 否则,检查缓存的当前容量,若溢出,则从双向链表中删除最近最近未使用的条目
  • 将新元素存储在列表的前面。

正如上述步骤所定义的,在检查容量时,我们从缓存中删除了后面的元素,它定义了我们最近最少使用的用例。

func (c *LRUCache) Put(key K, value V) {
	if node, ok := c.element[key]; ok {
		// there is already key in LRU cache, move node to the front of list
		c.list.MoveToFront(node)
		// update key value pair
		node.Value.(*list.Element).Value = Cache{Key: key, Value: value}
	} else {
		// there is no key in LRU cache
		if c.list.Len() == c.size {
			// LRU is full
			lastKey := c.list.Back().Value.(*list.Element).Value.(Cache).Key
			delete(c.element, lastKey)
			c.list.Remove(c.list.Back())
		}

		node := &list.Element{
			Value: Cache{
				Key:   key,
				Value: value,
			},
		}

		pointer := c.list.PushFront(node)
		c.element[key] = pointer
	}
}

RecentlyUsed

返回双向链表中最前面的值。

func (c *LRUCache) RecentlyUsed() V {
	return c.list.Front().Value.(*list.Element).Value.(Cache).Value
}

Remove

删除指定的key,如果key存在于缓存中则删除,否则无操作

func (c *LRUCache) Remove(key K) {
	if node, ok := c.element[key]; ok {
		delete(c.element, key)
		c.list.Remove(node)
	}
}

Clear

清空缓存,将双向链表和map全部置空

func (c *LRUCache) Clear() {
	c.list = nil
	c.element = nil
}

发表评论:

Powered By Z-BlogPHP 1.7.3

© 2018-2020 有趣的地方 粤ICP备18140861号-1 网站地图