算法设计-LRU与LFU

 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

type LRUCache struct {
	size, capacity int
	head, tail     *KVNode
	cache          map[int]*KVNode
}

type KVNode struct {
	prev, next *KVNode
	key, value int
}

func NewKVNode(key, value int) *KVNode {
	return &KVNode{
		key:   key,
		value: value,
	}
}

func Constructor(capacity int) LRUCache {
	lru := LRUCache{
		size:     0,
		capacity: capacity,
		head:     NewKVNode(0, 0),
		tail:     NewKVNode(0, 0),
		cache:    map[int]*KVNode{},
	}
	lru.head.next = lru.tail
	lru.tail.prev = lru.head
	return lru
}

func (lru *LRUCache) Get(key int) int {
	if node, ok := lru.cache[key]; ok {
		lru.MoveToHead(node)
		return node.value
	}
	return -1
}

func (lru *LRUCache) Put(key int, value int) {
	if node, ok := lru.cache[key]; ok {
		node.value = value
		lru.MoveToHead(node)
		return
	}
	newNode := &KVNode{key: key, value: value}
	lru.InsertToHead(newNode)
	lru.size++
	lru.cache[key] = newNode
	if lru.size > lru.capacity {
		lastNode := lru.RemoveTail()
		lru.size--
		delete(lru.cache, lastNode.key)
	}
}

func (lru *LRUCache) MoveToHead(node *KVNode) {
	lru.RemoveNode(node)
	lru.InsertToHead(node)
}

func (lru *LRUCache) InsertToHead(node *KVNode) {
	node.prev = lru.head
	node.next = lru.head.next
	lru.head.next.prev = node
	lru.head.next = node
}

func (lru *LRUCache) RemoveTail() *KVNode {
	lastNode := lru.tail.prev
	lru.RemoveNode(lru.tail.prev)
	return lastNode
}

func (lru *LRUCache) RemoveNode(node *KVNode) {
	node.prev.next = node.next
	node.next.prev = node.prev
}

  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
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107

type KVNode struct {
	prev, next *KVNode
	key, value int
	freq       int
}

type DoubleList struct {
	head, tail *KVNode
	size       int
}

func NewDoubleList() *DoubleList {
	dl := &DoubleList{
		head: &KVNode{ key: 0, value: 0},
		tail: &KVNode{ key: 0, value: 0},
		size: 0,
	}
	dl.head.next = dl.tail
	dl.tail.prev = dl.head
	return dl
}

func (dl *DoubleList) PushFront(node *KVNode) {
	node.prev = dl.head
	node.next = dl.head.next
	dl.head.next.prev = node
	dl.head.next = node
	dl.size++
}

func (dl *DoubleList) RemoveBack() *KVNode {
	lastNode := dl.tail.prev
	dl.Remove(lastNode)
	return lastNode
}

func (dl *DoubleList) Remove(node *KVNode) {
	node.prev.next = node.next
	node.next.prev = node.prev
	dl.size--
}

type LFUCache struct {
	cache                   map[int]*KVNode
	freq                    map[int]*DoubleList
	capacity, size, minFreq int
}

func Constructor(capacity int) LFUCache {
	return LFUCache{
		cache:    map[int]*KVNode{},
		freq:     map[int]*DoubleList{},
		capacity: capacity,
		size:     0,
		minFreq:  0,
	}
}

func (lfu *LFUCache) IncFreq(node *KVNode) {
	preFreq := node.freq
	lfu.freq[preFreq].Remove(node)
	if preFreq == lfu.minFreq && lfu.freq[preFreq].size == 0 {
		lfu.minFreq++
		delete(lfu.freq, preFreq)
	}
	node.freq++
	if lfu.freq[node.freq] == nil {
		lfu.freq[node.freq] = NewDoubleList()
	}
	lfu.freq[node.freq].PushFront(node)
}

func (lfu *LFUCache) Get(key int) int {
	if node, ok := lfu.cache[key]; ok {
		lfu.IncFreq(node)
		return node.value
	}
	return -1
}

func (lfu *LFUCache) Put(key int, value int) {
	if lfu.capacity == 0 {
		return
	}

	if node, ok := lfu.cache[key]; ok {
		node.value = value
		lfu.IncFreq(node)
		return
	}

	if lfu.size == lfu.capacity {
		node := lfu.freq[lfu.minFreq].RemoveBack()
		delete(lfu.cache, node.key)
		lfu.size--
		// No need to update minFreq because it will be set 1 below
	}

	node := &KVNode{ key: key, value: value, freq: 1}
	lfu.cache[key] = node
	if lfu.freq[1] == nil {
		lfu.freq[1] = NewDoubleList()
	}
	lfu.freq[1].PushFront(node)
	lfu.minFreq = 1
	lfu.size++
}