Explicação da solução
Complexidade de tempo de execução
get (hashset): O(1) no caso médio, O(n) no pior caso
set (hashset): Constante, O(1)
deleção na cabeça ao adicionar um novo elemento (lista ligada): Constante, O(1)
procura para eliminar e adicionar à cauda (lista ligada): O(n)
Complexidade: O(n)
Complexidade da memória
Linear, O(n) onde n é o tamanho do cache.
Solution Breakdown
Caching é uma técnica para armazenar dados em um armazenamento mais rápido (geralmente RAM) para atender a pedidos futuros mais rapidamente. Abaixo estão alguns exemplos comuns onde o cache é usado:
- Um cache de processador é usado para ler dados mais rapidamente da memória principal (RAM).
- Cache na RAM pode ser usado para armazenar parte dos dados do disco na RAM e atender pedidos futuros mais rapidamente.
- Respostas da rede podem ser armazenadas em cache na RAM para evitar muitas chamadas de rede.
No entanto, o cache de armazenamento geralmente não é grande o suficiente para armazenar o conjunto de dados completo. Portanto, precisamos despejar os dados do cache sempre que ele ficar cheio. Há uma série de algoritmos de cache para implementar uma política de despejo de cache. A LRU é muito simples e um algoritmo comumente usado. O conceito central do algoritmo de LRU é despejar os dados mais antigos do cache para acomodar mais dados.
Para implementar um cache LRU usamos duas estruturas de dados: um hashmap e uma lista duplamente ligada. Uma lista duplamente ligada ajuda na manutenção da ordem de despejo e um hashmap ajuda na busca O(1) das chaves em cache. Aqui vai o algoritmo para cache LRU.
If the element exists in hashmapmove the accessed element to the tail of the linked listOtherwise,if eviction is needed i.e. cache is already fullRemove the head element from doubly linked list and delete its hashmap entryAdd the new element at the tail of linked list and in hashmapGet from Cache and ReturnNota que a lista duplamente ligada é usada para manter o controle dos elementos mais recentemente acessados. O elemento na cauda da lista duplamente ligada é o elemento mais recentemente acessado. Todos os elementos recém inseridos (em put) vão para a cauda da lista. Da mesma forma, qualquer elemento acessado (em get operation) vai para a cauda da lista.
