lfucache

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/v2

Usage

• To get started, import the lfu-cache package and create a cache instance. New() returns an ErrInvalidCap error if you input a capacity which is less than or equal to 0.

  import "https://github.com/NdoleStudio/lfu-cache/v2"
  
  // creating the cache with capacity 3
  cache, err := lfucache.New[string, int](3)
  if err != nil {
      // the cap is invalid
  }
  
  // DO NOT DO THIS
  cache := lfucache.Cache{}
  

• Inserting a value in the cache. Set() returns ErrInvalidCap if the cache capacity is less than or equal to zero. Ideally you should NEVER get this error

  err := cache.Set("key", "value")
  if err != nil {
      // the cap is invalid
  }
  

• Getting a value in from the cache. Get() returns ErrCacheMiss if there is a cache miss

  val, err := cache.Get("key")
  if err != nil {
      // cache miss
  }
  
  or 
  
  if err == lfucache.ErrCacheMiss { 
      // cache miss
  }
  
  println(val) // val is of type `int`
  

• There are some helper methods like IsEmpty(), Len(), IsFull Cap()

  // creating the cache with capacity 3
  cache, _ := lfucache.New[string, string](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

• AchoArnold

See also the list of contributors who participated in this project.

License

This project is licensed under the MIT License - see the LICENSE 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

• Variables
• type Cache
  • func New[K comparable, V any](cap int) (cache *Cache[K, V], err error)
  • func (cache *Cache[K, V]) Cap() int
  • func (cache *Cache[K, V]) Get(key K) (value V, err error)
  • func (cache *Cache[K, V]) IsEmpty() bool
  • func (cache *Cache[K, V]) IsFull() bool
  • func (cache *Cache[K, V]) Len() int
  • func (cache *Cache[K, V]) Set(key K, value V) (err error)

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")
)

Types

type Cache

type Cache[K comparable, V any] 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

func New[K comparable, V any](cap int) (cache *Cache[K, V], err error)

New creates a new instance of the LFU Cache. It returns and ErrInvalidCap error if the cap <= 0.

func (*Cache[K, V]) Cap

func (cache *Cache[K, V]) Cap() int

Cap returns the cap fo the Cache.

func (*Cache[K, V]) Get

func (cache *Cache[K, V]) Get(key K) (value V, err error)

Get returns an item for the Cache having a key. It returns ErrCacheMiss if there's a Cache miss.

func (*Cache[K, V]) IsEmpty

func (cache *Cache[K, V]) IsEmpty() bool

IsEmpty determines if there are no items in the Cache.

func (*Cache[K, V]) IsFull

func (cache *Cache[K, V]) IsFull() bool

IsFull determines if the Cache is full.

func (*Cache[K, V]) Len

func (cache *Cache[K, V]) Len() int

Len returns the number of items in the Cache.

func (*Cache[K, V]) Set

func (cache *Cache[K, V]) Set(key K, value V) (err error)

Set is used to an item in the Cache with key and value. It returns ErrInvalidCap if the cache is not initialized.