LRU算法

LRU 是 Least Recently Used 的缩写，即最近最少使用，是系统中常用的一种页面置换算法，其算法思想就是：如果一个页面最近最少使用，那么在将来它被使用的概率就很低。在 App 中，也时常将 LRU 引用为缓存的一种淘汰策略，接下来我们将使用 Swift 来实现一个基于 LRU 的缓存机制。

leetcode题目

运用所掌握的数据结构，设计和实现一个 LRU (最近最少使用) 缓存机制 。
实现 LRUCache 类：

  • LRUCache(int capacity) 以正整数作为容量 capacity 初始化 LRU 缓存
  • int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。
  • void put(int key, int value) 如果关键字已经存在，则变更其数据值；如果关键字不存在，则插入该组「关键字-值」。当缓存容量达到上限时，它应该在写入新数据之前删除最久未使用的数据值，从而为新的数据值留出空间。
  • 要求：get 和 put 操作都要在 O(1)的时间复杂度内完成。

来源：力扣（LeetCode）

分析需求

  1. 要满足 O(1) 时间复杂度，能满足的数据结构就是哈希表。
  2. 最久最未使用，那么数据就应该是有顺序的，数据结构中能满足的是数组和链表。
  3. 数组在分配内存时是连续的，在 Swift 中，扩展一个已分配空间的数组，需要重新分配更大的空间，然后将内容复制到新空间中，这种开销比较大。
  4. 链表的存储是分散的，单向链表要在某个位置上插入或删除一个节点的时间复杂度为 O(n)，因为需要先遍历到该位置，而双向链表则不需要遍历，比较灵活。

综上，这个缓存应该是哈希表 + 双向链表的数据结构。

代码实现

缓存的主体是哈希表，双向链表是作为一个顺序的维护。
那么我们可以把链表的节点存储到哈希表中，节点中保存 key和 value ，再通过节点的前趋和后继指针维持双向链表结构。

链表的节点

由于 Swift 的 struct 不允许自身的嵌套，即以下的写法是错误的：

struct Node {
    var prev:Node
}

因此选用 class 来定义链表的节点：

//链表节点
class Node {
    var key,value :Int
    //前趋节点、后继节点
    var prev, next : Node?

    init(_ key:Int,_ value:Int) {
        self.key = key
        self.value = value
    }
    deinit {
        print("Node deinit :",key,"-",value)
    }
}

双向链表的实现

根据单一职责原则，我们将链表的实现和操作单独封装在 DuLinkList 类中，为方便调试，增加 printList() 函数来打印观察。

//双向链表实现
class DuLinkList {
    //首节点、尾节点
    private var header,tail : Node
    
    init() {
        header = Node.init(0, 0)
        tail = Node.init(0, 0)
        header.next = tail
        tail.prev = header
    }
    ///添加到链表首节点
    func addToFirst(_ node:Node){
        node.next = header.next
        header.next?.prev = node
        
        node.prev = header
        header.next = node
    }
    ///删除指定节点
    func removeNode(_ node:Node){
        //首尾节点不删除
        if node.prev == nil || node.next == nil {
            return
        }
        node.prev?.next = node.next
        node.next?.prev = node.prev
        node.prev = nil
        node.next = nil
    }
    ///删除最后一个节点
    func removeLast() -> Node {
        let note = tail.prev!
        removeNode(note)
        return note
    }
    ///打印链表
    func printList(){
        var next = header.next
        while let node = next, node.next != nil {
            print("list note : ",node.key,"-",node.value)
            next = node.next
        }
    }
    ///销毁链表
    private func destroyList(){
        var node:Node? = header
        repeat{
            let next = node?.next
            node?.prev = nil
            node?.next = nil
            node = next
        }while( node != nil)
    }
    
    deinit {
        print("DuLinkList deinit")
        destroyList()
    }
}

值的注意的是：双向链表的节点之间是相互引用的，构成了循环引用，会导致链表无法释放，因此增加 destroyList() 函数来销毁链表，并在 DuLinkList 类中的 deinit函数中调用。

