other.lfu_cache

Attributes

T
U

Classes

DoubleLinkedList	Double Linked List built specifically for LFU Cache
DoubleLinkedListNode	Double Linked List Node built specifically for LFU Cache
LFUCache	LFU Cache to store a given capacity of data. Can be used as a stand-alone object

Module Contents

class other.lfu_cache.DoubleLinkedList

Bases: Generic[T, U]

Double Linked List built specifically for LFU Cache

>>> dll: DoubleLinkedList = DoubleLinkedList()
>>> dll
DoubleLinkedList,
    Node: key: None, val: None, freq: 0, has next: True, has prev: False,
    Node: key: None, val: None, freq: 0, has next: False, has prev: True

>>> first_node = DoubleLinkedListNode(1,10)
>>> first_node
Node: key: 1, val: 10, freq: 0, has next: False, has prev: False

>>> dll.add(first_node)
>>> dll
DoubleLinkedList,
    Node: key: None, val: None, freq: 0, has next: True, has prev: False,
    Node: key: 1, val: 10, freq: 1, has next: True, has prev: True,
    Node: key: None, val: None, freq: 0, has next: False, has prev: True

>>> # node is mutated
>>> first_node
Node: key: 1, val: 10, freq: 1, has next: True, has prev: True

>>> second_node = DoubleLinkedListNode(2,20)
>>> second_node
Node: key: 2, val: 20, freq: 0, has next: False, has prev: False

>>> dll.add(second_node)
>>> dll
DoubleLinkedList,
    Node: key: None, val: None, freq: 0, has next: True, has prev: False,
    Node: key: 1, val: 10, freq: 1, has next: True, has prev: True,
    Node: key: 2, val: 20, freq: 1, has next: True, has prev: True,
    Node: key: None, val: None, freq: 0, has next: False, has prev: True

>>> removed_node = dll.remove(first_node)
>>> assert removed_node == first_node
>>> dll
DoubleLinkedList,
    Node: key: None, val: None, freq: 0, has next: True, has prev: False,
    Node: key: 2, val: 20, freq: 1, has next: True, has prev: True,
    Node: key: None, val: None, freq: 0, has next: False, has prev: True

>>> # Attempt to remove node not on list
>>> removed_node = dll.remove(first_node)
>>> removed_node is None
True

>>> # Attempt to remove head or rear
>>> dll.head
Node: key: None, val: None, freq: 0, has next: True, has prev: False
>>> dll.remove(dll.head) is None
True

>>> # Attempt to remove head or rear
>>> dll.rear
Node: key: None, val: None, freq: 0, has next: False, has prev: True
>>> dll.remove(dll.rear) is None
True

__repr__() → str

_position_node(node: DoubleLinkedListNode[T, U]) → None

Moves node forward to maintain invariant of sort by freq value

add(node: DoubleLinkedListNode[T, U]) → None

Adds the given node at the tail of the list and shifting it to proper position

remove(node: DoubleLinkedListNode[T, U]) → DoubleLinkedListNode[T, U] | None

Removes and returns the given node from the list

Returns None if node.prev or node.next is None

head: DoubleLinkedListNode[T, U]

rear: DoubleLinkedListNode[T, U]

class other.lfu_cache.DoubleLinkedListNode(key: T | None, val: U | None)

Bases: Generic[T, U]

Double Linked List Node built specifically for LFU Cache

>>> node = DoubleLinkedListNode(1,1)
>>> node
Node: key: 1, val: 1, freq: 0, has next: False, has prev: False

__repr__() → str

freq: int = 0

key

next: DoubleLinkedListNode[T, U] | None = None

prev: DoubleLinkedListNode[T, U] | None = None

val

class other.lfu_cache.LFUCache(capacity: int)

Bases: Generic[T, U]

LFU Cache to store a given capacity of data. Can be used as a stand-alone object or as a function decorator.

>>> cache = LFUCache(2)
>>> cache.put(1, 1)
>>> cache.put(2, 2)
>>> cache.get(1)
1
>>> cache.put(3, 3)
>>> cache.get(2) is None
True
>>> cache.put(4, 4)
>>> cache.get(1) is None
True
>>> cache.get(3)
3
>>> cache.get(4)
4
>>> cache
CacheInfo(hits=3, misses=2, capacity=2, current_size=2)
>>> @LFUCache.decorator(100)
... def fib(num):
...     if num in (1, 2):
...         return 1
...     return fib(num - 1) + fib(num - 2)

>>> for i in range(1, 101):
...     res = fib(i)

>>> fib.cache_info()
CacheInfo(hits=196, misses=100, capacity=100, current_size=100)

__contains__(key: T) → bool

>>> cache = LFUCache(1)

>>> 1 in cache
False

>>> cache.put(1, 1)
>>> 1 in cache
True

__repr__() → str

Return the details for the cache instance [hits, misses, capacity, current_size]

classmethod decorator(size: int = 128) → collections.abc.Callable[[collections.abc.Callable[[T], U]], collections.abc.Callable[Ellipsis, U]]

Decorator version of LFU Cache

Decorated function must be function of T -> U

get(key: T) → U | None

Returns the value for the input key and updates the Double Linked List. Returns Returns None if key is not present in cache

put(key: T, value: U) → None

Sets the value for the input key and updates the Double Linked List

cache: dict[T, DoubleLinkedListNode[T, U]]

capacity

decorator_function_to_instance_map: dict[collections.abc.Callable[[T], U], LFUCache[T, U]]

hits = 0

list: DoubleLinkedList[T, U]

miss = 0

num_keys = 0

other.lfu_cache.T

other.lfu_cache.U