用Swift实现Cache LRU （译文）

2018-04-22 本文已影响406人小凉介

此文章为本人翻译的译文，版权为原作者所有。
英文原文：How To Implement Cache LRU With Swift

本文代码地址MarcoSantarossa/CacheLRU.swift，个人觉得本文的实现不是很好，我写了新的版本，戳这里LRUCache

image

介绍

Cache LRU（最近最少使用）和字典很相似。通过Key-Value的方式存储。字典和Cache之间的区别在于后者的容量有限。每次达到容量时，Cache都会删除最近最少使用的数据。

在本文中，我们将看看如何使用Swift实现Cache LRU。

内容

入门指南
双链表
Cache LRU
总结

入门指南

首先，我们必须了解应该用什么数据结构来实现Cache LRU。有不同的方式来实现它。在这个版本中使用：

双链表：这是核心。我们需要这个链表来缓存元素。不使用数组，因为它更慢。Cache LRU策略是每次把最近使用的元素移到头部。但是如果我们将数组中的元素移到数组中的索引0处，需要对所有其他元素执行右移。
Dictionary<Key, ListNode>：使用双链表的问题是它的查找的时间复杂度是O（n）。可以使用一个字典来解决这个瓶颈 - 它的查找时间复杂度是O（1）。我们使用这个字典来存储列表的节点。

在下一节中，将看到如何实现双链表。如果你已经知道了，可以直接跳到Cache LRU部分。

双链表

对于本文，我们不需要实现完整的双向链表。出于这个原因，只实现Cache中使用到的的方法。

第一步是创建一个类DoublyLinkedList，它接受一个泛型T来存储节点：

final class DoublyLinkedList<T> {   

}

然后为节点创建一个类：

final class DoublyLinkedList<T> {
 
    final class Node<T> {
        var payload: T
        var previous: Node<T>?
        var next: Node<T>?
 
        init(payload: T) {
            self.payload = payload
        }
    }
}

在这里使用一个嵌套的Node类。如果你使用的是早于3.1的Swift版本，则必须在DoublyLinkedList之外创建此类。 Swift 3.1支持具有泛型的嵌套类。

然后，设置链表的存储最大量：

private(set) var count: Int = 0

链表上的操作有时实现起来很困难。可以存储第一个和最后一个元素，让一切更轻松：

private var head: Node<T>?
private var tail: Node<T>?

现在开始实现链表中的方法：

addHead

我们需要一个向链表中添加新元素的方法，这个新元素就是最近使用的元素。

func addHead(_ payload: T) -> Node<T> {
    let node = Node(payload: payload)
    defer {
        head = node
        count += 1
    }
 
    guard let head = head else {
        tail = node
        return node
    }
 
    head.previous = node
 
    node.previous = nil
    node.next = head
 
    return node
}

moveToHead

Cache LRU需要我们将最近使用的元素放在列表头部。因此需要一个方法把节点移动到头部：

func moveToHead(_ node: Node<T>) {
    guard node !== head else { return }
    let previous = node.previous
    let next = node.next
 
    previous?.next = next
    next?.previous = previous
 
    node.next = head
    node.previous = nil
 
    if node === tail {
        tail = previous
    }
 
    self.head = node
}

removeLast

当Cache已满时，需要一个方法来删除最久未使用的元素

func removeLast() -> Node<T>? {
    guard let tail = self.tail else { return nil }
 
    let previous = tail.previous
    previous?.next = nil
    self.tail = previous
 
    if count == 1 {
        head = nil
    }
 
    count -= 1
 
    // 1
    return tail
}

tail的值与self.tail不同。

最后，可以为Node类型添加一个别名，以便在Cache实现中使用：

typealias DoublyLinkedListNode<T> = DoublyLinkedList<T>.Node<T>

链表实现的最终版本应该是这样的：

typealias DoublyLinkedListNode<T> = DoublyLinkedList<T>.Node<T>
 
final class DoublyLinkedList<T> {
    final class Node<T> {
        var payload: T
        var previous: Node<T>?
        var next: Node<T>?
 
        init(payload: T) {
            self.payload = payload
        }
    }
 
    private(set) var count: Int = 0
 
    private var head: Node<T>?
    private var tail: Node<T>?
 
    func addHead(_ payload: T) -> Node<T> {
        let node = Node(payload: payload)
        defer {
            head = node
            count += 1
        }
 
        guard let head = head else {
            tail = node
            return node
        }
 
        head.previous = node
 
        node.previous = nil
        node.next = head
 
        return node
    }
 
