Python-LFU

Simplest usage

from lfu_cache import LFUCache
cache = LFUCache(2)
cache.put(1, 1)
cache.put(2, 2)
cache.get(1)
cache.put(3, 3) # will evict 2
cache.get(2) # raise KeyError

Algorithm can be read at this research paper. The implementation is exactly same where the cache object wraps FrequencyList linked list whose elements are FrequencyItem. FrequencyItem has an attribute frequency. FrequencyItem then wraps a NodeList double linked list with NodeItem as elements of it. NodeItem wraps up the actual key/value provided by application.

API Documentation

This documentation is automatically generated from Python-LFU source code.

class lfu_cache.LFUCache(limit: int)

Object implents an O(1) algorithm for implementing the LFU cache eviction scheme. This is based on paper at: http://dhruvbird.com/lfu.pdf

See: https://en.wikipedia.org/wiki/Least_frequently_used

get(key) → Union[KeyError, Any]

Gets value by key. Raises KeyError, if not found

put(key: Any, value: Any)

Puts an object to the cache

class lfu_cache.Element(value: Any, dllist: lfu_cache.dllist.DLList)

nextelement() → Optional[lfu_cache.dllist.Element]

Return the next list element or None

prevelement() → Optional[lfu_cache.dllist.Element]

Return the next list element or None

class lfu_cache.DLList

Object implementing a double linked list. Python verison of Golang list container. To simplify implementation, internally the list is implemented as a ring such that DLLlist.root is both next element of last and previous element of first

append(value: Any) → lfu_cache.dllist.Element

Inserts a new element with value v at tail of list. return Element

Parameters:value – Value to be saved Returns:New element with value value

appendleft(value: Any) → lfu_cache.dllist.Element

Inserts a new element with value v at front of list. return Element

Parameters:value – Value to be saved Returns:New element with value value

back() → Optional[lfu_cache.dllist.Element]

return last element of list or None

front() → Optional[lfu_cache.dllist.Element]

return first element of list or None

insertafter(value: Any, mark: lfu_cache.dllist.Element) → lfu_cache.dllist.Element

Inserts a new element e after mark and return e

Parameters:

• value – value to be saved
• mark – new element is added after mark

insertbefore(value: Any, mark: lfu_cache.dllist.Element) → lfu_cache.dllist.Element

Inserts a new element e before mark and return e

Parameters:

• value – value to be saved
• mark – new element is added before mark

moveafter(e: lfu_cache.dllist.Element, mark: lfu_cache.dllist.Element) → None

Move element e after mark

Parameters:

• e – Element to move
• mark – Element after which e will be moved

movebefore(e: lfu_cache.dllist.Element, mark: lfu_cache.dllist.Element) → None

Moves element e before mark

Parameters:

• e – Element to move
• mark – Element before which e will be moved

movetoback(e: lfu_cache.dllist.Element) → None

Moves element e to tail of list

Parameters:e – Element to move

movetofront(e: lfu_cache.dllist.Element) → None

Moves element e to front of list

Parameters:e – Element to move

reinit() → None

Reinits list

remove(e: lfu_cache.dllist.Element) → Any

Remove element e and return value associated with it

root = None

Sentinel node of the list.

exception lfu_cache.OtherListElement(ll, element)

Exception raised when you try to work with element of another list