tsman
commented
2 months ago
const maxCacheSize = 3
type KCounter struct {
key string
value int
}
func (t *KCounter) Less(than btree.Item) bool {
// 1. change pointer
counter := than.(*KCounter)
if t.key < counter.key {
return true
}
return t.value < counter.value
}
func Test_B(t *testing.T) {
put := func(tree *btree.BTree, itemByKey map[string]KCounter, kc KCounter) bool {
_, ok := itemByKey[kc.key]
if ok {
//update the value by re-inserting it
// 2. no need delete
//tree.Delete(&item)
tree.ReplaceOrInsert(&kc)
itemByKey[kc.key] = kc
return true
}
if tree.Len() >= maxCacheSize {
smallestItem := tree.Min().(*KCounter)
if kc.value < smallestItem.value {
//dont add group that have values that are smaller than the smallest elem in tree
return false
}
tree.DeleteMin()
}
tree.ReplaceOrInsert(&kc)
itemByKey[kc.key] = kc
return true
}
itemByKey := make(map[string]KCounter)
tree := btree.New(15)
for i := 0; i < 100000; i++ {
put(tree, itemByKey, KCounter{strconv.Itoa(i % 20), i % 10})
}
// 3. use debug for result.
t.Log("debug: see debug info")
}
i'm writing a kind of MFU cache
i'm using the KCounter where the KCounter.value is the frequency of the KCounter.key
the tree holds only N keys with the highest frequency , when there is no more room left the key with the minimal frequency will be dropped
running this code will result in runtime error
the error