LRU Cache是一种缓存的常用机制:在YYCache中,内存级别是使用双链表结合字典实现的，更新与获取时间复杂度都是o(1);磁盘级别直接使用的最近存储时间，根据数据库实现的;SDWebImage中是直接根据文件的存储时间来实现的。
1. 数组结合字典
class LRUCache: NSObject {
var dict:Dictionary<Int, Int>
var arr:[Int]
var max = 0
init(_ capacity: Int) {
max = capacity
arr = Array.init(repeating: -1, count: max)
dict = Dictionary.init(minimumCapacity: max)
}
func get(_ key: Int) -> Int {
if max == 0 {
return -1
}
if dict[key] != -1 {//已存在的数据进行查找与移动
let index = findArrIndex(value: key, arr: arr)//查找时间复杂度是o(n)
if index != -1 {
moveForward(index: index, arr: &arr)//移动时间复杂度是o(n)
}
}
return (dict[key] == nil ? -1 : dict[key])!
}
func put(_ key: Int, _ value: Int) {
if max == 0 {
return
}
//如果缓存已存在，把key移动到最近的位置，更新字典
if dict[key] != nil {
let index = findArrIndex(value: key, arr: arr)
if index != -1 {
moveForward(index: index, arr: &arr)
dict.updateValue(value, forKey: key)
return
}
}
if arr.count == max {
dict.removeValue(forKey: arr.first!)
arr.removeFirst()//移除队头，时间复杂度是o(n)
}
dict.updateValue(value, forKey: key)
arr.append(key)
}
func moveForward(index:Int,arr:inout [Int]) {
let tmp = arr[index]
for i in index..<arr.count-1 {
arr[i] = arr[i+1]
}
arr[arr.count-1] = tmp
}
func findArrIndex(value:Int,arr:[Int]) -> Int {
for i in 0..<arr.count {
if value == arr[i] {
return i
}
}
return -1
}
}
数组尾部为队头
在put时，需要检查缓存是否已经存在，如果有移动到末尾，查找和移动是线性的，时间复杂度是o(n)
get时，如果key存在需要移动到数组尾部，查找与移动的时间复杂度是o(n)
2. 双链表结合字典
数据结构是字典结合双链表，参考YYCache的实现。字典存储的是链表节点。
class DoubleLink : NSObject {
var _head:DoubleLinkNode?
var _tail:DoubleLinkNode?
//新的节点插入到头位置
func insertNodeAtHead(node:DoubleLinkNode) {
if (_head != nil) {
node.next = _head;
_head!.prev = node;
_head = node;
} else {
_tail = node
_head = _tail;
}
}
func insertNodeAtTail(node:DoubleLinkNode) {
if (_tail == nil) {
_head = node;
_tail = node
} else {
_tail?.next = node
node.prev = _tail
_tail = node
}
}
//已在链表的节点移动到头位置
func bringNodeToHead(node:DoubleLinkNode) {
if _head == node {
return
}
if (_tail == node) {
//当前节点是最后一个节点
_tail = node.prev;
_tail!.next = nil;
} else {
//从列表中移除当前节点
node.next.prev = node.prev;
node.prev.next = node.next;
}
node.next = _head;
node.prev = nil;
_head!.prev = node;
_head = node;
}
func removeNode(node:DoubleLinkNode) {
if (node.next != nil) {
node.next.prev = node.prev;
}
if (node.prev != nil) {
node.prev.next = node.next;
}
if (_head == node) {
_head = node.next;
}
if (_tail == node) {
_tail = node.prev;
}
}
func removeTailNode() -> DoubleLinkNode? {
if (_tail == nil) {
return nil;
}
let tail = _tail;
if (_head == _tail) {
_tail = nil
_head = nil;
} else {
_tail = _tail!.prev;
_tail!.next = nil;
}
return tail;
}
}
//头部为最近使用
class LRUCacheAdvanced: NSObject {
var dict:Dictionary<Int, DoubleLinkNode>!
var max = 0
var doubleLink:DoubleLink = DoubleLink()
init(_ capacity: Int) {
max = capacity
dict = Dictionary.init(minimumCapacity: max)
}
func get(_ key: Int) -> Int {
if max == 0 {
return -1
}
let node = dict[key]
if node != nil {//已存在的数据进行查找与移动
doubleLink.bringNodeToHead(node: node!)
}
return (node?.value == nil ? -1 : node!.value)!
}
func put(_ key: Int, _ value: Int) {
if max == 0 {
return
}
//如果缓存已存在，把key移动到最近的位置，更新字典
var node = dict[key]
if node == nil {
if dict.values.count == max {
let tail = doubleLink.removeTailNode()
dict.removeValue(forKey: tail!.key)
}
node = DoubleLinkNode.init(k: key, v: value)
doubleLink.insertNodeAtHead(node: node!)
}else{
node?.value = value
doubleLink.bringNodeToHead(node: node!)
}
dict.updateValue(node!, forKey: key)
}
}
在查找时，通过key在字典中找到对应的链表节点，删除当前节点，插入到头部；
查找、删除、移动时间复杂度是o(1)。
3. 测试用例
func testExample() {
let cache = LRUCache.init(2)
cache.put(1, 1);
cache.put(2, 2);
XCTAssertTrue(cache.get(1) == 1); // 返回 1
cache.put(3, 3); // 该操作会使得关键字 2 作废
XCTAssertTrue(cache.get(2) == -1); // 返回 -1 (未找到)
cache.put(4, 4); // 该操作会使得关键字 1 作废
XCTAssertTrue(cache.get(1) == -1); // 返回 -1 (未找到)
XCTAssertTrue(cache.get(3) == 3); // 返回 3
XCTAssertTrue(cache.get(4) == 4); // 返回 4
}
func testExample2() {
let cache = LRUCache.init(2)
cache.put(1, 1);
cache.put(2, 2);
cache.put(3, 3);
XCTAssertTrue(cache.get(1) == -1); // 返回 1
cache.put(3, 3); // 该操作会使得关键字 2 作废
XCTAssertTrue(cache.get(2) == 2); // 返回 -1 (未找到)
}
func testExample3() {
let cache = LRUCache.init(0)
cache.put(1, 1)
XCTAssertTrue(cache.get(1) == -1)
}
func testAdvanced() {
let cache = LRUCacheAdvanced.init(2)
cache.put(1, 1);
cache.put(2, 2);
XCTAssertTrue(cache.get(1) == 1); // 返回 1
cache.put(3, 3); // 该操作会使得关键字 2 作废
XCTAssertTrue(cache.get(2) == -1); // 返回 -1 (未找到)
cache.put(4, 4); // 该操作会使得关键字 1 作废
XCTAssertTrue(cache.get(1) == -1); // 返回 -1 (未找到)
XCTAssertTrue(cache.get(3) == 3); // 返回 3
XCTAssertTrue(cache.get(4) == 4); // 返回 4
}
func testAdvanced2() {
let cache = LRUCacheAdvanced.init(2)
cache.put(1, 1);
cache.put(2, 2);
cache.put(3, 3);
XCTAssertTrue(cache.get(1) == -1); // 返回 1
cache.put(3, 3); // 该操作会使得关键字 2 作废
XCTAssertTrue(cache.get(2) == 2); // 返回 -1 (未找到)
}
func testAdvanced3() {
let cache = LRUCacheAdvanced.init(0)
cache.put(1, 1)
XCTAssertTrue(cache.get(1) == -1)
}
func testAdvanced4() {
let cache = LRUCacheAdvanced.init(2)
cache.put(2, 1);
cache.put(2, 2);
XCTAssertTrue(cache.get(2) == 2); // 返回 1
cache.put(1, 1);
cache.put(4, 1); // 该操作会使得关键字 2 作废
XCTAssertTrue(cache.get(2) == -1); // 返回 -1 (未找到)
}
小结:
- 先实现功能，再考虑优化
- 分析每步耗时，看看能否有优化空间
