LRU cache

[Weatherby,Gerard]

I think this does the trick:

https://gist.github.com/Gerardwx/c60d200b4db8e7864cb3342dd19d41c9


#!/usr/bin/env python3
import collections
import random
from typing import Hashable, Any, Optional, Dict, Tuple


class LruCache:
    """Dictionary like storage of most recently inserted values"""

    def __init__(self, size: int = 1000):
        """:param size number of cached entries"""
        assert isinstance(size, int)
        self.size = size
        self.insert_counter = 0
       self.oldest = 0
        self._data : Dict[Hashable,Tuple[Any,int]]= {} # store values and age index
        self._lru: Dict[int, Hashable] = {} # age counter dictionary

    def insert(self, key: Hashable, value: Any) -> None:
        """Insert into dictionary"""
        existing = self._data.get(key, None)
        self._data[key] = (value, self.insert_counter)
        self._lru[self.insert_counter] = key
        if existing is not None:
            self._lru.pop(existing[1], None)  # remove old counter value, if it exists
        self.insert_counter += 1
        if (sz := len(self._data)) > self.size:  # is cache full?
            assert sz == self.size + 1
            while (
            key := self._lru.get(self.oldest, None)) is None:  # index may not be present, if value was reinserted
                self.oldest += 1
            del self._data[key]  # remove oldest key / value from dictionary
            del self._lru[self.oldest]
            self.oldest += 1  # next oldest index
        assert len(self._lru) == len(self._data)

    def get(self, key: Hashable) -> Optional[Any]:
        """Get value or return None if not in cache"""
        if (tpl := self._data.get(key, None)) is not None:
            return tpl[0]
        return None


if __name__ == "__main__":
    CACHE_SIZE = 1000
    TEST_SIZE = 1_000_000
    cache = LruCache(size=CACHE_SIZE)

    all = []
    for i in range(TEST_SIZE):
        all.append(random.randint(-5000, 5000))

    summary = collections.defaultdict(int)
    for value in all:
        cache.insert(value, value * value)
        summary[value] += 1
    smallest = TEST_SIZE
    largest = -TEST_SIZE
    total = 0
    for value, count in summary.items():
        smallest = min(smallest, count)
        largest = max(largest, count)
        total += count
    avg = total / len(summary)
    print(f"{len(summary)} values occurrences range from {smallest} to {largest}, average {avg:.1f}")

    recent = set()  # recent most recent entries
    for i in range(len(all) - 1, -1, -1):  # loop backwards to get the most recent entries
        value = all[i]
        if len(recent) < CACHE_SIZE:
            recent.add(value)
        if value in recent:
            if (r := cache.get(value)) != value * value:
                raise ValueError(f"Cache missing recent {value} {r}")
        else:
            if cache.get(value) != None:
                raise ValueError(f"Cache includes old {value}")

From: Python-list <python-list-bounces+gweatherby=uchc.edu at python.org> on behalf of Dino <dino at no.spam.ar>
Date: Wednesday, February 15, 2023 at 3:07 PM
To: python-list at python.org <python-list at python.org>
Subject: Re: LRU cache
*** Attention: This is an external email. Use caution responding, opening attachments or clicking on links. ***

Thank you Mats, Avi and Chris

btw, functools.lru_cache seems rather different from what I need, but
maybe I am missing something. I'll look closer.

On 2/14/2023 7:36 PM, Mats Wichmann wrote:
> On 2/14/23 15:07, Dino wrote:
>>

--
https://urldefense.com/v3/__https://mail.python.org/mailman/listinfo/python-list__;!!Cn_UX_p3!jb3Gr2BFAPLJ2YuI5rFdJUtalqWcijhxHAfdmCI3afnLFDdcekALxDYAQwpE1L_JlJBBJ-BB3BuLdoSE$<https://urldefense.com/v3/__https:/mail.python.org/mailman/listinfo/python-list__;!!Cn_UX_p3!jb3Gr2BFAPLJ2YuI5rFdJUtalqWcijhxHAfdmCI3afnLFDdcekALxDYAQwpE1L_JlJBBJ-BB3BuLdoSE$>