Reto: LRU Caché

Clase 21 de 41 • Curso de Algoritmos Avanzados: Estructuras de Datos Lineales

Contenido del curso

Introducción

1
¿Ya tomaste el Curso Avanzado de Algoritmos: Patrones de Arrays y Strings?
00:52 min

Lista Enlazada

Pilas y colas

Colas de prioridad

Próximos pasos

41
Toma el Curso Avanzado de Algoritmos: Grafos y Árboles
00:33 min

Tomar examen

Comentarios

Nicolas Alpargatero

student•

Problema y carateristicas:

Algoritmo real usando para almacenar en memoria los datos.

Diseñar una estructura de datos que siga las restricciones de una caché de uso menos reciente (LRU)

Inicializa la clase cache LRU con una capacidad de tamaño positivo.

int get(int key) Devuelve el valor de la llave si esta existe, en caso contrario devuelve -1.

void put(int key, int value) Actualiza el valor de la llave si esta existe. En caso contrario, añade el par llave-valor al caché. Si el número de llaves supera la capacidad del caché, elimina la pareja llave-valor menos utilizada recientemente.

Características:

Como entrada en la clase constructor un tamaño, que indica la cantidad que podemos almacenar.
Guardamos solo los más recientes si superamos la capacidad que nos pasan por parámetro, eliminamos los datos menos utilizados.
Complejidad temporal debe ser O(1)
la primera function get return un entero, la cual recibe una llave que también es un entero. Esta devuelve el valor de la llave si esta existe en mis datos almacenados y si no return -1
put() no return nada. Tenemos dos entradas, la llave y el valor, si la llave ya existe actualicemos el valor, de lo contrario creamos en nuestra cache, la llave y el valor.
cada vez que actualicemos o agreguemos un valor, es decir, cada vez que llamemos put() el valor actualizado o cambiante, o creado es el valor utilizado más recientemente
si el numero de llaves supera la capacidad del cache debemos eliminar la pareja llave valor, menos utilizada.

Nicolas Alpargatero

student•

Estaba difícil para mí, me toco con ayuda por tiempo, pero bueno logré entenderlo, principalmente es que se utiliza una combinación de una lista doblemente enlazada y un diccionario. . La cabeza de la lista doblemente enlazada apunta al elemento más recientemente utilizado, mientras que la cola apunta al elemento menos recientemente utilizado.

REYNALDO FABIAN NORIEGA ZAMBRANO

student•

MI aporte en C++. Podria mover la logica de actualizar la cabeza de la lista a otra funcion y evitar code duplication, pero esta implementacion es funcional :P

class Node{
public:
	int key;
	int val;
	Node *prev = nullptr;
	Node *next = nullptr;
};


class LRUCache{
public:
	int capacity;
	Node *head;
	Node *tail;
	std::unordered_map<int, Node *> cache_keys;

	LRUCache(){
		this->capacity = 10;
	}
	int get(int key){
		auto iter = cache_keys.find(key);
		if(iter != cache_keys.end()){
			Node *current = iter->second;
			Node *prev = iter->second->prev;
			Node *next = iter->second->next;

			if(current == this->head) return this->head->val;
			else{ 
				if(prev != nullptr) prev->next = next;
				if(next != nullptr) next->prev = prev;
				else{
					this->tail = prev;
				}

				current->next = this->head;
				current->prev = nullptr;
				this->head->prev = current;
				this->head = current;
				return head->val;
			}
		}
		else return -1;
	}
	
	void put(int key, int val){

		if(cache_keys.size() == 0){
			Node *entry = new Node;
			entry->val = val;
			entry->key = key;
			this->head = entry;
			this->tail = entry;
			cache_keys[key] = entry;
		}
		else{
			auto iter = cache_keys.find(key);
			if (iter  != cache_kes.end()){
				iter->second->val = val;
				
				Node *current = iter->second;
				Node *prev = iter->second->prev;
				Node *next = iter->second->next;

				if(current != this->head){ 
					if(prev != nullptr) prev->next = next;
					if(next != nullptr) next->prev = prev;
					else{
						this->tail = prev;
					}

					current->next = this->head;
					current->prev = nullptr;
					this->head->prev = current;
					this->head = current;
				}
			}
			else{
				Node *entry = new Node;
				entry->val = val;
				entry->key = key;
				entry->next = this->head;
				entry->prev = nullptr;

				this->head->prev = entry;
				this->head = entry;

				cache_keys[key] = entry;
				if(cache_keys.size() > this->capacity){
					Node *remove = this->tail;
					cache_keys.erase(remove->key);
					this->tail = remove->prev;
					if(this->tail != nullptr){
						this->tail->next = nullptr;
					}
					else{
						this->head = nullptr;
					}
					delete remove;
				}

			}
		}
	}
};

