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....@python.org> on behalf of Dino <d...@no.spam.ar> Date: Wednesday, February 15, 2023 at 3:07 PM To: python-list@python.org <python-list@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$> -- https://mail.python.org/mailman/listinfo/python-list