Quelle est la différence entre les algorithmes lru et lfu ?

Différence : LRU est l'algorithme de remplacement de page le moins récemment utilisé, qui élimine les pages qui n'ont pas été utilisées depuis le plus longtemps ; tandis que LFU est l'algorithme de remplacement de page le moins récemment utilisé, qui élimine les pages qui ont été utilisées ; visité le moins de fois au cours d'une certaine période. La clé de LRU est d'examiner la durée entre la dernière utilisation de la page et la planification, tandis que la clé de LFU est d'examiner la fréquence d'utilisation de la page au cours d'une certaine période de temps ;

L'environnement d'exploitation de ce tutoriel : système Windows 7, ordinateur Dell G3.

La mise en cache est essentielle pour le développement Web et constitue également le moyen le plus courant d'améliorer les performances. Qu'il s'agisse du cache du navigateur (s'il s'agit d'un navigateur Chrome, vous pouvez le visualiser via chrome:://cache) ou du cache côté serveur (via une base de données en mémoire telle que memcached ou redis). La mise en cache peut non seulement accélérer l'accès des utilisateurs, mais également réduire la charge et la pression du serveur. Ensuite, il est particulièrement important de comprendre les stratégies et les principes des algorithmes courants d’élimination du cache.

Algorithmes de mise en cache courants

• LRU (Le moins récemment utilisé) Le moins récemment utilisé, si les données ont été consultées récemment, la probabilité d'être consultées dans le futur est également plus élevé.
• LFU (Le moins fréquemment utilisé) Le moins fréquemment utilisé Si une donnée a été rarement utilisée au cours de la période récente, il est également très peu probable qu'elle soit utilisée à l'avenir.
• FIFO (Fist in first out). Si une donnée entre en premier dans le cache, elle doit être éliminée au plus tôt.

Cache LRU

Les stratégies de mise en cache comme les navigateurs et Memcached utilisent toutes l'algorithme LRU. L'algorithme LRU mettra en cache les données les moins visitées dans un avenir proche. les données sont éliminées. La raison pour laquelle LRU est si populaire est qu'il est relativement simple à mettre en œuvre, et il est également très pratique pour les problèmes pratiques, avec de bonnes performances d'exécution et un taux de réussite élevé. Parlons de la façon d'implémenter le cache LRU :

• De nouvelles données sont insérées en tête de la liste chaînée
• Chaque fois que le cache arrive (c'est-à-dire les données mises en cache sont accessibles), puis déplacez les données en tête de la liste chaînée
• Lorsque la liste chaînée est pleine, supprimez les données à la fin de la liste chaînée

LRU Le cache a les opérations suivantes :

• set(key,value) : Si la clé existe dans le hashmap, réinitialisez d'abord la valeur correspondante, puis obtenez le nœud cur correspondant, supprimez le nœud cur du lien lié list et déplacez-le en tête de la liste chaînée ; si la clé est dans Si le hashmap n'existe pas, créez un nouveau nœud et placez le nœud en tête de la liste chaînée. Lorsque le cache est plein, supprimez simplement le dernier nœud de la liste chaînée.
• get(key) : Si la clé existe dans le hashmap, placez le nœud correspondant en tête de la liste chaînée et renvoyez la valeur correspondante si elle n'existe pas, renvoyez -1.

La différence entre LRU et LFU :

LRU est l'algorithme de remplacement de page le moins récemment utilisé (Least Récemment utilisé), c'est-à-dire qu'il est éliminé en premier et n'a pas été utilisé depuis très longtemps. Utilisez la page !

LFU est l'algorithme de remplacement de page le moins fréquemment utilisé (Least Frequency Used), ce qui signifie éliminer la page avec le moins de visites dans une certaine période !

Par exemple, la période T de la deuxième méthode est de 10 minutes. Si la pagination est effectuée toutes les minutes, le bloc de mémoire principal est 3, et si le sens de page requis est 2 1 2 1 2 3 4

Notez qu'une interruption de page manquante se produira lors de l'ajustement de la page 4

Si l'algorithme LRU est utilisé, la page 1 doit être modifiée (la page 1 n'a pas été utilisée depuis le plus longtemps), mais la page 3 devrait être modifié selon l'algorithme LFU (en dix minutes, la page 3 n'a été utilisée qu'une seule fois)

Résumé

On voit que la clé de LRU est de regardez le temps écoulé entre la dernière fois que la page a été utilisée et la planification

Et la clé de LFU est de regarder à quelle fréquence une page est utilisée dans une certaine période de temps !

Pour plus de connaissances connexes, veuillez visiter la colonne FAQ !

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!