José Ramón García

student•

El truco está en hacer una lista doblemente enlazada y un diccionario que almacena los keys y los nodos.

De esta forma el algoritmo es O(1) temporal pero O(n) en memoria

Comparto pruebas

Este es mi codigo

class Nodo:
    def __init__(self, valor, siguiente=None, anterior = None):
        self.valor = valor
        self.siguiente = siguiente 
        self.anterior = anterior
class LRU_cache:

    def __init__(self, primer_nodo, max_keys):
        self.cabeza = primer_nodo
        self.cola = primer_nodo
        self.max_keys = max_keys
        self.keys_actual = 1
        self.nodos_dicc = {}

    def get(key: int):
        if 1< key < self.keys_actual:
            return self.nodos_dicc[key].valor
        return -1

    def put(self, key: int, value: int):
        #El caso donde hay espacio para nuevas keys
        if self.keys_actual < self.max_keys:
            self.nodos_dicc[key] = Nodo(value)
            nuevo_nodo = self.nodos_dicc[key]
            nuevo_nodo.anterior = self.cola
            self.cola.siguiente = nuevo_nodo
            self.cola = nuevo_nodo
            self.keys_actual +=1

        #caso donde el key ya existe, actualizamos
        elif key in self.nodos_dicc:
            nodo_actual = self.nodos_dicc[key]
            nodo_actual.value = value #actualizamos el valor

            #Ahora quiero que por ser el nuevo actualizado, sea el nuevo tail
            nodo_siguiente = nodo_actual.siguiente
            nodo_anterior = nodo_actual.anterior

            nodo_anterior.siguiente = nodo_siguiente
            nodo_siguiente.anterior = nodo_anterior

            nodo_actual.siguiente = None
            nodo_actual.anterior = self.cola
            self.cola = nodo_actual

        #El caso donde el key no existe y ya no haya espacio
        else:
            #borrar la más antigua y esa es la cabeza
            cabeza = self.cabeza
            cabeza_siguiente = cabeza.siguiente

            cabeza_siguiente.anterior = None
            cabeza.siguente = None
            self.cabeza = cabeza_siguiente
            #hemos aislado a la cabeza y puesto una nueva

            #Ahora añadimos el nuevo valor a la cola
            self.nodos_dicc[key] = Nodo(value)
            nuevo_nodo = self.nodos_dicc[key]
            nuevo_nodo.anterior = self.cola
            self.cola.siguiente = nuevo_nodo
            self.cola = nuevo_nodo

    def imprimir(self, nodo = None):
        if nodo is None:
            nodo = self.cabeza
        actual = nodo
        while actual:
            print(actual.valor, end=" -> ")
            actual = actual.siguiente
        print("None")

Miguel Angel Reyes Moreno

student•

Con una lista doblemente enlazada y hash map se puede muy bien, comparto código en typescript:

class DoublyLinkedListNode {  key: number;  value: number;  prev: DoublyLinkedListNode | null;  next: DoublyLinkedListNode | null;
&#x20; constructor(key: number, value: number) {    this.key = key;    this.value = value;    this.prev = null;    this.next = null;  }}
class LRUCache {  private capacity: number;  private cache: Map\<number, DoublyLinkedListNode>;  private head: DoublyLinkedListNode;  private tail: DoublyLinkedListNode;
&#x20; constructor(capacity: number) {    this.capacity = capacity;    this.cache = new Map();    this.head = new DoublyLinkedListNode(0, 0);    this.tail = new DoublyLinkedListNode(0, 0);    this.head.next = this.tail;    this.tail.prev = this.head;  }
&#x20; get(key: number): number {    if (!this.cache.has(key)) {      return -1;    }
&#x20;   const node = this.cache.get(key)!;    this.removeNode(node);    this.addToFront(node);    return node.value;  }
&#x20; put(key: number, value: number): void {    if (this.cache.has(key)) {      const node = this.cache.get(key)!;      this.removeNode(node);      node.value = value;      this.addToFront(node);    } else {      if (this.cache.size >= this.capacity) {        const leastUsed = this.tail.prev!;        this.removeNode(leastUsed);        this.cache.delete(leastUsed.key);      }      const newNode = new DoublyLinkedListNode(key, value);      this.addToFront(newNode);      this.cache.set(key, newNode);    }  }
&#x20; private removeNode(node: DoublyLinkedListNode): void {    const prevNode = node.prev!;    const nextNode = node.next!;    prevNode.next = nextNode;    nextNode.prev = prevNode;  }
&#x20; private addToFront(node: DoublyLinkedListNode): void {    node.prev = this.head;    node.next = this.head.next;    this.head.next!.prev = node;    this.head.next = node;  }}

class Node{
public:
	int key;
	int val;
	Node *prev = nullptr;
	Node *next = nullptr;
};


class LRUCache{
public:
	int capacity;
	Node *head;
	Node *tail;
	std::unordered_map<int, Node *> cache_keys;

