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
85
86
87
88
89
90
91
92
93
94
95
96

type Key interface{}
type Cache struct {
    MaxEntries int           //缓存容量
    OnEvicted  func(key Key, value interface{}) 
                             //缓存被淘汰时的回调函数
    ll         *list.List    // 双链表
    cache      map[interface{}]*list.Element
}

type entry struct {
    key    Key
    value  interface{}
}

func New(maxEntries int) *Cache {
    return &Cache{
        MaxEntries: maxEntries,
        ll:         list.New(),
        cache:      make(map[interface{}]*list.ELement),
    }
}

func (c *Cache) Add(key Key, value interface{}) {
    if c.cache == nil {
        c.cache = make(map[interface{}]*list.Element)
        c.ll = list.new()
    }
    if ee, ok := c.cache[key]; ok {
        c.ll.MoveToFront(ee)
        ee.Value.(*entry).value = value
        return
    }
    ele := c.ll.PushFront(&entry{key, value})
    c.cache[key] = ele
    if c.MaxEntries != 0 && c.ll.Len() > MaxEntries {
        c.RemoveOldest()
    }
}

func (c *Cache) Get(key Key) (value interface{}, ok bool) {
    if c.cache == nil {
        return
    }
    if ele, hit := c.cache[key]; hit {
        c.ll.NoveToFront(ele)
        return ele.Value.(*entry).value, true
    }
}
func (c *Cache) Remove(key Key) {
	if c.cache == nil {
		return
	}
	if ele, hit := c.cache[key]; hit {
		c.removeElement(ele)
	}
}

// RemoveOldest removes the oldest item from the cache.
func (c *Cache) RemoveOldest() {
	if c.cache == nil {
		return
	}
	ele := c.ll.Back()
	if ele != nil {
		c.removeElement(ele)
	}
}

func (c *Cache) removeElement(e *list.Element) {
	c.ll.Remove(e)
	kv := e.Value.(*entry)
	delete(c.cache, kv.key)
	if c.OnEvicted != nil {
		c.OnEvicted(kv.key, kv.value)
	}
}

// Len returns the number of items in the cache.
func (c *Cache) Len() int {
	if c.cache == nil {
		return 0
	}
	return c.ll.Len()
}

// Clear purges all stored items from the cache.
func (c *Cache) Clear() {
	if c.OnEvicted != nil {
		for _, e := range c.cache {
			kv := e.Value.(*entry)
			c.OnEvicted(kv.key, kv.value)
		}
	}
	c.ll = nil
	c.cache = nil
}

  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
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139

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

func Constructor(capacity int) LFUCache {
  return LFUCache {
    cache: make(map[int]*Node),
    freq: make(map[int]*DoubleList),
    ncap: capacity,
  }
}

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

func (this *LFUCache) Put(key, value int) {
  if this.ncap == 0 {
    return
  }
  if node, ok := this.cache[key]; ok {
    node.val = value
    this.IncFreq(node)
  } else {
    if this.size >= this.ncap {
      node := this.freq[this.minFreq].RemoveLast()
      delete(this.cache, node.key)
      this.size--
    }
    x := &Node{key: key, val: value, freq: 1}
    this.cache[key] = x
    if this.freq[1] == nil {
      this.freq[1] = CreateDL()
    }
    this.freq[1].AddFirst(x)
    this.minFreq = 1
    this.size++
  }
}

func (this *LFUCache) IncFreq(node *Node) {
  _freq := node.freq
  this.freq[_freq].Remove(node)
  if this.minFreq == _freq && this.freq[_freq].IsEmpty() {
    this.minFreq++
    delete(this.freq, _freq)
  }

  node.freq++
  if this.freq[node.freq] == nil {
    this.freq[node.freq] = CreateDL()
  }
  this.freq[node.freq].AddFirst(node)
}

type DoubleList struct {
  head, tail *Node
}

type Node struct {
  prev, next *Node
  key, val, freq int
}

func CreateDL() *DoubleList {
  head, tail := &Node{}, &Node{}
  head.next, tail.prev = tail, head
  return &DoubleList {
    head: head,
    tail: tail,
  }
}

func (this *DoubleList) AddFirst(node *Node) {
  node.next = this.head.next
  node.prev = this.head

  this.head.next.prev = node
  this.head.next = node
}

func (this *DoubleList) Remove(node *Node) {
  node.prev.next = node.next
  node.next.prev = node.prev

  node.next = nil
  node.prev = nil
}

func (this *DoubleList) RemoveLast() *Node {
  if this.IsEmpty() {
    return nil
  }

  last := this.tail.prev
  this.Remove(last)

  return last
}

func (this *DoubleList) IsEmpty() bool {
  return this.head.next == this.tail
}

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


type LRUCache struct {

}


func Constructor(capacity int) LRUCache {

}


func (this *LRUCache) Get(key int) int {

}


func (this *LRUCache) Put(key int, value int)  {

}