LFU

package main
import (
    "fmt"
    "math/rand"
    "time"
)
var LFUInitRefCount uint8 = 5
var LFUMaxRefCount uint8 = 255
var LFUMaxAccessTs uint16 = 65535
var LFUMaxRandNumber uint16 = 65535
type LFUValueInfo struct {
    refCount     uint8       // 引用计数
    lastAccessTs uint16      // 最近一次访问时间
    value        interface{} // 数据
}
type LFUInfo struct {
    samples   int // 抽样数量
    eleLimit  int // 容器元素数量限制
    incFactor int // 引用计数增长因子，概率性增长，引用计数、增长因子越大，引用计数增长越慢
    decFactor int // 引用计数缩减因子，以分钟为单位，引用计数多少分钟减1
    mp        map[interface{}]*LFUValueInfo
}
func (lfu *LFUInfo) Get(key interface{}) (value interface{}, ok bool) {
    data, ok := lfu.mp[key]
    if ok == false {
        return
    }
    lfu.updateValueInfo(data)
    return data.value, ok
}
func (lfu *LFUInfo) Set(key, value interface{}) {
    if _, ok := lfu.mp[key]; !ok {
        lfu.mp[key] = lfu.newLFUValueInfo()
    }
    data, _ := lfu.mp[key]
    data.value = value
    lfu.updateValueInfo(data)
    if len(lfu.mp) > lfu.eleLimit {
        lfu.adjustElements()
    }
}
func (lfu *LFUInfo) newLFUValueInfo() *LFUValueInfo {
    return &LFUValueInfo{refCount: LFUInitRefCount, lastAccessTs: lfu.getCurrentTsInMinutes()}
}
func (lfu *LFUInfo) updateValueInfo(data *LFUValueInfo) {
    if data == nil {
        return
    }
    // 根据增长因子计算引用计数
    lfu.incRefCount(data)
    // 根据衰减因子计算引用计数
    lfu.decRefCount(data)
    // 更新访问时间戳
    data.lastAccessTs = lfu.getCurrentTsInMinutes()
}
func (lfu *LFUInfo) incRefCount(data *LFUValueInfo) {
    if data.refCount == LFUMaxRefCount {
        return
    }
    baseCount := 0
    if data.refCount > LFUInitRefCount {
        baseCount = int(data.refCount - LFUInitRefCount)
    }
    p := float64(1.0) / float64(baseCount*lfu.incFactor+1)
    r := lfu.randIncRate()
    if r < p {
        data.refCount++
    }
}
func (lfu *LFUInfo) randIncRate() float64 {
    randValue := rand.Intn(int(LFUMaxRefCount))
    return float64(randValue) / float64(LFUMaxRefCount)
}
func (lfu *LFUInfo) decRefCount(data *LFUValueInfo) {
    if data.refCount == 0 {
        return
    }
    decValue := uint16(0)
    if lfu.decFactor > 0 {
        decValue = lfu.getRefCountDecValue(data.lastAccessTs) / uint16(lfu.decFactor)
    }
    if uint16(data.refCount) > decValue {
        data.refCount = data.refCount - uint8(decValue)
    } else {
        data.refCount = 0
    }
}
func (lfu *LFUInfo) getRefCountDecValue(lastMinutes uint16) uint16 {
    nowMinutes := lfu.getCurrentTsInMinutes()
    if nowMinutes > lastMinutes {
        return nowMinutes - lastMinutes
    } else {
        return LFUMaxAccessTs + nowMinutes - lastMinutes
    }
}
func (lfu *LFUInfo) getCurrentTsInMinutes() uint16 {
    return uint16(time.Now().Unix() / 60 % int64(LFUMaxAccessTs))
}
// 删除抽样数量中，引用次数最小的一个
func (lfu *LFUInfo) adjustElements() {
    count := 0
    var delKey interface{}
    minCount := uint8(LFUMaxRefCount)
    for key, value := range lfu.mp {
        if count >= lfu.samples {
            break
        }
        if value.refCount <= minCount {
            minCount = value.refCount
            delKey = key
        }
        count++
    }
    fmt.Println(delKey)
    delete(lfu.mp, delKey)
}
func NewLFUInfo(inc, dec, sample, limit int) *LFUInfo {
    return &LFUInfo{
        samples:   sample,
        eleLimit:  limit,
        incFactor: inc,
        decFactor: dec,
        mp:        make(map[interface{}]*LFUValueInfo),
    }
}
func main() {
    lfu := NewLFUInfo(10, 1, 10, 10000)
    for uli := 0; uli < 10001; uli++ {
        lfu.Set(uli, 10000+uli)
    }
}

代码来自 https://studygolang.com/topics/12462