README
Lest Frequently Used (LFU) Cache
This is an in memory implementation of a least frequently used (LFU) cache in Go with constant time complexity O(1) for Set
, Set
, and Cache Eviction
operations. The least recently used item is evicted in the case where 2 items thems have the same least frequency.
It's based on this paper http://dhruvbird.com/lfu.pdf by some very smart people
Documentation
You can use view the standard documentation on https://pkg.go.dev/github.com/NdoleStudio/lfu-cache. I wrote a beginner friendly blog post here
Install
go get https://github.com/NdoleStudio/lfu-cache
Usage
-
To get started, import the
lfu-cache
package and create a cache instance.New()
returns anErrInvalidCap
error if you input a capacity which is less than or equal to0
.import "github.com/NdoleStudio/lfu-cache" // creating the cache with capacity 3 cache, err := lfucache.New(3) if err != nil { // the cap is invalid } // DO NOT DO THIS cache := lfucache.Cache{}
-
Inserting a value in the cache.
Set()
returnsErrInvalidCap
if the cache capacity is less than or equal to zero. Ideally you should NEVER get this errorerr := cache.Set("key", "value") if err != nil { // the cap is invalid }
-
Getting a value in from the cache.
Get()
returnsErrCacheMiss
if there is a cache missval, err := cache.Get("key") if err != nil { // cache miss } or if err == lfucache.ErrCacheMiss { // cache miss } println(val) // val is of type interface{} println(val.(string)) // print val as string
-
There are some helper methods like
IsEmpty()
,Len()
,IsFull
Cap()
// creating the cache with capacity 3 cache, _ := lfucache.New(3) // setting a value _ = cache.Set("key", "value") cache.IsEmpty() // returns false cache.Len() // returns 1 because there is 1 item in the cache cache.IsFull() // returns false because the cache is not full cache.Cap() // returns 3 which is the capacity of the cache
Running Tests
To run tests, cd to the project directory and run
go test -v
Versioning
We use SemVer for versioning. For the versions available, see the tags on this repository.
Authors
See also the list of contributors who participated in this project.
License
This project is licensed under the MIT License - see the LICENSE.md file for details
Documentation
Overview ¶
Package lfucache an in memory least frequently used (LFU) cache. All operations have with O(1) complexity. When evicting an item from the cache, if 2 items have the same frequency the (least recently used) LRU item is evicted.
Ideally, you should provide a wrapper around this class to ensure strict type checks for keys and values that can be put into the cache.
Index ¶
Constants ¶
Variables ¶
var ( // ErrCacheMiss is the error that is returned when there is a Cache during a Get operation ErrCacheMiss = errors.New("cache miss") // ErrInvalidCap is the error returned when the cache cap is invalid ErrInvalidCap = errors.New("cache cap <= 0") )
Functions ¶
Types ¶
type Cache ¶
type Cache struct {
// contains filtered or unexported fields
}
Cache is the data structure for the LFU Cache. The zero value of this cache is not ready to use because the cap is zero
func New ¶
New creates a new instance of the LFU Cache. It returns and ErrInvalidCap error if the cap <= 0.
func (*Cache) Get ¶
Get returns an item for the Cache having a key. It returns ErrCacheMiss if there's a Cache miss.