数据结构与算法 - 双链表 - LRU

上篇文章中复习了双链表的基本操作，接下来使用双链表实现 LRU 算法

LRU(Least Recently Used)：最近最少使用，优先淘汰最长时间未被使用的数据，是页面置换算法的一种，广泛地应用于计算机领域的各种基础组件中，如 iOS 中的内存管理和 NSCache 组件。

实现的要点：

标记出最近使用和最久没有使用的数据。我们可以将最近使用的数据移动到链表头部，最久没有使用过的就会自动沉淀到链表尾部
快速访问位于链表中间的数据。要求能够快速访问到该数据前面的数据，如在链表中间位置删除数据，使用双链表能保证这种操作的时间复杂度为 O(1)
快速存取目标数据。使用哈希表来存放具体的数据，在删除、插入时维护链表和哈希表的数据一致性

节点的定义：

class LRUCacheNode {
    var time: TimeInterval!
    var next: LRUCacheNode!
    var previous: LRUCacheNode!
    // key 是沟通哈希表和双链表的桥梁
    var key: String!
    // value 存放缓存的目标数据
    var value: Any?
    init(_ key:String, _ value:Any) {
        self.key = key
        self.value = value
        self.time = CACurrentMediaTime()
        self.next = nil
        self.previous = nil
    }
    var description: String {
        return self.debugDesc()
    }
}

LRU 缓存容器：

enum LRUError:Error {
    case NullParamOccur
    case ValueNotExist
}

class LRUCache {
    let maxCapacity:Int!
    fileprivate var curCapacity:Int!
    private var container: Dictionary<String, LRUCacheNode>!
    private var headNode: LRUCacheNode!
    private var tailNode: LRUCacheNode!
    init(_ maxCapacity:Int) {
        self.maxCapacity = maxCapacity
        self.curCapacity = 0
        self.container = Dictionary()
        self.headNode = nil
        self.tailNode = nil
    }
    var description: String {
        var work = self.headNode
        while work != nil {
            Swift.print(work?.debugDesc() as Any)
            work = work?.next
        }
        return String(describing: self.container)
    }
    func print() {
        Swift.print(self.description + 
        "\ncapacity:\(String(describing: self.curCapacity))" + "\n\n")
    }
}

常用操作

裁剪，发生在每次新数据被添加时

private func trim(){
    if self.maxCapacity < self.curCapacity {
        self.removeAtTail()
    }
}

按 key 移除数据，发生在数据被访问时，一旦数据被访问(如查询、添加、修改)，先删除，然后插入到头部

private func removeNode(_ node:LRUCacheNode?) throws{
    guard node != nil else {
        throw LRUError.NullParamOccur
    }
    
    if node === self.headNode {
        self.removeAtHead()
    } else if node === self.tailNode {
        self.removeAtTail()
    } else {
        self.removeInMid(with: node!)
    }
}

private func removeAtHead() {
    if self.headNode === self.tailNode {
        self.removeAll()
    } else {
        self.container[self.headNode.key] = nil
        self.headNode = self.headNode.next
        self.headNode.previous = nil
        self.curCapacity -= 1
    }
}

private func removeInMid(with node:LRUCacheNode) {
    node.next.previous = node.previous
    node.previous.next = node.next
    self.curCapacity -= 1
    self.container[node.key] = nil
}

private func removeAtTail() {
    if self.headNode === self.tailNode {
        self.removeAll()
    } else {
        self.container[self.tailNode.key] = nil
        self.tailNode = self.tailNode.previous
        self.tailNode.next = nil
        self.curCapacity -= 1
    }
}

头部插入，发生在数据被访问时，一旦数据被访问(如查询、添加、修改)，先删除，然后插入到头部

private func insertAtHead(_ node:LRUCacheNode) {
    self.container[node.key] = node
    if self.headNode == nil {
        self.headNode = node
        self.tailNode = node
        self.curCapacity = 1
        return
    }
    node.next = self.headNode
    self.headNode?.previous = node
    self.headNode = node
    node.previous = nil
    self.curCapacity += 1
}

移动到头部

private func bring2Head(_ node:LRUCacheNode) throws {
    if node === self.headNode {
        return
    }
    
    try self.removeNode(node)
    self.insertAtHead(node)
}

新增和修改，当 key 相同，而 value 不同时将进行修改操作

func add(value val: Any?, key:String) {
    if val == nil {
        do {
            try self.remove(key: key)
        } catch {
            Swift.print("remove.error\(error)")
        }
    }
    
    let oldNode = self.container[key]
    if oldNode != nil {
        oldNode!.time = CACurrentMediaTime()
        oldNode!.value = val!
        do {
            try self.bring2Head(oldNode!)
        } catch {
            Swift.print("remove.error\(error)")
        }
    } else {
        let node = LRUCacheNode(key, val!)
        self.container[key] = node
        self.insertAtHead(node)
        self.trim()
    }
}

删除

func remove(key:String) throws {
    let node = self.container[key]
    try self.removeNode(node)
}

func removeAll() {
    self.headNode = nil
    self.tailNode = nil
    self.curCapacity = 0
    self.container.removeAll()
}

查询

func isContain(key:String) -> Bool {
    let node = self.container[key]
    if node != nil {
        node!.time = CACurrentMediaTime()
        do {
            try self.bring2Head(node!)
        } catch {}
        return true
    }
    return false
}

func object(for key:String) throws -> Any {
    if self.isContain(key: key) {
        return self.container[key]!.value!
    }
    throw LRUError.ValueNotExist
}

验证代码

let lruCache = LRUCache(3)
for i in 0 ..< 6 {
    lruCache.add(value: Int(i), key: String(describing:i * 100))
}
lruCache.print()

_ = lruCache.isContain(key: String(describing: 200))
_ = lruCache.isContain(key: String(describing: 300))
_ = lruCache.isContain(key: String(describing: 300))
lruCache.print()

lruCache.add(value: Int(8), key: String(describing: 900))
lruCache.add(value: Int(9), key: String(describing: 900))
lruCache.print()
/*输出如下:
Optional("key:500,value:5 (0x10050f770)")
Optional("key:400,value:4 (0x10050f450)")
Optional("key:300,value:3 (0x10050f890)")
Optional(["400": DataStructureDemo.LRUCacheNode, 
    "500": DataStructureDemo.LRUCacheNode, 
    "300": DataStructureDemo.LRUCacheNode])
capacity:Optional(3)


Optional("key:300,value:3 (0x10050f890)")
Optional("key:500,value:5 (0x10050f770)")
Optional("key:400,value:4 (0x10050f450)")
Optional(["400": DataStructureDemo.LRUCacheNode, 
    "500": DataStructureDemo.LRUCacheNode, 
    "300": DataStructureDemo.LRUCacheNode])
capacity:Optional(3)


Optional("key:900,value:9 (0x1012498c0)")
Optional("key:300,value:3 (0x10050f890)")
Optional("key:500,value:5 (0x10050f770)")
Optional(["900": DataStructureDemo.LRUCacheNode, 
    "500": DataStructureDemo.LRUCacheNode, 
    "300": DataStructureDemo.LRUCacheNode])
capacity:Optional(3)
*/

算法

算法双链表 Swift

本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议，转载请注明出处！

算法 - 下三角填充（ Swift 学习 & 过渡设计）上一篇

数据结构与算法 - 双链表 - 大整数相加下一篇