	LRUCache(){
		this->capacity = 10;
	}
	int get(int key){
		auto iter = cache_keys.find(key);
		if(iter != cache_keys.end()){
			Node *current = iter->second;
			Node *prev = iter->second->prev;
			Node *next = iter->second->next;

			if(current == this->head) return this->head->val;
			else{ 
				if(prev != nullptr) prev->next = next;
				if(next != nullptr) next->prev = prev;
				else{
					this->tail = prev;
				}

				current->next = this->head;
				current->prev = nullptr;
				this->head->prev = current;
				this->head = current;
				return head->val;
			}
		}
		else return -1;
	}
	
	void put(int key, int val){

		if(cache_keys.size() == 0){
			Node *entry = new Node;
			entry->val = val;
			entry->key = key;
			this->head = entry;
			this->tail = entry;
			cache_keys[key] = entry;
		}
		else{
			auto iter = cache_keys.find(key);
			if (iter  != cache_kes.end()){
				iter->second->val = val;
				
				Node *current = iter->second;
				Node *prev = iter->second->prev;
				Node *next = iter->second->next;

				if(current != this->head){ 
					if(prev != nullptr) prev->next = next;
					if(next != nullptr) next->prev = prev;
					else{
						this->tail = prev;
					}

					current->next = this->head;
					current->prev = nullptr;
					this->head->prev = current;
					this->head = current;
				}
			}
			else{
				Node *entry = new Node;
				entry->val = val;
				entry->key = key;
				entry->next = this->head;
				entry->prev = nullptr;

				this->head->prev = entry;
				this->head = entry;

				cache_keys[key] = entry;
				if(cache_keys.size() > this->capacity){
					Node *remove = this->tail;
					cache_keys.erase(remove->key);
					this->tail = remove->prev;
					if(this->tail != nullptr){
						this->tail->next = nullptr;
					}
					else{
						this->head = nullptr;
					}
					delete remove;
				}

			}
		}
	}
};

class Nodo:
    def __init__(self, valor, siguiente=None, anterior = None):
        self.valor = valor
        self.siguiente = siguiente 
        self.anterior = anterior
class LRU_cache:

    def __init__(self, primer_nodo, max_keys):
        self.cabeza = primer_nodo
        self.cola = primer_nodo
        self.max_keys = max_keys
        self.keys_actual = 1
        self.nodos_dicc = {}

    def get(key: int):
        if 1< key < self.keys_actual:
            return self.nodos_dicc[key].valor
        return -1

    def put(self, key: int, value: int):
        #El caso donde hay espacio para nuevas keys
        if self.keys_actual < self.max_keys:
            self.nodos_dicc[key] = Nodo(value)
            nuevo_nodo = self.nodos_dicc[key]
            nuevo_nodo.anterior = self.cola
            self.cola.siguiente = nuevo_nodo
            self.cola = nuevo_nodo
            self.keys_actual +=1

        #caso donde el key ya existe, actualizamos
        elif key in self.nodos_dicc:
            nodo_actual = self.nodos_dicc[key]
            nodo_actual.value = value #actualizamos el valor

            #Ahora quiero que por ser el nuevo actualizado, sea el nuevo tail
            nodo_siguiente = nodo_actual.siguiente
            nodo_anterior = nodo_actual.anterior

            nodo_anterior.siguiente = nodo_siguiente
            nodo_siguiente.anterior = nodo_anterior

            nodo_actual.siguiente = None
            nodo_actual.anterior = self.cola
            self.cola = nodo_actual

        #El caso donde el key no existe y ya no haya espacio
        else:
            #borrar la más antigua y esa es la cabeza
            cabeza = self.cabeza
            cabeza_siguiente = cabeza.siguiente

