README

Lest Frequently Used (LFU) Cache

Build Status codecov Go Report Card GitHub contributors GitHub license PkgGoDev

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 an ErrInvalidCap error if you input a capacity which is less than or equal to 0.

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

Expand ▾ Collapse ▴

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

    This section is empty.

    Variables

    View Source
    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

    This section is empty.

    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

      func New(cap int) (cache *Cache, err error)

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

        func (*Cache) Cap

        func (cache *Cache) Cap() int

          Cap returns the cap fo the Cache.

          func (*Cache) Get

          func (cache *Cache) Get(key interface{}) (value interface{}, err error)

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

            func (*Cache) IsEmpty

            func (cache *Cache) IsEmpty() bool

              IsEmpty determines if there are no items in the Cache.

              func (*Cache) IsFull

              func (cache *Cache) IsFull() bool

                IsFull determines if the Cache is full.

                func (*Cache) Len

                func (cache *Cache) Len() int

                  Len returns the number of items in the Cache.

                  func (*Cache) Set

                  func (cache *Cache) Set(key interface{}, value interface{}) (err error)

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

                    Source Files