    func moveToHead(_ node: Node<T>) {
        guard node !== head else { return }
        let previous = node.previous
        let next = node.next
 
        previous?.next = next
        next?.previous = previous
 
        node.next = head
        node.previous = nil
 
        if node === tail {
            tail = previous
        }
 
        self.head = node
    }
 
    func removeLast() -> Node<T>? {
        guard let tail = self.tail else { return nil }
 
        let previous = tail.previous
        previous?.next = nil
        self.tail = previous
 
        if count == 1 {
            head = nil
        }
 
        count -= 1
 
        return tail
    }
}

Cache LRU

现在是时候实现Cache了。我们可以开始创建一个新的CacheLRU类：

泛型Key必须是Hashable类型，因为它是存储在双链表中的值的key。

Cache和字典一样是通过Key-Value方式存储数据。不幸的是，我们的双链表值只能是payload，而不能是一个key。为了解决这个问题，可以创建一个包含value和key的结构体。链表节点将存储包含value和key的对象CachePayload：

final class CacheLRU<Key: Hashable, Value> {
 
    private struct CachePayload {
        let key: Key
        let value: Value
    }
}

然后，我们应该添加两个数据结构 - 一个双链表和一个字典：

private let list = DoublyLinkedList<CachePayload>()
private var nodesDict = [Key: DoublyLinkedListNode<CachePayload>]()

正如在介绍中看到的那样，Cache LRU的容量有限。我们可以通过init方法把容量传给一个私有属性：

private let capacity: Int
 
init(capacity: Int) {
    self.capacity = max(0, capacity)
}

使用max方法来避免capacity小于0。

现在实现两个Cache方法来get和set元素：

setValue

通过set方法，可以为某个key添加/更新元素。这个值作为最近使用的元素移动到链表的开头：

func setValue(_ value: Value, for key: Key) {
    // 1
    let payload = CachePayload(key: key, value: value)
 
    // 2
    if let node = nodesDict[key] {
        node.payload = payload
        list.moveToHead(node)
    } else {
        let node = list.addHead(payload)
        nodesDict[key] = node
    }
 
    // 3
    if list.count > capacity {
        let nodeRemoved = list.removeLast()
        if let key = nodeRemoved?.payload.key {
            nodesDict[key] = nil
        }
    }
}

创建一个对象来包装要存储在列表中的key和value。
如果链表已经存储了该特定key的元素，更新该值并将其移动到列表的开头。否则，创建一个新节点并将其添加为列表的头部。
如果超过了Cache容量，删除链表最后一个元素。

getValue

使用get方法，可以拿到特定key的元素。每次使用一个元素时，它都会作为最近使用的元素移动到链表的头部：

func getValue(for key: Key) -> Value? {
    guard let node = nodesDict[key] else { return nil }
 
    list.moveToHead(node)
 
    return node.payload.value
}

Cache最终版本是这样的：

final class CacheLRU<Key: Hashable, Value> {
 
    private struct CachePayload {
        let key: Key
        let value: Value
    }
 
    private let capacity: Int
    private let list = DoublyLinkedList<CachePayload>()
    private var nodesDict = [Key: DoublyLinkedListNode<CachePayload>]()
 
    init(capacity: Int) {
        self.capacity = max(0, capacity)
    }
 
    func setValue(_ value: Value, for key: Key) {
        let payload = CachePayload(key: key, value: value)
 
        if let node = nodesDict[key] {
            node.payload = payload
            list.moveToHead(node)
        } else {
            let node = list.addHead(payload)
            nodesDict[key] = node
        }
 
        if list.count > capacity {
            let nodeRemoved = list.removeLast()
            if let key = nodeRemoved?.payload.key {
                nodesDict[key] = nil
            }
        }
    }
 
    func getValue(for key: Key) -> Value? {
        guard let node = nodesDict[key] else { return nil }
 
        list.moveToHead(node)
 
        return node.payload.value
    }
}

我们可以像这样使用这个Cache：

let cache = CacheLRU<Int, String>(capacity: 2)
 
cache.getValue(for: 5) // nil
 
cache.setValue("One", for: 1)
cache.setValue("Eleven", for: 11)
cache.setValue("Twenty", for: 20)
 
cache.getValue(for: 1) // nil. We exceeded the capacity with the previous `setValue`  and `1` was the last element.
cache.getValue(for: 11) // Eleven

总结

这就是我们的Cache LRU了。

如今，我们应用程序有很多内存可用。尽管如此，可能仍需要一个容量有限的缓存来节省内存空间。例如，当我们必须缓存像图像那样耗费空间的对象时。

Update:
我发现Array比链表快。因为Cache LRU的版本使用双链表，所以我抛弃了这种的作法。