Η εφαρμογή μιας πολιτικής αντικατάστασης cache LRU βοηθά στη βελτιστοποίηση της χρήσης μνήμης αφαιρώντας τα λιγότερο πρόσφατα προσπελασμένα αντικείμενα όταν η cache φτάσει την χωρητικότητά της.

Κατανόηση λανθάνουσας μνήμης LRU

Μια LRU (Λίγο πρόσφατα χρησιμοποιημένη) cache κρατά την παρακολούθηση της χρήσης στοιχείων για να καθορίσει ποια δεδομένα για να εκδιώξει όταν απαιτείται χώρος.

Βασικά συστατικά μιας λανθάνουσας μνήμης LRU

Μια αποτελεσματική LRU cache συνδυάζει συνήθως δύο δομές δεδομένων:

  • Χάρτης Hash: Παρέχει γρήγορη πρόσβαση σε στοιχεία cache.
  • Διπλή Λίστα Συνδεδεμένων: Διατηρεί τη σειρά χρήσης του αντικειμένου, με πιο πρόσφατη στο μπροστινό μέρος.

Βήματα εφαρμογής

Ακολουθήστε αυτά τα βήματα για την εφαρμογή μιας λανθάνουσας μνήμης LRU:

  • Αρχικοποίηση του χάρτη hash και διπλά συνδεδεμένη λίστα.
  • Για πρόσβαση δεδομένων, μετακινήστε το αντικείμενο στην μπροστινή όψη της λίστας.
  • Εάν η λανθάνουσα μνήμη υπερβαίνει την ικανότητα, αφαιρέστε το στοιχείο στο τέλος του καταλόγου.
  • Ενημέρωση του χάρτη hash ανάλογα κατά τη διάρκεια των καταχωρήσεων και διαγραφές.

Εφαρμογή δείγματος σε Python

Εδώ είναι ένα απλό παράδειγμα μιας LRU cache σε Python:

Σημείωση: Ο κώδικας αυτός χρησιμοποιεί την ενότητα συλλογών για το OrderedDict, η οποία απλοποιεί την υλοποίηση.

«Πύθωνας

από τις συλλογές εισαγωγής OrderedDict

κατηγορία LRUCache:

def init (εαυτός, ικανότητα):

αυτο.cache = ΔιαταγήDict ()

αυτοδυναμία = ικανότητα

def get( εαυτό, κλειδί):

εάν το κλειδί δεν είναι σε self.cache:

επιστροφή -1

self.cache.move to end (key)

επιστροφή αυτο.cache[κλειδί]

def put( self, κλειδί, τιμή):

self.cache[κλειδί] = τιμή

self.cache.move to end (key)

εάν len(self.cache) > αυτοδυναμία:

self.cache.popitem (last=False)

\"\"