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
 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
108
109
110
111
112
113
114
115
116

type DLinkedList struct {
    key, value, frequency int
    pre, next *DLinkedList
}
type LFUCache struct {
    recent map[int]*DLinkedList
    count map[int]int
    cache map[int]*DLinkedList
    // dlist *DLinkedList
    head, tail *DLinkedList
    capacity int
}
func Constructor(capacity int) LFUCache {
    head, tail := &DLinkedList{}, &DLinkedList{}
    head.next = tail
    tail.pre = head
    return LFUCache{
        recent: map[int]*DLinkedList{},
        count: map[int]int{},
        cache: map[int]*DLinkedList{},
        head: head,
        tail: tail,
        capacity: capacity,
    }
}


func (lfu *LFUCache) Get(key int) int {
    if node, ok := lfu.cache[key]; ok {
        freNum := node.frequency
        if lfu.count[freNum+1] > 0 {
            if lfu.recent[freNum] == node {
                if node.next != lfu.tail {
                    lfu.recent[freNum] = node.next
                } else {
                    lfu.recent[freNum] = nil
                }
                lfu.removeNode(node)
                lfu.addNodeBefore(lfu.recent[freNum+1], node) 
            } else if lfu.recent[freNum] != node && lfu.recent[freNum] != nil {
                lfu.removeNode(node)
                lfu.addNodeBefore(lfu.recent[freNum+1], node)
            } 
        } else { 
            if lfu.recent[freNum] != node {
                lfu.removeNode(node)
                lfu.addNodeBefore(lfu.recent[freNum], node)
            } else {
                if node.next != lfu.tail {
                    lfu.recent[freNum] = node.next
                } else {
                    lfu.recent[freNum] = nil
                }
            }
        }
        lfu.recent[freNum+1] = node
        node.frequency++
        lfu.count[freNum]--
        lfu.count[freNum+1]++
        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 {
        lfu.Get(key)
        node.value = value
        return
    }
    if len(lfu.cache) == lfu.capacity {
        tailNode := lfu.tail.pre
        lfu.removeNode(tailNode)
        if lfu.count[tailNode.frequency] <= 1 { 
            lfu.recent[tailNode.frequency] = nil 
        } 
        lfu.count[tailNode.frequency]-- 
        delete(lfu.cache, tailNode.key)
    }
    newNode := &DLinkedList{
        key: key,
        value: value,
        frequency: 1,
    }
    if len(lfu.cache) == 0 || lfu.recent[1] == nil { 
        lfu.addNodeBefore(lfu.tail, newNode)
    } else {
        lfu.addNodeBefore(lfu.recent[1], newNode) 
    }
    lfu.cache[key] = newNode
    lfu.recent[1] = newNode
    lfu.count[1]++
}

func (lfu *LFUCache) addNodeBefore(curNode *DLinkedList, newNode *DLinkedList) {
    preNode := curNode.pre
    curNode.pre = newNode
    newNode.next = curNode
    preNode.next = newNode
    newNode.pre = preNode
}

func (lfu *LFUCache) removeNode(node *DLinkedList) {
    preNode, nextNode := node.pre, node.next
    preNode.next = nextNode
    nextNode.pre = preNode
}
/**
 * Your LFUCache object will be instantiated and called as such:
 * obj := Constructor(capacity);
 * param_1 := obj.Get(key);
 * obj.Put(key,value);
 */

 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

func TestLFU(t *testing.T) {
	assert := assert.New(t)
	input1 := []string{"LFUCache", "put", "put", "put", "put", "get", "get"}
	input2 := [][]int{{2}, {2, 1}, {1, 1}, {2, 3}, {4, 1}, {1}, {2}}

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

	expected_res := []interface{}{nil, nil, nil, 1, nil, -1, 3, nil, -1, 3, 4}
	real_res := ExecLFU(input1, input2)
	assert.Equal(expected_res, real_res)
}

func TestLFU2(t *testing.T) {
	assert := assert.New(t)
	input1 := []string{"LFUCache", "put", "put", "get", "get", "get", "put", "put", "get", "get", "get", "get"}
	input2 := [][]int{{3}, {2, 2}, {1, 1}, {2}, {1}, {2}, {3, 3}, {4, 4}, {3}, {2}, {1}, {4}}

	expected_res := []interface{}{nil, nil, nil, 2, 1, 2, nil, nil, -1, 2, 1, 4}
	real_res := ExecLFU(input1, input2)
	assert.Equal(expected_res, real_res)
}


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