算法

LRU 实现+实际应用

文章目录
  1. 1. 使用单链表，双链表
  2. 2. 使用数组
  3. 3. 哈希链表

目前分析几种 LRU 实现

LRU：Least Recently Used 最近最久未使用
常用于大量数据中只会频繁调用部分数据的优化算法
在 OS 中缓存算法（页面置换算法）-FIFO、LFU、LRU

实例分析，假如os分给进程的页面大小为3，序列为4、3、2、3、5，下面的缺页次数为4次

43235
43235
null4323
nullnull442
缺页缺页缺页不缺缺页

使用单链表，双链表

如果只是使用链表存储数据结构

  1. 查询：每次都需要遍历 list 插到指定 node。 O(n)
  2. 插入：O(n)
    1. 先遍历 list 找到 node，然后断链
    2. 把 node 放在 head 位置，原来断链地方复原
    3. 如果不存在那就需要读磁盘数据，放在 list head 位置，然后把 list.end 删除。

使用数组

  1. 查询：每次遍历数组找到 idx。 O(n)
  2. 插入：O(n) 数组大量位置移动
    1. 遍历 array 查找 idx
    2. 将 array[idx] 放在数组头位置。时间复杂度 O(n)
    3. 如果不在这个位置需要，读磁盘放在数组array 位置
  3. 优化方案，可以把最近使用的数据放在 array 末尾位置减少数组移动的问题
    1. 但是如果多次未命中，磁盘数据每次插到 array 首位，也会大量移动数据
    2. 如果多次未命中说明不该使用 LRU 了呀

哈希链表

根据前两种设计方式，耗时的地方是遍历
使用 hashmap 可以解决遍历问题，可是 hashmap 是无序的，那么 hashmap + list呢(+array
不存在的……)？
hashmap 不是连续的，那么就是用 list 来维护有序性
使用单向链表，移动节点的时候，找到 node 以后，断链问题需要找到 prev 节点，所以还需要重头遍历 O(n)
如果使用双向链表，就可以解决前置节点问题

所以最终使用 hashmap + doublelist 处理 LRU

  1. 查询：使用 hashmap O(1)
  2. 插入：O(1)
    1. put hashmap，更新 list

算法实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
class LRUCache {
  class Node: Equatable, CustomStringConvertible {
    var val: Int?
    var key: Int?
    var prev: Node?
    var next: Node?

    static func == (lhs: Node, rhs: Node) -> Bool {
      return lhs.val == rhs.val
    }

    var description: String {
      if let _ = key,
        let v = val{
        return "\(v) "
      }else {
        return "head-tail"
      }
    }
  }
  
  var map: [Int: Node]!
  let head = Node()
  let tail = Node()
  let capacity: Int
  
  init(_ capacity: Int) {
    self.capacity = capacity
    map = [Int: Node].init(minimumCapacity: capacity)
    head.next = tail
    tail.prev = head
  }
  
  private func moveToHead(_ n: Node) {
    n.prev?.next = n.next
    n.next?.prev = n.prev

    n.next = head.next
    head.next = n
    n.next?.prev = n
    n.prev = head
  }
  
  private func deleteNode(_ n: Node){
    n.prev?.next = n.next
    n.next?.prev = n.prev
    n.prev = nil; n.next = nil
  }
  
  private func addNodeToCache(_ n: Node) {
    map[n.key!] = n
    moveToHead(n)

    if map.count > capacity {// 超出缓存拿走
      if let n = tail.prev,
        let k = n.key {
        map.removeValue(forKey: k)
        deleteNode(n)
      }
    }
  }
  
  func get(_ key: Int) -> Int {
    if let n = map[key] {
      moveToHead(n)
      return n.val!
    }else {
      return -1
    }
  }
  
  func put(_ key: Int, _ value: Int) {
    if let n = map[key] { // update value
      n.val = value
      moveToHead(n)
    } else {
      let n = Node()
      n.key = key
      n.val = value
      addNodeToCache(n)
    }
  }
}