Swift -- LRU算法实现和简单的缓存示例

双链表

image.png

来看双向链表的实现
首先定义Node

/// 双向列表的节点
class linkedNode<T> {
    var value: T
    
    var previous: linkedNode?
    var next: linkedNode?
    
    init(_ value: T) {
        self.value = value
    }
}

List

class linkedList<T> {
    typealias Node = linkedNode<T>
    
     private var head: Node?
     private var tail: Node?
    
    /// 判断是否为空
    var isEmpty: Bool {
        return head == nil
    }
    /// 获取头节点
    var first: Node?{
        return head
    }
    ///获取尾节点
    var last: Node? {
        return tail
    }
    ///获取 链表数量
    var count: Int = 0
    // 下标语法糖
    subscript(index: Int) -> T? {
        var i = index
        var next = head
        
        while i > 0 {
            i -= 1
            next = next?.next
        }
        
        return next?.value
    }
}

尾插法
1 tail.next = new Node
2 new Node.previous = tail
这里主要注意 头尾节点的问题

/// 尾插
    func append(_ value: T) {
        let newNode = Node(value)
        
        if let lastNode = tail {
            lastNode.next = newNode
            newNode.previous = lastNode
            
            tail = newNode
        }else {
            head = newNode
            tail = newNode
        }
        
        //修改数量
        count += 1
    }

中插


image.png
 ///插入 node
    func insert(value: T, atIndex index: Int) {
        let (pre,next) = nodesBeforeAndAfter(index: index)
        
        let newNode = Node(value)
        
        pre?.next = newNode
        next?.previous = newNode
        
        newNode.previous = pre
        newNode.next = next
        
        if pre == nil {
            head = newNode
        }
        
        if count == index - 1 {
            tail = newNode
        }
        
        count += 1
        
        
    }
///获取某节点的头结点和尾节点
    private func nodesBeforeAndAfter(index: Int) -> (Node?,Node?) {
        
        var next = head
        var previous: Node?
        var i = index
        
        while i > 0 && next?.next != nil{
            i -= 1
            
            previous = next
            next = next?.next
            
        }
        
        return (previous,next)
        
    }

删除节点

///删除最后一个
    func removeLast() {
        removeNode(node: last!)
    }
    /// 移除某一个node
    func removeNode(node: Node) {
        let pre = node.previous
        let next = node.next
        
        pre?.next = next
        next?.previous = pre
        
        if pre == nil {
            head = node.next
        }
        if next == nil {
            tail = node.previous
        }
        count -= 1
    }

移动到头结点

/// node 移动到头节点
    func moveToHead(node: Node) {
        let pre = node.previous
        let next = node.next
        
        pre?.next = next
        next?.previous = pre
        
        node.next = head
        head?.previous = node
        
        head = node
        
        if pre == nil {
            return
        }
        if next == nil {
            tail = pre
        }
    }

LRU

准备工作差不多了
我来看下LRU的定义


image.png
  1. 新数据插入到链表头部;

  2. 每当缓存命中(即缓存数据被访问),则将数据移到链表头部;

  3. 当链表满的时候,将链表尾部的数据丢弃。

【命中率】

当存在热点数据时,LRU的效率很好,但偶发性的、周期性的批量操作会导致LRU命中率急剧下降,缓存污染情况比较严重。

【复杂度】

实现简单。

【代价】

命中时需要遍历链表,找到命中的数据块索引,然后需要将数据移到头部。

LRU 实践

我们客户端关于LRU算法 最先想到,肯定是图片缓存系统
为了方便
我们存的数据 为["1": "我是一张图片"] 这种【String: Stirng】
首先我们定义一个简单的缓存类

/// LRU 实现
class CacheLRU<T> {
    var limit: Int
    var cache: linkedList<T>
    init(cacheNumber: Int) {
        self.limit = cacheNumber
        self.cache = linkedList<T>()
    }
    
    //增
    func add(some: T) {
        if cache.count == limit {
            cache.removeLast()
        }
        cache.append(some)
    }
    //删
    func clearCache() {
        cache.removeAll()
    }
    