            cabeza_siguiente.anterior = None
            cabeza.siguente = None
            self.cabeza = cabeza_siguiente
            #hemos aislado a la cabeza y puesto una nueva

            #Ahora añadimos el nuevo valor a la cola
            self.nodos_dicc[key] = Nodo(value)
            nuevo_nodo = self.nodos_dicc[key]
            nuevo_nodo.anterior = self.cola
            self.cola.siguiente = nuevo_nodo
            self.cola = nuevo_nodo

    def imprimir(self, nodo = None):
        if nodo is None:
            nodo = self.cabeza
        actual = nodo
        while actual:
            print(actual.valor, end=" -> ")
            actual = actual.siguiente
        print("None")

class DoublyLinkedListNode {  key: number;  value: number;  prev: DoublyLinkedListNode | null;  next: DoublyLinkedListNode | null;
&#x20; constructor(key: number, value: number) {    this.key = key;    this.value = value;    this.prev = null;    this.next = null;  }}
class LRUCache {  private capacity: number;  private cache: Map\<number, DoublyLinkedListNode>;  private head: DoublyLinkedListNode;  private tail: DoublyLinkedListNode;
&#x20; constructor(capacity: number) {    this.capacity = capacity;    this.cache = new Map();    this.head = new DoublyLinkedListNode(0, 0);    this.tail = new DoublyLinkedListNode(0, 0);    this.head.next = this.tail;    this.tail.prev = this.head;  }
&#x20; get(key: number): number {    if (!this.cache.has(key)) {      return -1;    }
&#x20;   const node = this.cache.get(key)!;    this.removeNode(node);    this.addToFront(node);    return node.value;  }
&#x20; put(key: number, value: number): void {    if (this.cache.has(key)) {      const node = this.cache.get(key)!;      this.removeNode(node);      node.value = value;      this.addToFront(node);    } else {      if (this.cache.size >= this.capacity) {        const leastUsed = this.tail.prev!;        this.removeNode(leastUsed);        this.cache.delete(leastUsed.key);      }      const newNode = new DoublyLinkedListNode(key, value);      this.addToFront(newNode);      this.cache.set(key, newNode);    }  }
&#x20; private removeNode(node: DoublyLinkedListNode): void {    const prevNode = node.prev!;    const nextNode = node.next!;    prevNode.next = nextNode;    nextNode.prev = prevNode;  }
&#x20; private addToFront(node: DoublyLinkedListNode): void {    node.prev = this.head;    node.next = this.head.next;    this.head.next!.prev = node;    this.head.next = node;  }}

Reto: LRU Caché

Introducción

¿Ya tomaste el Curso Avanzado de Algoritmos: Patrones de Arrays y Strings?

Lista Enlazada

Estructura de datos: Lista Enlazada

Programando listas enlazadas con Java

Cómo Invertir una Lista Enlazada

Odd Even Linked List: análisis del problema

Solución de Odd Even Linked List

Playground: Odd Even Liked List

Programando Odd Even Linked List con C++

Linked List Cycle: análisis del problema

Solución de Linked List Cycle

Playground: Linked List Cycle

Programando Linked List Cycle con Python

Palindrome Linked List: análisis del problema

Solución de Palindrome Linked List

Playground: Palindrome Linked List

Programando Palindrome Linked List con Java

Reorder List: análisis del problema

Solución de Reorder List

Programando Reorder List con JavaScript

Playground: Reorder List Without Repeated Values

Reto: LRU Caché

Ejercicios Prácticos con Listas Enlazadas y Historial de Navegador

Operaciones con Listas Enlazadas: Suma, Intercambio y Navegador

Pilas y colas

Estructura de datos: Pilas y Colas

Paréntesis Válido: análisis del problema

Solución de Paréntesis Válido

Playground: Paréntesis Válido

Programando Paréntesis Válido con C++

Comparación de Cadenas con Backspaces

Colas de prioridad

Estructura de datos: Colas de Prioridad

K Closest Points to Origin: análisis del problema

Solución de K Closest Points to Origin

Playground: K Closest Points to Origin

Programando K Closest Points to Origin con Python

Reorganize String: análisis del problema

Solución de Reorganize String

Playground: Reorganize String

Programando Reorganize String con Python

Colas de Prioridad: Ejercicios Prácticos y Soluciones

Colas de Prioridad y Gestión de Eventos

Próximos pasos

Toma el Curso Avanzado de Algoritmos: Grafos y Árboles