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

// @Title: LFU 缓存 (LFU Cache)
// @Author: 15816537946@163.com
// @Date: 2019-11-03 20:51:52
// @Runtime: 168 ms
// @Memory: 16 MB
type LFUCache struct {
	// 用于检查key的存在性
	m   map[int]*entry
	pq  PQ
	cap int
}

func Constructor(capacity int) LFUCache {
	return LFUCache{
		m:   make(map[int]*entry, capacity),
		pq:  make(PQ, 0, capacity),
		cap: capacity,
	}
}

// Get获取key的值
func (this *LFUCache) Get(key int) int {
	ep, ok := this.m[key]
	if ok {
		this.pq.update(ep)
		return ep.value
	}
	return -1

}

func (this *LFUCache) Put(key int, value int) {
	if this.cap <= 0 {
		return
	}
	ep, ok := this.m[key]
	// update
	if ok {
		this.m[key].value = value
		this.pq.update(ep)
		return
	}

	ep = &entry{key: key, value: value}
	// pq已满的话， 先删除再插入
	if len(this.pq) == this.cap {
		tmp := heap.Pop(&this.pq).(*entry)
		delete(this.m, tmp.key)
	}
	this.m[key] = ep
	heap.Push(&this.pq, ep)

}

type entry struct {
	key, value int
	// 辅助参数
	frequency, index int
	date             time.Time
}

type PQ []*entry

func (pq PQ) Len() int { return len(pq) }

func (pq PQ) Less(i, j int) bool {
	if pq[i].frequency == pq[j].frequency {
		return pq[i].date.Before(pq[j].date)
	}
	return pq[i].frequency < pq[j].frequency
}

func (pq PQ) Swap(i, j int) {
	pq[i], pq[j] = pq[j], pq[i]
	pq[i].index = i
	pq[j].index = j
}

func (pq *PQ) Push(x interface{}) {
	n := len(*pq)
	entry := x.(*entry)
	entry.index = n
	entry.date = time.Now()
	*pq = append(*pq, entry)
}

func (pq *PQ) Pop() interface{} {
	old := *pq
	n := len(old)
	entry := old[n-1]
	entry.index = -1 // for safety
	*pq = old[0 : n-1]
	return entry
}

func (pq *PQ) update(entry *entry) {
	entry.frequency++
	entry.date = time.Now()
	heap.Fix(pq, entry.index)
}

/**
 * Your LFUCache object will be instantiated and called as such:
 * obj := Constructor(capacity);
 * param_1 := obj.Get(key);
 * obj.Put(key,value);
 */