    //移
    func move(value: linkedNode<T>) {
        cache.moveToHead(node: value)
    }
}
// 1 先从缓存系统查看是否有缓存
extension linkedList where T == Dictionary<String, String> {
    func contains(name: String) -> Node? {
        var next = head
        var index = 0
        while index < count {
            if next?.value[name] != nil {
                return next
            }
            index += 1
            next = next?.next
        }
        return nil
    }
}
extension CacheLRU where T == Dictionary<String, String> {
    func fetchImage(name: String) {
        let node = cache.contains(name: name)
        
        if let dic = node?.value {
            // 1.内存存在 直接取内存中的数据
            print(dic[name] ?? "😁")
            // 2.lru 访问的数据成为头结点
            move(value: node!)
        }else {
            //网络获取 并且 add
        }
    }
}

我们来看结果
1 创建缓存类 存贮图片
这里设置存贮上线为2张图片(实际肯定是内存为标准)

let cacheMnager = CacheLRU<Dictionary<String,String>>.init(cacheNumber: 2)
let image1 = ["1": "我是一张图片"]
let image2 = ["2": "我是一张图片"]
let image3 = ["3": "我是一张图片"]
cacheMnager.add(some: image1)
cacheMnager.add(some: image2)
cacheMnager.add(some: image3)

因为上线是2 导致 第二张图片被清除


image.png

2 访问已有图片

cacheMnager.fetchImage(name: "3")

访问已有图片的 已有图片的node 会移到头部


image.png

LRU-K

image.png

LRU-K中的K代表最近使用的次数,因此LRU可以认为是LRU-1。LRU-K的主要目的是为了解决LRU算法“缓存污染”的问题,其核心思想是将“最近使用过1次”的判断标准扩展为“最近使用过K次”。

实现上: LRU-K 的其实就是 在LRU的基础上多维护一条历史链表。链表里面的数据多一个访问次数属性。当访问次数打到K次。就存到缓存队列里 这里和LRU一样

【命中率】

LRU-K降低了“缓存污染”带来的问题,命中率比LRU要高。

【复杂度】

LRU-K队列是一个优先级队列,算法复杂度和代价比较高。

【代价】

由于LRU-K还需要记录那些被访问过、但还没有放入缓存的对象,因此内存消耗会比LRU要多;当数据量很大的时候,内存消耗会比较可观。

LRU-K需要基于时间进行排序(可以需要淘汰时再排序,也可以即时排序),CPU消耗比LRU要高。

我们看代码实现

class CacheLRU_K<T,E> {
    let cache: CacheLRU<E>
    let cacheHistory: CacheLRU<T>
    let limit: Int
    let K: Int
    
    init(limit: Int,K: Int) {
        self.K = K
        self.limit = limit
        self.cache = CacheLRU.init(cacheNumber: limit)
        self.cacheHistory = CacheLRU.init(cacheNumber: limit)
    }
}
extension linkedList where T == Dictionary<String,Any> {
    func contains(name: String) -> T? {
        var next = head
        var index = 0
        while index < count {
            if next?.value[name] != nil {
                return next?.value
            }
            index += 1
            next = next?.next
        }
        return nil
    }
}
extension CacheLRU_K where T == Dictionary<String,Any>, E == [String: String] {
    func add(some: T) {
        
        var data: [String: Any] = some
        let name = some.first!.key
        let temp = cacheHistory.cache.contains(name: name)
        if let temp = temp {
            data = temp
        }
        
        if data["number"] == nil {
            data["number"] = 0
        }
        
        var number = data["number"] as! Int
        data["number"] = number + 1
        number += 1
        if number == K {
            data["number"] = nil
            let temp = data as! [String: String]
            cache.add(some: temp)
            //cacheHistory remove
            //下班了 以后补上0.0
        }else {
            
            if cacheHistory.cache.count == limit {
                cacheHistory.cache.removeLast()
            }
            cacheHistory.add(some: data)
        }
    }
    
    func fetchImage(name: String) {
        let node = cache.cache.contains(name: name)
        
        if let dic = node?.value {
            // 1.内存存在 直接取内存中的数据
            print(dic[name] ?? "😁")
            // 2.lru 访问的数据成为头结点
            cache.move(value: node!)
        }else {
            //这里和lru 不同
            //网络请求
            // lru_k add
        }
    }
}

这里 基本和LRU 一样就是维护一条历史队列
这里初始化 K 为2 意思
只有连续add 2次才能真正的假如到缓存链表中

