一.LRU簡介

LRU（Least recently used顶霞，最近最少使用）算法根據(jù)數(shù)據(jù)的歷史訪問記錄來進(jìn)行淘汰數(shù)據(jù)，其核心思想是“如果數(shù)據(jù)最近被訪問過，那么將來被訪問的幾率也更高”。
見leetcode146題:
LRU緩存機(jī)制

二.在iOS中的運(yùn)用

實(shí)現(xiàn)一個 Memory Cache 類 LRUCache模孩，使用 LRU 淘汰策略，它有容量上的限制 capacity贮缅，實(shí)現(xiàn)接口：

- (id)initWithCapacity:(NSInteger)capacity;
- (void)setItem:(id)item forKey:(NSString *)key;
- (id)getItemForKey:(NSString *)key;

分析:
使用雙向鏈表實(shí)現(xiàn),可以在時間復(fù)雜度O(1)內(nèi)完成刪除和插入的操作.

模版代碼

class LRUCache {

    init(_ capacity: Int) {
        
    }
    
    func get(_ key: Int) -> Int {
        
    }
    
    func put(_ key: Int, _ value: Int) {
        
    }
}

三.實(shí)現(xiàn)

1.先實(shí)現(xiàn)鏈表節(jié)點(diǎn)

class ListNode {
    var key: Int
    var value: Int
    var next: ListNode?
    var prev: ListNode?
    
    init(key: Int, value: Int) {
        self.key = key
        self.value = value
    }
}

2.實(shí)現(xiàn)LRUCache

class LRUCache {
    private var cache = [Int: ListNode]()
    // 最大size
    private var max_size = 0
    // 當(dāng)前size
    private var cur_size = 0
    // 頭
    private var head: ListNode?
    // 尾
    private var tail: ListNode?
    
    init(_ capacity: Int) {
        max_size = capacity
    }
    
    public func get(_ key: Int) -> Int {
        if let node = cache[key] {
            moveToHead(node: node)
            return node.value
        }
        return -1
    }
    
    public func put(_ key: Int, _ value: Int) {
        if let node = cache[key] {
            node.value = value
            moveToHead(node: node)
        } else {
            let node = ListNode(key: key, value: value)
            
            addNode(node: node)
            cache[key] = node
            
            cur_size += 1
            if cur_size > max_size {
                removeTail()
                cur_size -= 1
            }
        }
    }
    
    /// 添加節(jié)點(diǎn)到頭部
    private func addNode(node: ListNode) {
        if self.head == nil {
            self.head = node
            self.tail = node
        } else {
            let temp = self.head!
            self.head = node
            self.head?.next = temp
            temp.prev = self.head
        }
    }
    
    /// 移動到頭部
    private func moveToHead(node: ListNode) {
        if node === self.head {
            return
        }
        
        let prev = node.prev
        let next = node.next
        prev?.next = next
        if next != nil {
            next!.prev = prev
        } else {
            self.tail = prev
        }
        let origin = self.head
        self.head = node
        self.head?.next = origin
        origin?.prev = self.head
    }
    
    /// 刪除尾部
    @discardableResult
    private func removeTail() -> ListNode? {
        if let tail = self.tail {
            cache.removeValue(forKey: tail.key)
            self.tail = tail.prev
            self.tail?.next = nil
            return tail
        }
        return nil
    }
}

四.測試用例

let cache = LRUCache(2)
cache.put(1, 1)
cache.put(2, 2)
cache.get(1)
cache.put(3, 3)
cache.get(2)

// ["LRUCache","put","put","put","put","get","get","get","get","put","get","get","get","get","get"]
// [[3],[1,1],[2,2],[3,3],[4,4],[4],[3],[2],[1],[5,5],[1],[2],[3],[4],[5]]

let cache = LRUCache(3)
cache.put(1, 1)
cache.put(2, 2)
cache.put(3, 3)
cache.put(4, 4)
print(cache.get(4))
print(cache.get(3))
print(cache.get(2))
print(cache.get(1))
cache.put(5, 5)
print(cache.get(1))
print(cache.get(2))
print(cache.get(3))
print(cache.get(4))
print(cache.get(5))

// ["LRUCache","put","get","put","get","get"]
// [[1],[2,1],[2],[3,2],[2],[3]]
let cache = LRUCache(1)
cache.put(2, 1)
print(cache.get(2))
cache.put(3, 2)
print(cache.get(2))
print(cache.get(3))