Quelle est la différence entre le LFR et le LFU?
Quelle est la différence entre LRU et LFU implémentations de cache?
je sais que LRU peut être implémenté en utilisant LinkedHashMap.
Mais comment implémenter la cache LFU?
3 réponses
considérons un flux constant de requêtes de cache avec une capacité de cache de 3, Voir ci-dessous:
A, B, C, A, A, A, A, A, A, A, A, A, A, A, B, C, D
Si l'on considère un most Recently Used (LRU) cache avec HashMap + implémentation de liste doublement liée avec O(1) eviction time et O (1) load time, nous aurions les éléments suivants mis en cache lors du traitement des requêtes de mise en cache comme mentionné ci-dessus.
[A]
[A, B]
[A, B, C]
[B, C, A] <- a stream of As keeps A at the head of the list.
[C, A, B]
[A, B, C]
[B, C, D] <- here, we evict A, we can do better!
Quand vous regardez cet exemple, vous peut facilement voir que nous pouvons faire mieux - étant donné la plus grande chance attendue de demander un A à l'avenir, nous ne devrions pas l'expulser même s'il a été utilisé le moins récemment.
A - 12
B - 2
C - 2
D - 1
utilisation la moins fréquente (UML) cache tire avantage de cette information en gardant une trace du nombre de fois que la requête cache a été utilisée dans son algorithme d'expulsion.
LRU est un algorithme d'expulsion de cache appelé cache le moins récemment utilisé.
Regarde ce ressource
LFU est un algorithme d'expulsion de cache appelé cache le moins fréquemment utilisé.
Il nécessite trois structures de données. L'une est une table de hachage qui est utilisée pour mettre en cache la clé/les valeurs afin que, avec une clé, nous puissions récupérer l'entrée cache à O(1). La deuxième est une liste double liée pour chaque fréquence d'accès. La fréquence max est plafonnée à la taille du cache pour éviter de créer de plus en plus d'entrées dans la liste de fréquences. Si nous avons un cache de taille max 4, alors nous finirons avec 4 fréquences différentes. Chaque fréquence aura une liste double liée pour garder la trace des entrées de cache appartenant à cette fréquence particulière. La troisième structure de données serait de relier d'une manière ou d'une autre ces listes de fréquences. Il peut s'agir d'un tableau ou d'une autre liste liée de sorte qu'en accédant à une entrée de cache il peut être facilement promu à la prochaine liste de fréquences dans le temps O (1).
la principale différence est que dans LRU nous vérifions seulement sur quelle page est récemment que utilisé vieux dans le temps que d'autres pages I. e vérification fondée uniquement sur les pages utilisées récemment. Mais dans LFU nous vérifions la vieille page aussi bien que la fréquence de cette page et si la fréquence de la page est plus lag que la vieille page nous ne pouvons pas la supprimer et si nous toutes les vieilles pages ont la même fréquence alors prendre le dernier I. la méthode FIFO pour ça. et supprimer la page....