《iOS面试题整理》- LRU 算法

数组实现

 var cache: [Int] = []
let maxCount = 5 // 缓存最大值

extension Array where Element: Equatable {
    mutating func remove(_ object: Element) {
        if let index = index(of: object) {
            remove(at: index)
        }
    }
}

func LRU (data : Int){
    // 如果没有缓存
    if !cache.contains(data) {
        // 数组满了, 移除最后一个数据
        if cache.count == maxCount { cache.removeLast() }
    } else {
        cache.remove(data)
    }
    cache.insert(data, at: 0)
}

LRU(data: 1)
LRU(data: 2)
LRU(data: 3)
LRU(data: 4)
LRU(data: 5)

print(cache)

// 数组满了
LRU(data: 6)
print(cache)

// 相同元素
LRU(data: 4)
print(cache)

输出
[5, 4, 3, 2, 1]
[6, 5, 4, 3, 2]
[4, 6, 5, 3, 2]

链表实现

  class ListNode<T> {
    var value: T
    var previous: ListNode?
    var next : ListNode?
    init(_ value: T) {
        self.value = value
    }
}

class List<T> {
    typealias Node = ListNode<T>
    
    private var head: Node?
    private var tail: Node?
    
    // 判断是否为空
    var isEmpty: Bool { return head == nil }
    
    // 获取头节点
    var first: Node? { return head }
    
    // 获取尾节点
    var last : Node? { return tail }
    
    // 链表数量
    var count: Int = 0;
    
    // 下标
    subscript(index: Int) -> T? {
        var i = index
        var next = head
        while i > 0 {
            i -= 1
            next = next?.next
        }
        return next?.value
    }
    
    // 插入尾部
    func insert(value : T) {
        
        let newNode = Node(value)
        
        if let first = head {
            newNode.next = first
            first.previous = newNode
            head = newNode;
        } else {
            head = newNode
            tail = newNode
        }
        count += 1
    }
    
    // 移除某个节点
    func remove(node: Node) {
        
        let pre = node.previous
        let next = node.next
        
        pre?.next = next
        next?.previous = pre
        
        if pre == nil { head = node.next }
        if tail == nil { tail = node.previous }
        
        count -= 1
    }
    
    // 移除最后一个节点
    func removeLast() {
        remove(node: last!)
    }
    
    // 移动某个节点到头部
    func moveToHead(node: Node) {
        
        let pre = node.previous
        let next = node.next
        
        pre?.next = next
        next?.previous = pre
        
        node.next = head
        head?.previous = node
        
        head = node
        
        if pre == nil { return }
        if next == nil  { tail = pre}
    }
}

class CacheLRU<T> {
    var limit : Int
    var cache : List<T>
    init(cacheCount: Int) {
        self.limit = cacheCount
        self.cache = List<T>()
    }
    
    // 添加数据
    func add(value: T) {
        if cache.count == limit { cache.removeLast()}
        cache.insert(value:value)
    }
    
    // 移动数据
    func move(value: ListNode<T>) {
        cache.moveToHead(node: value)
    }
}

extension List where T == Dictionary<String, String> {
    // 判断链表是否含有缓存
    func contains(name: String) -> Node? {
        var next = head
        var index = 0
        while index < count {
            if next?.value[name] != nil { return next }
            index += 1
            next = next?.next
        }
        return nil;
    }
    
    // 打印 log 信息
    func log() {
        var next = head
        while next != nil {
            print(next?.value as Any)
            next = next?.next
        }
    }
}

extension CacheLRU where T == Dictionary<String, String> {
    
    // 访问已有的数据
    func fetch(key : String) {
        let node = cache.contains(name: key)
        if let dic = node?.value {
            // 存在的话, 直接取数据
            print(dic)
            
            // 移动到头节点
            move(value: node!)
        } else {
            
        }
    }
}

let cacheManager = CacheLRU<Dictionary<String, String>>(cacheCount: 2)
let value1 = ["1" : "测试1"]
let value2 = ["2" : "测试2"]
let value3 = ["3" : "测试3"]

// 模拟添加数据
cacheManager.add(value: value1)
cacheManager.add(value: value2)
cacheManager.add(value: value3)
cacheManager.cache.log()

// 模拟访问数据
cacheManager.fetch(key: "2")
cacheManager.cache.log()


输出
添加数据
Optional(["3": "测试3"])
Optional(["2": "测试2"])
访问数据
["2": "测试2"]
Optional(["2": "测试2"])
Optional(["3": "测试3"])