Explication de la solution
Complexité du temps d’exécution
get (hashset) : O(1) dans le cas moyen, O(n) dans le pire cas
set (hashset) : Constante, O(1)
suppression en tête lors de l’ajout d’un nouvel élément (liste chaînée) : Constante, O(1)
recherche de suppression et d’ajout en queue (liste chaînée) : O(n)
Complexité : O(n)
Complexité de la mémoire
Linéaire, O(n) où n est la taille du cache.
Décomposition de la solution
Le cache est une technique pour stocker des données dans un stockage plus rapide (généralement la RAM) pour servir les demandes futures plus rapidement. Voici quelques exemples courants où le cache est utilisé :
- Un cache de processeur est utilisé pour lire les données plus rapidement à partir de la mémoire principale (RAM).
- Le cache en RAM peut être utilisé pour stocker une partie des données du disque en RAM et servir les futures demandes plus rapidement.
- Les réponses du réseau peuvent être mises en cache en RAM pour éviter trop d’appels réseau.
Cependant, le stockage du cache n’est généralement pas assez grand pour stocker l’ensemble des données. Il faut donc évincer les données du cache dès qu’il est plein. Il existe un certain nombre d’algorithmes de mise en cache pour mettre en œuvre une politique d’éviction du cache. LRU est un algorithme très simple et couramment utilisé. Le concept de base de l’algorithme LRU est d’évincer les données les plus anciennes du cache pour accueillir plus de données.
Pour mettre en œuvre un cache LRU, nous utilisons deux structures de données : une hashmap et une liste doublement liée. Une liste doublement liée aide à maintenir l’ordre d’éviction et une hashmap aide à la recherche O(1) des clés du cache. Voici l’algorithme pour le 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 ReturnNotez que la liste doublement liée est utilisée pour garder la trace des éléments les plus récemment accédés. L’élément à la queue de la liste doublement liée est l’élément le plus récemment accédé. Tous les éléments nouvellement insérés (dans put) vont à la queue de la liste. De même, tout élément accédé (en opération get) va à la queue de la liste.
