Úgy tűnik, hogy a böngészőjét nem támogatja az alkalmazásunk.

Megoldás magyarázata

Futtatási idő bonyolultsága

get (hashset): O(1) átlagos esetben, O(n) legrosszabb esetben

set (hashset): Állandó, O(1)

törlés a fejnél új elem hozzáadásakor (kapcsolt lista): Állandó, O(1)

keresés törléskor és hozzáadáskor a farban (láncolt lista): O(n)

Bonyolultság: O(n)

Memória komplexitás

Lineáris, O(n), ahol n a gyorsítótár mérete.

Megoldás bontása

A gyorsítótárazás egy olyan technika, amely az adatokat egy gyorsabb tárolóban (általában RAM) tárolja a jövőbeli kérések gyorsabb kiszolgálása érdekében. Az alábbiakban néhány gyakori példát mutatunk be, ahol a gyorsítótárat használják:

• A processzor gyorsítótárát arra használják, hogy gyorsabban olvassanak adatokat a főmemóriából (RAM).
• A gyorsítótár a RAM-ban használható a lemezadatok egy részének RAM-ban való tárolására és a jövőbeli kérések gyorsabb kiszolgálására.
• A hálózati válaszok gyorsítótárba helyezhetők a RAM-ban a túl sok hálózati hívás elkerülése érdekében.

A gyorsítótár azonban általában nem elég nagy a teljes adatállomány tárolásához. Ezért az adatokat ki kell ürítenünk a gyorsítótárból, amikor az megtelik. Számos gyorsítótárazási algoritmus létezik a gyorsítótárból való kilakoltatási politika megvalósítására. Az LRU nagyon egyszerű és általánosan használt algoritmus. Az LRU algoritmus lényege, hogy a legrégebbi adatokat kiüríti a gyorsítótárból, hogy több adat férjen el benne.

Az LRU gyorsítótár megvalósításához két adatszerkezetet használunk: egy hashmapet és egy duplán összekapcsolt listát. A duplán kapcsolt lista segít a kilakoltatási sorrend fenntartásában, a hashmap pedig a gyorsítótár kulcsainak O(1) keresésében. Íme az LRU gyorsítótár algoritmusa.

If the element exists in hashmapmove the accessed element to the tail of the linked listOtherwise,if eviction is needed i.e. cache is already fullRemove the head element from doubly linked list and delete its hashmap entryAdd the new element at the tail of linked list and in hashmapGet from Cache and Return

Megjegyezzük, hogy a duplán összekapcsolt listát a legutóbb elért elemek nyomon követésére használjuk. A duplán kapcsolt lista végén lévő elem a legfrissebben elért elem. Minden újonnan beillesztett elem (in put) a lista végére kerül. Hasonlóképpen, minden elem, amelyhez hozzáférünk (get műveletben), a lista végére kerül.