Se pare că browserul dvs. nu este suportat de aplicația noastră.

Soluție Explicație

Complexitate în timp de execuție

get (hashset): O(1) în cazul mediu, O(n) în cel mai rău caz

set (hashset): Constant, O(1)

ștergere la cap la adăugarea unui nou element (listă legată): Constant, O(1)

cercetare pentru ștergere și adăugare la coadă (listă legată): O(n)

Complexitate: O(n)

Complexitatea memoriei

Liniară, O(n) unde n este dimensiunea cache-ului.

Descompunerea soluției

Caching-ul este o tehnică de stocare a datelor într-o memorie mai rapidă (de obicei RAM) pentru a servi mai repede cererile viitoare. Mai jos sunt prezentate câteva exemple comune în care se utilizează memoria cache:

• Cașca unui procesor este utilizată pentru a citi datele mai rapid din memoria principală (RAM).
• Cașca în RAM poate fi utilizată pentru a stoca o parte din datele de pe disc în RAM și a servi mai rapid cererile viitoare.
• Răspunsurile de rețea pot fi stocate în memoria cache în RAM pentru a evita prea multe apeluri de rețea.

Cu toate acestea, memoria cache nu este de obicei suficient de mare pentru a stoca întregul set de date. Așadar, trebuie să evacuăm datele din memoria cache ori de câte ori aceasta devine plină. Există o serie de algoritmi de cache pentru a implementa o politică de evacuare a cache-ului. LRU este foarte simplu și este un algoritm utilizat în mod obișnuit. Conceptul de bază al algoritmului LRU este de a evacua cele mai vechi date din memoria cache pentru a găzdui mai multe date.

Pentru a implementa o memorie cache LRU folosim două structuri de date: un hashmap și o listă dublu legată. O listă dublu legată ajută la menținerea ordinii de evacuare, iar un hashmap ajută la căutarea O(1) a cheilor din cache. Iată algoritmul pentru memoria cache LRU.

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

Rețineți că lista dublu legată este utilizată pentru a ține evidența celor mai recent accesate elemente. Elementul de la coada listei dublu legate este elementul cel mai recent accesat. Toate elementele nou inserate (în put) merg la coada listei. În mod similar, orice element accesat (în operațiunea get) merge la coada listei.

.