Skip to content

Commit 38aa0ac

Browse files
halfrosthalfrost
committed
Add LFU/LRU template
1 parent fb72c85 commit 38aa0ac

File tree

2 files changed

+335
-0
lines changed

2 files changed

+335
-0
lines changed

‎template/LFUCache.go

Lines changed: 196 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,196 @@
1+
package template
2+
3+
import "container/list"
4+
5+
// LFUCache define
6+
type LFUCache struct {
7+
nodes map[int]*list.Element
8+
lists map[int]*list.List
9+
capacity int
10+
min int
11+
}
12+
13+
type node struct {
14+
key int
15+
value int
16+
frequency int
17+
}
18+
19+
// Constructor define
20+
func Constructor(capacity int) LFUCache {
21+
return LFUCache{nodes: make(map[int]*list.Element),
22+
lists: make(map[int]*list.List),
23+
capacity: capacity,
24+
min: 0,
25+
}
26+
}
27+
28+
// Get define
29+
func (lfuCache *LFUCache) Get(key int) int {
30+
value, ok := lfuCache.nodes[key]
31+
if !ok {
32+
return -1
33+
}
34+
currentNode := value.Value.(*node)
35+
lfuCache.lists[currentNode.frequency].Remove(value)
36+
currentNode.frequency++
37+
if _, ok := lfuCache.lists[currentNode.frequency]; !ok {
38+
lfuCache.lists[currentNode.frequency] = list.New()
39+
}
40+
newList := lfuCache.lists[currentNode.frequency]
41+
newNode := newList.PushFront(currentNode)
42+
lfuCache.nodes[key] = newNode
43+
if currentNode.frequency-1 == lfuCache.min && lfuCache.lists[currentNode.frequency-1].Len() == 0 {
44+
lfuCache.min++
45+
}
46+
return currentNode.value
47+
}
48+
49+
// Put define
50+
func (lfuCache *LFUCache) Put(key int, value int) {
51+
if lfuCache.capacity == 0 {
52+
return
53+
}
54+
if currentValue, ok := lfuCache.nodes[key]; ok {
55+
currentNode := currentValue.Value.(*node)
56+
currentNode.value = value
57+
lfuCache.Get(key)
58+
return
59+
}
60+
if lfuCache.capacity == len(lfuCache.nodes) {
61+
currentList := lfuCache.lists[lfuCache.min]
62+
backNode := currentList.Back()
63+
delete(lfuCache.nodes, backNode.Value.(*node).key)
64+
currentList.Remove(backNode)
65+
}
66+
lfuCache.min = 1
67+
currentNode := &node{
68+
key: key,
69+
value: value,
70+
frequency: 1,
71+
}
72+
if _, ok := lfuCache.lists[1]; !ok {
73+
lfuCache.lists[1] = list.New()
74+
}
75+
newList := lfuCache.lists[1]
76+
newNode := newList.PushFront(currentNode)
77+
lfuCache.nodes[key] = newNode
78+
}
79+
80+
/**
81+
* Your LFUCache object will be instantiated and called as such:
82+
* obj := Constructor(capacity);
83+
* param_1 := obj.Get(key);
84+
* obj.Put(key,value);
85+
*/
86+
87+
// Index Priority Queue
88+
// import "container/heap"
89+
90+
// type LFUCache struct {
91+
// capacity int
92+
// pq PriorityQueue
93+
// hash map[int]*Item
94+
// counter int
95+
// }
96+
97+
// func Constructor(capacity int) LFUCache {
98+
// lfu := LFUCache{
99+
// pq: PriorityQueue{},
100+
// hash: make(map[int]*Item, capacity),
101+
// capacity: capacity,
102+
// }
103+
// return lfu
104+
// }
105+
106+
// func (this *LFUCache) Get(key int) int {
107+
// if this.capacity == 0 {
108+
// return -1
109+
// }
110+
// if item, ok := this.hash[key]; ok {
111+
// this.counter++
112+
// this.pq.update(item, item.value, item.frequency+1, this.counter)
113+
// return item.value
114+
// }
115+
// return -1
116+
// }
117+
118+
// func (this *LFUCache) Put(key int, value int) {
119+
// if this.capacity == 0 {
120+
// return
121+
// }
122+
// // fmt.Printf("Put %d\n", key)
123+
// this.counter++
124+
// // 如果存在，增加 frequency，再调整堆
125+
// if item, ok := this.hash[key]; ok {
126+
// this.pq.update(item, value, item.frequency+1, this.counter)
127+
// return
128+
// }
129+
// // 如果不存在且缓存满了，需要删除。在 hashmap 和 pq 中删除。
130+
// if len(this.pq) == this.capacity {
131+
// item := heap.Pop(&this.pq).(*Item)
132+
// delete(this.hash, item.key)
133+
// }
134+
// // 新建结点，在 hashmap 和 pq 中添加。
135+
// item := &Item{
136+
// value: value,
137+
// key: key,
138+
// count: this.counter,
139+
// }
140+
// heap.Push(&this.pq, item)
141+
// this.hash[key] = item
142+
// }
143+
144+
// // An Item is something we manage in a priority queue.
145+
// type Item struct {
146+
// value int // The value of the item; arbitrary.
147+
// key int
148+
// frequency int // The priority of the item in the queue.
149+
// count int // use for evicting the oldest element
150+
// // The index is needed by update and is maintained by the heap.Interface methods.
151+
// index int // The index of the item in the heap.
152+
// }
153+
154+
// // A PriorityQueue implements heap.Interface and holds Items.
155+
// type PriorityQueue []*Item
156+
157+
// func (pq PriorityQueue) Len() int { return len(pq) }
158+
159+
// func (pq PriorityQueue) Less(i, j int) bool {
160+
// // We want Pop to give us the highest, not lowest, priority so we use greater than here.
161+
// if pq[i].frequency == pq[j].frequency {
162+
// return pq[i].count < pq[j].count
163+
// }
164+
// return pq[i].frequency < pq[j].frequency
165+
// }
166+
167+
// func (pq PriorityQueue) Swap(i, j int) {
168+
// pq[i], pq[j] = pq[j], pq[i]
169+
// pq[i].index = i
170+
// pq[j].index = j
171+
// }
172+
173+
// func (pq *PriorityQueue) Push(x interface{}) {
174+
// n := len(*pq)
175+
// item := x.(*Item)
176+
// item.index = n
177+
// *pq = append(*pq, item)
178+
// }
179+
180+
// func (pq *PriorityQueue) Pop() interface{} {
181+
// old := *pq
182+
// n := len(old)
183+
// item := old[n-1]
184+
// old[n-1] = nil // avoid memory leak
185+
// item.index = -1 // for safety
186+
// *pq = old[0 : n-1]
187+
// return item
188+
// }
189+
190+
// // update modifies the priority and value of an Item in the queue.
191+
// func (pq *PriorityQueue) update(item *Item, value int, frequency int, count int) {
192+
// item.value = value
193+
// item.count = count
194+
// item.frequency = frequency
195+
// heap.Fix(pq, item.index)
196+
// }

