使用队列实现缓存淘汰

暮雨

发布于 2019-08-21 10:19:20

1.1K0

发布于 2019-08-21 10:19:20

文章被收录于专栏：云端漫步云端漫步

数据结构设计

在上文中实现了一个简单的缓存，并定时对缓存做过期处理。在这一篇文章中将通过基于队列的思想实现对缓存的限制

在写代码之前，首先要想好数据怎么存储也就是存储结构，理清了这一步，代码就好写了。

对于储存还是使用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的数据结构

// 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
}

本文参与腾讯云自媒体分享计划，分享自微信公众号。

原始发表：2019-08-15，如有侵权请联系 cloudcommunity@tencent.com 删除

数据结构