let manager = CacheLRU_K<[String:Any],[String:String]>.init(limit: 2, K: 2)
let image11 = ["1": "我是一张图片"]
manager.add(some: image11)

缓存和 历史缓存的结果


image.png

继续add

manager.add(some: image11)

这时候内存中就存在了我要要缓存的数据


image.png

历史缓存中就应该删除这条记录

下班了 溜了。。实现过程可能没讲清楚。但是代码都注释的听明白的。有时间补上

©著作权归作者所有,转载或内容合作请联系作者
  • 序言:七十年代末,一起剥皮案震惊了整个滨河市,随后出现的几起案子,更是在滨河造成了极大的恐慌,老刑警刘岩,带你破解...
    沈念sama阅读 204,189评论 6 478
  • 序言:滨河连续发生了三起死亡事件,死亡现场离奇诡异,居然都是意外死亡,警方通过查阅死者的电脑和手机,发现死者居然都...
    沈念sama阅读 85,577评论 2 381
  • 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
    开封第一讲书人阅读 150,857评论 0 337
  • 文/不坏的土叔 我叫张陵,是天一观的道长。 经常有香客问我,道长,这世上最难降的妖魔是什么? 我笑而不...
    开封第一讲书人阅读 54,703评论 1 276
  • 正文 为了忘掉前任,我火速办了婚礼,结果婚礼上,老公的妹妹穿的比我还像新娘。我一直安慰自己,他们只是感情好,可当我...
    茶点故事阅读 63,705评论 5 366
  • 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
    开封第一讲书人阅读 48,620评论 1 281
  • 那天,我揣着相机与录音,去河边找鬼。 笑死,一个胖子当着我的面吹牛,可吹牛的内容都是我干的。 我是一名探鬼主播,决...
    沈念sama阅读 37,995评论 3 396
  • 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
    开封第一讲书人阅读 36,656评论 0 258
  • 序言:老挝万荣一对情侣失踪,失踪者是张志新(化名)和其女友刘颖,没想到半个月后,有当地人在树林里发现了一具尸体,经...
    沈念sama阅读 40,898评论 1 298
  • 正文 独居荒郊野岭守林人离奇死亡,尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 35,639评论 2 321
  • 正文 我和宋清朗相恋三年,在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 37,720评论 1 330
  • 序言:一个原本活蹦乱跳的男人离奇死亡,死状恐怖,灵堂内的尸体忽然破棺而出,到底是诈尸还是另有隐情,我是刑警宁泽,带...
    沈念sama阅读 33,395评论 4 319
  • 正文 年R本政府宣布,位于F岛的核电站,受9级特大地震影响,放射性物质发生泄漏。R本人自食恶果不足惜,却给世界环境...
    茶点故事阅读 38,982评论 3 307
  • 文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹,春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 29,953评论 0 19
  • 文/苍兰香墨 我抬头看了看天上的太阳。三九已至,却和暖如春,着一层夹袄步出监牢的瞬间,已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 31,195评论 1 260
  • 我被黑心中介骗来泰国打工, 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留,地道东北人。 一个月前我还...
    沈念sama阅读 44,907评论 2 349
  • 正文 我出身青楼,却偏偏与公主长得像,于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子,可洞房花烛夜当晚...
    茶点故事阅读 42,472评论 2 342

推荐阅读更多精彩内容

  • 缓存淘汰算法--LRU算法 1. LRU 1.1 原理 LRU(Least recently used,)算法根据...
    白公子是猫奴阅读 476评论 0 0
  • 1. LRU 1.1.原理 LRU(Leastrecentlyused,最近最少使用)算法根据数据的历史访问记录来...
    安易学车阅读 2,520评论 0 23
  • 1. LRU 1.1. 原理LRU(Least recently used,最近最少使用)算法根据数据的历史访问记...
    AKyS佐毅阅读 2,151评论 0 3
  • LRU原理 LRU(Least recently used,最近最少使用)算法根据数据的历史访问记录来进行淘汰数据...
    jiangmo阅读 60,195评论 3 30
  • 在路边摊打包两份水饺,老板是一对老夫妇,听错了煮了三份水饺,多的一份老板送给了隔壁摊小伙吃。 我喜欢你,你喜欢我吗...
    天真林某人阅读 116评论 0 0