在上文中实现了一个简单的缓存,并定时对缓存做过期处理。在这一篇文章中将通过基于队列的思想实现对缓存的限制
在写代码之前,首先要想好数据怎么存储也就是存储结构,理清了这一步,代码就好写了。
对于储存还是使用hashmap这种数据结构,在数据量小的情况下,它的时间复杂度是比较低的,执行效率也比较高。为了不使map的存储过大,影响性能,我们设置一个存储的阀值,通过一定的数据失效规则,达到对map的限制。本文是基于队列的思路来实现的。存储关系如下图
可以简单的理解为,使用队列做了一层存储的check
首先需要实现一个队列的存储结构,队列是一种线性的数据结构,我们可以使用数组或是链表来实现,因为我们需要的是一个定长的队列,而且时间复杂度要求低些,所以就选用数组。数据结构如下:
type Queue struct {
cap int //队列的容量
head int // 队列头游标
tail int // 队列尾游标
arr []interface{} // 数据存储数组
}
队列简单就两个操作,入队和出。当头指针和尾指针相同时,队列为空,当尾指针等于容量,不能做入队操作。
// 入队
func (q *Queue) Push(val interface{}) bool {
if q.IsFull() {
return false
}
q.arr[q.tail] = val
q.tail++
return true
}
// 出队
func (q *Queue) Pop() (val interface{}) {
if q.IsEmpty() {
return nil
}
val = q.arr[q.head]
q.head++
return val
}
// 满队列
func (q *Queue) IsFull() bool {
if q.tail == q.cap {
return true
}
return false
}
// 空队列
func (q *Queue) IsEmpty() bool {
if q.head == q.tail {
return true
}
return false
}
首先看下cache的数据结构
// cache
type FIFOCache struct {
cache map[int]int
queue *Queue
}
通过队列实现向map中添加key限制。当队列满时,再添加数据,做pop出队操作,并删除map中的key,通过队列实现了对map长度的限制。
// get value
func (c *FIFOCache) Get(key int) (value interface{}) {
if val, ok := c.cache[key]; ok {
return val
}
return nil
}
// set value
func (c *FIFOCache) Set(key, value int) {
if c.queue.IsFull() {
rmkey := c.queue.Pop()
delete(c.cache, rmkey.(int))
}
c.queue.Push(key)
c.cache[key] = value
}
package main
import (
"fmt"
"strconv"
"time"
)
// 队列数据结构
type Queue struct {
cap int
head int
tail int
arr []interface{}
}
// 实例化
func NewQueue(cap ...int) *Queue {
var length int
if len(cap) == 0 {
length = 30
} else {
length = cap[0]
}
return &Queue{
cap: length,
arr: make([]interface{}, length, length),
}
}
// 入队
func (q *Queue) Push(val interface{}) bool {
if q.IsFull() {
return false
}
q.arr[q.tail] = val
q.tail++
return true
}
// 出队
func (q *Queue) Pop() (val interface{}) {
if q.IsEmpty() {
return nil
}
val = q.arr[q.head]
q.head++
return val
}
// 满队列
func (q *Queue) IsFull() bool {
if q.tail == q.cap {
return true
}
return false
}
// 空队列
func (q *Queue) IsEmpty() bool {
if q.head == q.tail {
return true
}
return false
}
// cache
type FIFOCache struct {
cache map[int]int
queue *Queue
}
func New(cap int) *FIFOCache {
return &FIFOCache{
cache: make(map[int]int),
queue: NewQueue(cap),
}
}
// get value
func (c *FIFOCache) Get(key int) (value interface{}) {
if val, ok := c.cache[key]; ok {
return val
}
return nil
}
// set value
func (c *FIFOCache) Set(key, value int) {
if c.queue.IsFull() {
rmkey := c.queue.Pop()
delete(c.cache, rmkey.(int))
}
c.queue.Push(key)
c.cache[key] = value
}
func main() {
var num = 0
var result int
var cache = New(3)
for {
num = InputNum()
startTime := time.Now()
data := cache.Get(num)
if data != nil {
result = data.(int)
} else {
result = sum(num)
cache.Set(num, result)
}
fmt.Println("计算结果", result)
costTime := time.Since(startTime)
fmt.Println("cost time", costTime)
fmt.Println("\n")
fmt.Println("end cache", cache.cache)
}
}
// 输入函数
func InputNum() (num int) {
var input string
fmt.Println("Please enter calc num: ")
fmt.Scanln(&input)
num, _ = strconv.Atoi(input)
return num
}
// 计算
func sum(num int) (sum int) {
for i := 1; i <= num; i++ {
sum += i
}
return
}