Caché LRU en Python usando OrderedDict

La memoria caché LRU (Usados ​​menos recientemente) descarta primero los elementos usados ​​menos recientemente. Este algoritmo requiere realizar un seguimiento de lo que se usó y cuándo, lo cual es costoso si uno quiere asegurarse de que el algoritmo siempre descarte el elemento que se usó menos recientemente. Las implementaciones generales de esta técnica requieren mantener «bits de edad» para las líneas de caché y rastrear la línea de caché «Usada menos recientemente» en función de los bits de edad.
Nuestro enunciado del problema es diseñar e implementar una estructura de datos para la memoria caché de uso menos reciente (LRU). 
Debe soportar las siguientes operaciones: get y put.
* get(clave) – Obtiene el valor (siempre será positivo) de la clave si la clave existe en el caché, de lo contrario devuelve -1. 
* poner (clave, valor)– Establezca o inserte el valor si la clave aún no está presente. Cuando la memoria caché alcanza su capacidad, debe invalidar el elemento utilizado menos recientemente antes de insertar uno nuevo.
La memoria caché siempre se inicializa con capacidad positiva.

Ejemplos: 
 

Input/Output : 
LRUCache cache = new LRUCache( 2 /* capacity */ );

cache.put(1, 1);                                    
cache.put(2, 2);
cache.get(1);       // returns 1
cache.put(3, 3);    // evicts key 2
cache.get(2);       // returns -1 (not found)
cache.put(4, 4);    // evicts key 1
cache.get(1);       // returns -1 (not found)
cache.get(3);       // returns 3
cache.get(4);       // returns 4

Nuestra solución es usar el poder de OrderedDict del módulo de colecciones que mantiene el orden de inserción de claves y podemos cambiar ese orden si es necesario. La mejor parte es que todas las operaciones tienen una complejidad de tiempo O(1).
Mantenemos nuestro OrderedDict de tal manera que el pedido muestra qué tan recientemente se usaron. Al principio, tendremos el uso menos reciente y, al final, el uso más reciente. 
Si se realiza alguna actualización O consulta a una clave, se mueve al final (utilizada más recientemente). Si se agrega algo, se agrega al final (usado/agregado más recientemente)
Para obtener (clave): devolvemos el valor de la clave que se consulta en O (1) y devolvemos -1 si no encontramos el teclee out dict/cache. Y también mueva la clave hasta el final para mostrar que se usó recientemente.
Para put(clave, valor): primero, agregamos/actualizamos la clave mediante métodos convencionales. Y también mueva la clave hasta el final para mostrar que se usó recientemente. Pero aquí también comprobaremos si la longitud de nuestro diccionario ordenado ha excedido nuestra capacidad, si es así eliminamos la primera clave (menos utilizada recientemente)
 

from collections import OrderedDict
 
class LRUCache:
 
    # initialising capacity
    def __init__(self, capacity: int):
        self.cache = OrderedDict()
        self.capacity = capacity
 
    # we return the value of the key
    # that is queried in O(1) and return -1 if we
    # don't find the key in out dict / cache.
    # And also move the key to the end
    # to show that it was recently used.
    def get(self, key: int) -> int:
        if key not in self.cache:
            return -1
        else:
            self.cache.move_to_end(key)
            return self.cache[key]
 
    # first, we add / update the key by conventional methods.
    # And also move the key to the end to show that it was recently used.
    # But here we will also check whether the length of our
    # ordered dictionary has exceeded our capacity,
    # If so we remove the first key (least recently used)
    def put(self, key: int, value: int) -> None:
        self.cache[key] = value
        self.cache.move_to_end(key)
        if len(self.cache) > self.capacity:
            self.cache.popitem(last = False)
 
 
# RUNNER
# initializing our cache with the capacity of 2
cache = LRUCache(2)
 
 
cache.put(1, 1)
print(cache.cache)
cache.put(2, 2)
print(cache.cache)
cache.get(1)
print(cache.cache)
cache.put(3, 3)
print(cache.cache)
cache.get(2)
print(cache.cache)
cache.put(4, 4)
print(cache.cache)
cache.get(1)
print(cache.cache)
cache.get(3)
print(cache.cache)
cache.get(4)
print(cache.cache)
 
#This code was contributed by Sachin Negi

OrderedDict([(1, 1)])
OrderedDict([(1, 1), (2, 2)])
OrderedDict([(2, 2), (1, 1)])
OrderedDict([(1, 1), (3, 3)])
OrderedDict([(1, 1), (3, 3)])
OrderedDict([(3, 3), (4, 4)])
OrderedDict([(3, 3), (4, 4)])
OrderedDict([(4, 4), (3, 3)])
OrderedDict([(3, 3), (4, 4)])

Complejidad de tiempo :O(1)
Otra implementación de LRU