‎template/LRUCache.go

Lines changed: 139 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,139 @@
1+
package template
2+
3+
// LRUCache define
4+
type LRUCache struct {
5+
head, tail *Node
6+
keys map[int]*Node
7+
capacity int
8+
}
9+
10+
// Node define
11+
type Node struct {
12+
key, val int
13+
prev, next *Node
14+
}
15+
16+
// ConstructorLRU define
17+
func ConstructorLRU(capacity int) LRUCache {
18+
return LRUCache{keys: make(map[int]*Node), capacity: capacity}
19+
}
20+
21+
// Get define
22+
func (lruCache *LRUCache) Get(key int) int {
23+
if node, ok := lruCache.keys[key]; ok {
24+
lruCache.Remove(node)
25+
lruCache.Add(node)
26+
return node.val
27+
}
28+
return -1
29+
}
30+
31+
// Put define
32+
func (lruCache *LRUCache) Put(key int, value int) {
33+
node, ok := lruCache.keys[key]
34+
if ok {
35+
node.val = value
36+
lruCache.Remove(node)
37+
lruCache.Add(node)
38+
return
39+
}
40+
node = &Node{key: key, val: value}
41+
lruCache.keys[key] = node
42+
lruCache.Add(node)
43+
if len(lruCache.keys) > lruCache.capacity {
44+
delete(lruCache.keys, lruCache.tail.key)
45+
lruCache.Remove(lruCache.tail)
46+
}
47+
}
48+
49+
// Add define
50+
func (lruCache *LRUCache) Add(node *Node) {
51+
node.prev = nil
52+
node.next = lruCache.head
53+
if lruCache.head != nil {
54+
lruCache.head.prev = node
55+
}
56+
lruCache.head = node
57+
if lruCache.tail == nil {
58+
lruCache.tail = node
59+
lruCache.tail.next = nil
60+
}
61+
}
62+
63+
// Remove define
64+
func (lruCache *LRUCache) Remove(node *Node) {
65+
if node == lruCache.head {
66+
lruCache.head = node.next
67+
if node.next != nil {
68+
node.next.prev = nil
69+
}
70+
node.next = nil
71+
return
72+
}
73+
if node == lruCache.tail {
74+
lruCache.tail = node.prev
75+
node.prev.next = nil
76+
node.prev = nil
77+
return
78+
}
79+
node.prev.next = node.next
80+
node.next.prev = node.prev
81+
}
82+
83+
/**
84+
* Your LRUCache object will be instantiated and called as such:
85+
* obj := Constructor(capacity);
86+
* param_1 := obj.Get(key);
87+
* obj.Put(key,value);
88+
*/
89+
90+
// 22%
91+
// import "container/list"
92+
93+
// type LRUCache struct {
94+
// Cap int
95+
// Keys map[int]*list.Element
96+
// List *list.List
97+
// }
98+
99+
// type pair struct {
100+
// K, V int
101+
// }
102+
103+
// func Constructor(capacity int) LRUCache {
104+
// return LRUCache{
105+
// Cap: capacity,
106+
// Keys: make(map[int]*list.Element),
107+
// List: list.New(),
108+
// }
109+
// }
110+
111+
// func (c *LRUCache) Get(key int) int {
112+
// if el, ok := c.Keys[key]; ok {
113+
// c.List.MoveToFront(el)
114+
// return el.Value.(pair).V
115+
// }
116+
// return -1
117+
// }
118+
119+
// func (c *LRUCache) Put(key int, value int) {
120+
// if el, ok := c.Keys[key]; ok {
121+
// el.Value = pair{K: key, V: value}
122+
// c.List.MoveToFront(el)
123+
// } else {
124+
// el := c.List.PushFront(pair{K: key, V: value})
125+
// c.Keys[key] = el
126+
// }
127+
// if c.List.Len() > c.Cap {
128+
// el := c.List.Back()
129+
// c.List.Remove(el)
130+
// delete(c.Keys, el.Value.(pair).K)
131+
// }
132+
// }
133+
134+
/**
135+
* Your LRUCache object will be instantiated and called as such:
136+
* obj := Constructor(capacity);
137+
* param_1 := obj.Get(key);
138+
* obj.Put(key,value);
139+
*/

0 commit comments

Comments
 (0)