LRU cache

[avi.e.gross at gmail.com]

Dino,

If your question is understood, you want to treat a dictionary as a sort of
queue with a maximum number of entries. And, you want to remove some kind of
least useful item to make room for any new one.

Most dictionaries now have entries in the order they were entered. There may
already be some variant out there that implements this but it should not be
hard to create.

So you could simply change the method that adds an item to the dictionary.
If the new next  item is not already in the dictionary, simply remove the
first item using whatever method you wish. 

Getting all the keys may be avoided by using an iterator once as in:
next(iter( my_dict.keys() )) or something like that. 

You can then remove that item using the key and insert your new item at the
end.

Of course,  that is not least recently used but least recently entered. 

To deal with keeping track of what was accessed last or never, is a problem
not trivially solved with just a dictionary. I mean you could store a tuple
for each item that included a date and a payload as the value, and you could
then search all the values and find the one with the oldest date. That seems
a bit much so another architecture could be to maintain another data
structure holding keys and dates that perhaps you keep sorted by date and
every time the cache accesses a value, it finds the item in the second
storage and updates the date and  moves the item to the end of the
structure. 

But note that some may want to keep an access count so you always know how
many times an item has been re-used and thus not remove them as easily.

The main goal of a dictionary is to speed up access and make it almost
linear. Your algorithm can add so much overhead, depending on how it is
done, that it can defeat the purpose. 

What some might do is skip the dictionary and use some kind of queue like a
dequeue that handles your thousand entries and new items are added at the
end, items accessed moved to the front, and a brute force search is used to
find an entry. But note some algorithms like that may end up removing the
newest item immediately as it is least recently used if placed at the end. 

It may be an Ordered Dict is one solution as shown here:

https://www.geeksforgeeks.org/lru-cache-in-python-using-ordereddict/



-----Original Message-----
From: Python-list <python-list-bounces+avi.e.gross=gmail.com at python.org> On
Behalf Of Dino
Sent: Tuesday, February 14, 2023 5:07 PM
To: python-list at python.org
Subject: LRU cache


Here's my problem today. I am using a dict() to implement a quick and dirty
in-memory cache.

I am stopping adding elements when I am reaching 1000 elements (totally
arbitrary number), but I would like to have something slightly more
sophisticated to free up space for newer and potentially more relevant
entries.

I am thinking of the Least Recently Used principle, but how to implement
that is not immediate. Before I embark on reinventing the wheel, is there a
tool, library or smart trick that will allow me to remove elements with LRU
logic?

thanks

Dino
--
https://mail.python.org/mailman/listinfo/python-list