LRU-cache er en forkortelse for Least Recently Used Cache, som fjerner den senest anvendte post. Da formålet med cachen er at give en hurtig og effektiv måde at hente data på, skal den opfylde visse krav.
Nogle af kravene er
- Fikseret størrelse: Cache skal have nogle grænser for at begrænse hukommelsesforbruget.
- Hurtig adgang:
- Cache-indsættelse og opslag skal være hurtige, helst på O(1)-tid.
- Udskiftning af indgang i tilfælde af, at hukommelsesgrænsen er nået: En cache skal have en effektiv algoritme til at fjerne posten, når hukommelsen er fuld.
I tilfælde af LRU-cache fjerner vi den senest anvendte post, så vi skal holde styr på de senest anvendte poster, poster, der ikke er blevet brugt længe, og som er blevet brugt for nylig. samt opslags- og indsættelsesoperationen skal være hurtig nok.
Når vi tænker på O(1)-opslag, er HashMap den åbenlyse datastruktur, vi kommer til at tænke på. HashMap giver O(1) indsættelse og opslag, men HashMap har ikke en mekanisme til at spore, hvilken post der er blevet spurgt for nylig og hvilken ikke.
For at spore dette kræver vi en anden datastruktur, som giver hurtig indsættelse, sletning og opdatering, og i tilfælde af LRU bruger vi Doubly Linkedlist . Årsagen til at vælge Doubly LinkList er O(1) sletning, opdatering og indsættelse, hvis vi har adressen på den knude, som denne operation skal udføres på.
Så vores implementering af LRU-cache vil have HashMap og Doubly LinkedList. I hvilken HashMap vil indeholde nøglerne og adressen på knuderne i Doubly LinkedList . Og Doubly LinkedList vil indeholde værdierne af nøglerne.
Da vi skal holde styr på de senest anvendte poster, vil vi bruge en smart tilgang. Vi vil fjerne elementet fra bunden og tilføje elementet i starten af LinkedList, og når der er adgang til en post, vil den blive flyttet til toppen. så de senest anvendte poster vil være øverst og de mindst anvendte vil være nederst.
Lad os implementere LRU Cache.
Jeg håber kode og tutorial er selvforklarende.