fastlfu is still under developement, the API might not be stable yet, you should not use in production ❗
This is a Go 1.18 implementation of the fastLFU (Least Frequently Used) cache eviction scheme, described in a 2021 paper by Dhruv Matani, Ketan Shah and Anirban Mitra called An O(1) algorithm for implementing the LFU cache eviction scheme.
Here's an extract from the paper introduction:
The LFU algorithm has behaviour desirable by many real world workloads. However, in many places, the LRU algorithm is is preferred over the LFU algorithm because of its lower run time complexity of O(1) versus O(logn). We present here an LFU cache eviction algorithm that has a runtime complexity of O(1) for all of its operations, which include insertion, access and deletion(eviction).
Install the fastlfu module:
go get github.com/arl/fastlfu@latest
Let's create a Cache object where keys are uint64 and values are strings:
c := fastlfu.New[uint64, string]()Add a bunch of key-value pairs:
c.Insert(0, "foo")
c.Insert(1, "bar")
c.Insert(2, "baz")Each time we fetch a value associated from a key, we increment the key frequency:
v1, ok1 := c.Fetch(0)
// returns "foo", true
v2, ok1 := c.Fetch(1)
// returns "bar", trueIf we call Fetch with a key that is not present, we get the zero-value of the
value type, and false:
v, ok := c.Fetch(12345678)
// returns "", falseAfter these calls, the (0, "foo") and (1, "bar") key-value pairs have been
more frequently used than (2, "baz").
So if we require the cache to evict the least frequently used value, it's going
to be "baz". Evict also returns a boolean indicating if any eviction has
been performed.
v, ok := c.Evict(0)
// returns "baz", trueNOTE: Evict is guaranteed to succeed unless the Cache is empty.
If we call Evict again, we can't predict they key-value pair that is going to
be evicted because the remaining pairs have the same frequency.
v, ok := c.Evict(0)
// returns either ("foo", true) or ("bar", true)TODO