用Swift實(shí)現(xiàn)Cache LRU （譯文）

此文章為本人翻譯的譯文，版權(quán)為原作者所有。
英文原文：How To Implement Cache LRU With Swift

本文代碼地址MarcoSantarossa/CacheLRU.swift，個(gè)人覺得本文的實(shí)現(xiàn)不是很好，我寫了新的版本，戳這里LRUCache

image

介紹

Cache LRU（最近最少使用）和字典很相似。通過Key-Value的方式存儲(chǔ)。字典和Cache之間的區(qū)別在于后者的容量有限。每次達(dá)到容量時(shí)，Cache都會(huì)刪除最近最少使用的數(shù)據(jù)。

在本文中，我們將看看如何使用Swift實(shí)現(xiàn)Cache LRU。

內(nèi)容

  • 入門指南
  • 雙鏈表
  • Cache LRU
  • 總結(jié)

入門指南

首先，我們必須了解應(yīng)該用什么數(shù)據(jù)結(jié)構(gòu)來實(shí)現(xiàn)Cache LRU。有不同的方式來實(shí)現(xiàn)它。在這個(gè)版本中使用：

  • 雙鏈表：這是核心。我們需要這個(gè)鏈表來緩存元素。不使用數(shù)組，因?yàn)樗?。Cache LRU策略是每次把最近使用的元素移到頭部。但是如果我們將數(shù)組中的元素移到數(shù)組中的索引0處，需要對(duì)所有其他元素執(zhí)行右移。
  • Dictionary<Key, ListNode>：使用雙鏈表的問題是它的查找的時(shí)間復(fù)雜度是O（n）?？梢允褂靡粋€(gè)字典來解決這個(gè)瓶頸 - 它的查找時(shí)間復(fù)雜度是O（1）。我們使用這個(gè)字典來存儲(chǔ)列表的節(jié)點(diǎn)。

在下一節(jié)中，將看到如何實(shí)現(xiàn)雙鏈表。如果你已經(jīng)知道了，可以直接跳到Cache LRU部分。

雙鏈表

對(duì)于本文，我們不需要實(shí)現(xiàn)完整的雙向鏈表。 出于這個(gè)原因，只實(shí)現(xiàn)Cache中使用到的的方法。

第一步是創(chuàng)建一個(gè)類DoublyLinkedList，它接受一個(gè)泛型T來存儲(chǔ)節(jié)點(diǎn)：

final class DoublyLinkedList<T> {   

}

然后為節(jié)點(diǎn)創(chuàng)建一個(gè)類：

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
        }
    }
}

在這里使用一個(gè)嵌套的Node類。 如果你使用的是早于3.1的Swift版本，則必須在DoublyLinkedList之外創(chuàng)建此類。 Swift 3.1支持具有泛型的嵌套類。

然后，設(shè)置鏈表的存儲(chǔ)最大量：

private(set) var count: Int = 0

鏈表上的操作有時(shí)實(shí)現(xiàn)起來很困難?？梢源鎯?chǔ)第一個(gè)和最后一個(gè)元素，讓一切更輕松：

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

現(xiàn)在開始實(shí)現(xiàn)鏈表中的方法：

addHead

我們需要一個(gè)向鏈表中添加新元素的方法，這個(gè)新元素就是最近使用的元素。

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需要我們將最近使用的元素放在列表頭部。 因此需要一個(gè)方法把節(jié)點(diǎn)移動(dòng)到頭部：

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

當(dāng)Cache已滿時(shí)，需要一個(gè)方法來刪除最久未使用的元素

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
}
  1. tail的值與self.tail不同。

最后，可以為Node類型添加一個(gè)別名，以便在Cache實(shí)現(xiàn)中使用：

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

鏈表實(shí)現(xiàn)的最終版本應(yīng)該是這樣的：

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

現(xiàn)在是時(shí)候?qū)崿F(xiàn)Cache了。 我們可以開始創(chuàng)建一個(gè)新的CacheLRU類：

泛型Key必須是Hashable類型，因?yàn)樗谴鎯?chǔ)在雙鏈表中的值的key。

Cache和字典一樣是通過Key-Value方式存儲(chǔ)數(shù)據(jù)。不幸的是，我們的雙鏈表值只能是payload，而不能是一個(gè)key。 為了解決這個(gè)問題，可以創(chuàng)建一個(gè)包含value和key的結(jié)構(gòu)體。鏈表節(jié)點(diǎn)將存儲(chǔ)包含value和key的對(duì)象CachePayload：

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

然后，我們應(yīng)該添加兩個(gè)數(shù)據(jù)結(jié)構(gòu) - 一個(gè)雙鏈表和一個(gè)字典：

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

正如在介紹中看到的那樣，Cache LRU的容量有限。 我們可以通過init方法把容量傳給一個(gè)私有屬性：

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

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

現(xiàn)在實(shí)現(xiàn)兩個(gè)Cache方法來get和set元素：

setValue

通過set方法，可以為某個(gè)key添加/更新元素。這個(gè)值作為最近使用的元素移動(dòng)到鏈表的開頭：

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
        }
    }
}
  1. 創(chuàng)建一個(gè)對(duì)象來包裝要存儲(chǔ)在列表中的key和value。
  2. 如果鏈表已經(jīng)存儲(chǔ)了該特定key的元素，更新該值并將其移動(dòng)到列表的開頭。否則，創(chuàng)建一個(gè)新節(jié)點(diǎn)并將其添加為列表的頭部。
  3. 如果超過了Cache容量，刪除鏈表最后一個(gè)元素。

getValue

使用get方法，可以拿到特定key的元素。 每次使用一個(gè)元素時(shí)，它都會(huì)作為最近使用的元素移動(dòng)到鏈表的頭部：

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
    }
}

我們可以像這樣使用這個(gè)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

總結(jié)

這就是我們的Cache LRU了。

如今，我們應(yīng)用程序有很多內(nèi)存可用。 盡管如此，可能仍需要一個(gè)容量有限的緩存來節(jié)省內(nèi)存空間。例如，當(dāng)我們必須緩存像圖像那樣耗費(fèi)空間的對(duì)象時(shí)。

Update:
我發(fā)現(xiàn)Array比鏈表快。因?yàn)镃ache LRU的版本使用雙鏈表，所以我拋棄了這種的作法。

最后編輯于 ：
?著作權(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)容

  • Collection & Map Collection 子類有 List 和 Set List --> Array...
    任教主來也閱讀 3,318評(píng)論 1贊 9
  • 關(guān)于Mongodb的全面總結(jié) MongoDB的內(nèi)部構(gòu)造《MongoDB The Definitive Guide》...
    中v中閱讀 32,315評(píng)論 2贊 89
  • 從 YYCache 源碼 Get 到如何設(shè)計(jì)一個(gè)優(yōu)秀的緩存 來源：Lision 前言 iOS 開發(fā)中總會(huì)用到各種緩...
    今天lgw閱讀 6,273評(píng)論 1贊 22
  • 1、通過CocoaPods安裝項(xiàng)目名稱項(xiàng)目信息 AFNetworking網(wǎng)絡(luò)請(qǐng)求組件 FMDB本地?cái)?shù)據(jù)庫組件 SD...
    陽明AI閱讀 16,223評(píng)論 3贊 119
  • 目前更新到十集，我看了第一集就停不下來，一口氣看完，現(xiàn)在苦哈哈地等更新。 怎么說呢，豆瓣和知乎上的評(píng)價(jià)都不看好，雖...
    是唯伊不是唯一閱讀 467評(píng)論 3贊 0

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