Swift -- LRU算法實(shí)現(xiàn)和簡(jiǎn)單的緩存示例

雙鏈表

image.png

來看雙向鏈表的實(shí)現(xiàn)
首先定義Node

/// 雙向列表的節(jié)點(diǎn)
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
    }
    /// 獲取頭節(jié)點(diǎn)
    var first: Node?{
        return head
    }
    ///獲取尾節(jié)點(diǎn)
    var last: Node? {
        return tail
    }
    ///獲取 鏈表數(shù)量
    var count: Int = 0
    // 下標(biāo)語法糖
    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
這里主要注意 頭尾節(jié)點(diǎn)的問題

/// 尾插
    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
        }
        
        //修改數(shù)量
        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
        
        
    }
///獲取某節(jié)點(diǎn)的頭結(jié)點(diǎn)和尾節(jié)點(diǎn)
    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)
        
    }

刪除節(jié)點(diǎn)

///刪除最后一個(gè)
    func removeLast() {
        removeNode(node: last!)
    }
    /// 移除某一個(gè)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
    }

移動(dòng)到頭結(jié)點(diǎn)

/// node 移動(dòng)到頭節(jié)點(diǎn)
    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

準(zhǔn)備工作差不多了
我來看下LRU的定義


image.png

  1. 新數(shù)據(jù)插入到鏈表頭部；

  2. 每當(dāng)緩存命中（即緩存數(shù)據(jù)被訪問），則將數(shù)據(jù)移到鏈表頭部；

  3. 當(dāng)鏈表滿的時(shí)候，將鏈表尾部的數(shù)據(jù)丟棄。

【命中率】

當(dāng)存在熱點(diǎn)數(shù)據(jù)時(shí)，LRU的效率很好，但偶發(fā)性的、周期性的批量操作會(huì)導(dǎo)致LRU命中率急劇下降，緩存污染情況比較嚴(yán)重。

【復(fù)雜度】

實(shí)現(xiàn)簡(jiǎn)單。

【代價(jià)】

命中時(shí)需要遍歷鏈表，找到命中的數(shù)據(jù)塊索引，然后需要將數(shù)據(jù)移到頭部。

LRU 實(shí)踐

我們客戶端關(guān)于LRU算法 最先想到，肯定是圖片緩存系統(tǒng)
為了方便
我們存的數(shù)據(jù) 為["1": "我是一張圖片"] 這種【String: Stirng】
首先我們定義一個(gè)簡(jiǎn)單的緩存類

/// LRU 實(shí)現(xiàn)
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 先從緩存系統(tǒng)查看是否有緩存
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.內(nèi)存存在 直接取內(nèi)存中的數(shù)據(jù)
            print(dic[name] ?? "??")
            // 2.lru 訪問的數(shù)據(jù)成為頭結(jié)點(diǎn)
            move(value: node!)
        }else {
            //網(wǎng)絡(luò)獲取 并且 add
        }
    }
}

我們來看結(jié)果
1 創(chuàng)建緩存類 存貯圖片
這里設(shè)置存貯上線為2張圖片（實(shí)際肯定是內(nèi)存為標(biāo)準(zhǔn)）

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)

因?yàn)樯暇€是2 導(dǎo)致 第二張圖片被清除


image.png

2 訪問已有圖片

cacheMnager.fetchImage(name: "3")

訪問已有圖片的 已有圖片的node 會(huì)移到頭部


image.png

LRU-K

image.png

LRU-K中的K代表最近使用的次數(shù)，因此LRU可以認(rèn)為是LRU-1。LRU-K的主要目的是為了解決LRU算法“緩存污染”的問題，其核心思想是將“最近使用過1次”的判斷標(biāo)準(zhǔn)擴(kuò)展為“最近使用過K次”。

實(shí)現(xiàn)上： LRU-K 的其實(shí)就是 在LRU的基礎(chǔ)上多維護(hù)一條歷史鏈表。鏈表里面的數(shù)據(jù)多一個(gè)訪問次數(shù)屬性。當(dāng)訪問次數(shù)打到K次。就存到緩存隊(duì)列里 這里和LRU一樣

【命中率】

LRU-K降低了“緩存污染”帶來的問題，命中率比LRU要高。

【復(fù)雜度】

LRU-K隊(duì)列是一個(gè)優(yōu)先級(jí)隊(duì)列，算法復(fù)雜度和代價(jià)比較高。

【代價(jià)】

由于LRU-K還需要記錄那些被訪問過、但還沒有放入緩存的對(duì)象，因此內(nèi)存消耗會(huì)比LRU要多；當(dāng)數(shù)據(jù)量很大的時(shí)候，內(nèi)存消耗會(huì)比較可觀。

LRU-K需要基于時(shí)間進(jìn)行排序（可以需要淘汰時(shí)再排序，也可以即時(shí)排序），CPU消耗比LRU要高。

我們看代碼實(shí)現(xiàn)

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
            //下班了 以后補(bǔ)上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.內(nèi)存存在 直接取內(nèi)存中的數(shù)據(jù)
            print(dic[name] ?? "??")
            // 2.lru 訪問的數(shù)據(jù)成為頭結(jié)點(diǎn)
            cache.move(value: node!)
        }else {
            //這里和lru 不同
            //網(wǎng)絡(luò)請(qǐng)求
            // lru_k add
        }
    }
}

這里 基本和LRU 一樣就是維護(hù)一條歷史隊(duì)列
這里初始化 K 為2 意思
只有連續(xù)add 2次才能真正的假如到緩存鏈表中

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

緩存和 歷史緩存的結(jié)果


image.png

繼續(xù)add

manager.add(some: image11)

這時(shí)候內(nèi)存中就存在了我要要緩存的數(shù)據(jù)


image.png

歷史緩存中就應(yīng)該刪除這條記錄

下班了 溜了。。實(shí)現(xiàn)過程可能沒講清楚。但是代碼都注釋的聽明白的。有時(shí)間補(bǔ)上

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時(shí)請(qǐng)結(jié)合常識(shí)與多方信息審慎甄別。
平臺(tái)聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點(diǎn)，簡(jiǎn)書系信息發(fā)布平臺(tái)，僅提供信息存儲(chǔ)服務(wù)。

相關(guān)閱讀更多精彩內(nèi)容

  • 緩存淘汰算法--LRU算法 1. LRU 1.1 原理 LRU（Least recently used，）算法根據(jù)...
    白公子是貓奴閱讀 507評(píng)論 0贊 0
  • 1. LRU 1.1.原理 LRU（Leastrecentlyused，最近最少使用）算法根據(jù)數(shù)據(jù)的歷史訪問記錄來...
    安易學(xué)車閱讀 2,621評(píng)論 0贊 23
  • 1. LRU 1.1. 原理LRU（Least recently used，最近最少使用）算法根據(jù)數(shù)據(jù)的歷史訪問記...
    AKyS佐毅閱讀 2,281評(píng)論 0贊 3
  • LRU原理 LRU（Least recently used，最近最少使用）算法根據(jù)數(shù)據(jù)的歷史訪問記錄來進(jìn)行淘汰數(shù)據(jù)...
    jiangmo閱讀 60,621評(píng)論 3贊 30
  • 在路邊攤打包兩份水餃，老板是一對(duì)老夫婦，聽錯(cuò)了煮了三份水餃，多的一份老板送給了隔壁攤小伙吃。 我喜歡你，你喜歡我嗎...
    天真林某人閱讀 160評(píng)論 0贊 0

友情鏈接更多精彩內(nèi)容