Comment implémenter le cache LFU en utilisant des structures de données simples et minimales?

Question

Cette question m'a été posée lors d'une interview où il a d'abord posé une question sur la différence entre LRU et LFU et a ensuite demandé de mettre en œuvre les deux. Je savais que LRU pouvait être implémenté via LinkedHashMap mais j'ai été confondu avec LFU. Quelqu'un peut-il me dire comment l'implémenter avec les structures de données les plus simples avec une bonne explication? Peut-il aussi être implémenté avec LinkedHashMap aussi?

Answer 1

En supposant que les entrées de cache ont été saisies, vous pouvez le faire avec une file d'attente (LinkedList) et une carte (HashMap). (Supposons que la file d'attente et la carte sont pleines)
Sélectionnez une limite b pour la file d'attente. Sur chaque demande de cache, placez la clé de la page demandée dans la file d'attente, puis interrogez la file d'attente.
Si la page que vous souhaitez est sur la carte, renvoyez la page. Si la page ne se trouve pas sur la carte, trouvez la clé la moins fréquente dans la file d'attente, qui se trouve également dans la carte ou la clé de la page que vous voulez. Si cette clé est la clé de la page que vous voulez, ne faites rien; Sinon, supprimez l'entrée de la carte pour cette clé et insérez votre page dans la carte.
Retournez votre page.

La complexité pour un accès au cache est O (1), O (b) pour un échec.
Cela suppose que vous souhaitez limiter la fréquence. c'est à dire. "moins fréquemment utilisé dans les dernières demandes b" au lieu de "moins fréquemment utilisé".