LRUCache 的实现

/// 通过构建哈希表和双向链表来实现LRU算法
 /// 其中，哈希表的 value 是 链表的的节点
class LRUCache {
    //存储容量
    var capacity = 5
    
    //哈希表
    private var cacheTable = Dictionary<Int,Node>()
    //双向链表
    private let linkList = DuLinkList()
    
    init(_ capacity:Int) {
        self.capacity = capacity
    }
    
    /// 将 value 存入哈希表中
    /// 如果表中未存在，则生成节点，并存入表中，并将节点移到链表的首节点
    /// 如果表中已存在，则将更新 value ，并将节点移到链表的首节点
    /// 如果超出存储容量，则删除链表末尾的节点，再存入，并将节点移到链表的首节点
    func put(_ key:Int,_ value:Int){
        if let node = cacheTable[key] {
            node.value = value
            cacheTable[key] = node
            //删除node节点，重新添加到链表首节点
            linkList.removeNode(node)
            linkList.addToFirst(node)
        }else{
            //创建节点
            let note = Node.init(key, value)
            
            if cacheTable.count >= capacity {
                //超出容量,则删除最后一个节点、清除哈希表的 value
                let temp = linkList.removeLast()
                cacheTable[temp.key] = nil
            }
            cacheTable[key] = note
            linkList.addToFirst(note)
        }
    }
    
    /// 从哈希表中取出 value
    /// 如果哈希表中存在value，则将对应的节点放到链表首节点,反之则返回 -1
    func get(_ key:Int) -> Int? {
        guard let node = cacheTable[key] else {
            return -1
        }
        //删除node节点，重新添加到链表首节点
        linkList.removeNode(node)
        linkList.addToFirst(node)

        return node.value
    }
    
    func printTable() {
        print("cache : ",cacheTable)
        linkList.printList()
        print("---------------------")
    }
    
    deinit {
        print("LRUCache deinit")
    }
}

测试

let cache = LRUCache.init(3)
cache.put(1, 1)
cache.printTable()
cache.put(2, 2)
cache.printTable()
cache.put(3, 3)
cache.printTable()
cache.put(4, 4)
cache.printTable()
cache.put(5, 5)
cache.printTable()
print("cache get :",cache.get(3))
cache.printTable()
cache.put(4, 9)
cache.printTable()

测试结果：

cache :  [1: SwiftLang.Node]
list note :  1 - 1
---------------------
cache :  [2: SwiftLang.Node, 1: SwiftLang.Node]
list note :  2 - 2
list note :  1 - 1
---------------------
cache :  [2: SwiftLang.Node, 1: SwiftLang.Node, 3: SwiftLang.Node]
list note :  3 - 3
list note :  2 - 2
list note :  1 - 1
---------------------
Node deinit : 1 - 1
cache :  [2: SwiftLang.Node, 4: SwiftLang.Node, 3: SwiftLang.Node]
list note :  4 - 4
list note :  3 - 3
list note :  2 - 2
---------------------
Node deinit : 2 - 2
cache :  [4: SwiftLang.Node, 5: SwiftLang.Node, 3: SwiftLang.Node]
list note :  5 - 5
list note :  4 - 4
list note :  3 - 3
---------------------
cache get : Optional(3)
cache :  [4: SwiftLang.Node, 5: SwiftLang.Node, 3: SwiftLang.Node]
list note :  3 - 3
list note :  5 - 5
list note :  4 - 4
---------------------
cache :  [4: SwiftLang.Node, 5: SwiftLang.Node, 3: SwiftLang.Node]
list note :  4 - 9
list note :  3 - 3
list note :  5 - 5
---------------------
LRUCache deinit
DuLinkList deinit
Node deinit : 4 - 9
Node deinit : 3 - 3
Node deinit : 5 - 5
Node deinit : 0 - 0
Node deinit : 0 - 0

标签: LRU, 缓存策略

评论已关闭