LRU 算法

 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
84

+---------------------------------+
|                                 |
|  type DLinkedList struct {      |
|      Key, Val int               |
|      Pre, Next *DLinkedList     |
|  }                              |
|                                 +----> // 基础数据结构（双链表实现LRU缓存）
|  type LRUCache struct {         |
|      size int                   |
|      capacity int               |
|      cache map[int]*DLinkedList |
|      head, tail *DLinkedList    |
|  }                              |
+---------------------------------+
   func Constructor(capacity int) LRUCache {
       l := LRUCache {
               capacity : capacity,
               cache : map[int]*DLinkedList{},
               head : &DLinkedList{},
               tail : &DLinkedList{},
       }
       l.head.Next = l.tail
       l.tail.Pre = l.head
       return l
   }


 +-------------------------------------------------------+
 | func (l *LRUCache) Get(key int) int {                 |
 |     if _, ok := l.cache[key]; !ok {                   |
 |             return -1                                 |
 |     }                                                 |
 |     node := l.cache[key]                              |
 |     l.moveToHead(node)                                |
 |     return node.Val                                   |
 | }                                                     |
 |                                                       |
 | func (lru *LRUCache) Put(key int, value int)  {       |
 |     if node, ok := lru.cache[key]; ok {               |
 |             node.Val = value                          |
 |             lru.moveToHead(node)                      +--> // 核心操作 get put 取 存
 |             return                                    |
 |     }                                                 |
 |     newNode := &DLinkedList{                          |
 |             Key : key,                                |
 |             Val : value,                              |
 |     }                                                 |
 |     if lru.size!= 0 && lru.size == lru.capacity {     |
 |             lru.removeTail()                          |
 |             lru.size--                                |
 |     }                                                 |
 |     lru.addNewNode(newNode)                           |
 |     lru.size++                                        |
 |     lru.cache[key] = newNode                          |
 | }                                                     |
 +-------------------------------------------------------+

 +-------------------------------------------------------+
 | func (l *LRUCache) removeNode(node *DLinkedList) {    |
 |     node.Pre.Next = node.Next                         |
 |     node.Next.Pre = node.Pre                          |
 | }                                                     |
 | func (l *LRUCache) moveToHead(node *DLinkedList) {    |
 |     l.removeNode(node)                                |
 |     l.addNewNode(node)                                |
 | }                                                     |
 |                                                       |
 | func (l *LRUCache) removeTail() {                     |
 |                                                       |
 |     node := l.tail.Pre                                |
 |     delete(l.cache, node.Key)                         |
 |     node.Pre.Next = node.Next                         +----> // 辅助函数
 |     node.Next.Pre = node.Pre                          |
 | }                                                     |
 |                                                       |
 | func (l *LRUCache) addNewNode(node *DLinkedList) {    |
 |     next := l.head.Next                               |
 |     node.Next = next                                  |
 |     node.Pre = l.head                                 |
 |     l.head.Next = node                                |
 |     next.Pre = node                                   |
 | }                                                     |
 |                                                       |
 +-------------------------------------------------------+

 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

// import "github.com/stretchr/testify/assert"

func TestLRU(t *testing.T) {
    assert := assert.New(t)
    input1 := []string{"LRUCache","put","put","get","put","get","put","get","get","get"}
    input2 := [][]int{{2},{1,1},{2,2},{1},{3,3},{2},{4,4},{1},{3},{4}}
    
    expected_res := []interface{}{nil, nil, nil, 1, nil, -1, nil, -1, 3, 4}
    real_res := ExecLRU(input1, input2)
    assert.Equal(expected_res, real_res)
}

func ExecLRU(input1 []string, input2 [][]int) []interface{} {
    l := Constructor(input2[0][0])
    res := []interface{}{nil}
    for i, v := range input1 {
        if i == 0 {
            continue
        }
        if v == "put" {
            l.Put(input2[i][0], input2[i][1])
            res = append(res, nil)
        } else if v == "get" {
            tmp := l.Get(input2[i][0])
            res = append(res, tmp)
        }
    }
    return res
}