Sembra che il tuo browser non sia supportato dalla nostra applicazione.

Soluzione Spiegazione

Complessità runtime

get (hashset): O(1) nel caso medio, O(n) nel caso peggiore

set (hashset): Costante, O(1)

cancellazione in testa quando si aggiunge un nuovo elemento (lista collegata): Costante, O(1)

cerca per cancellare e aggiungere in coda (lista collegata): O(n)

Complessità: O(n)

Complessità della memoria

Lineare, O(n) dove n è la dimensione della cache.

Riduzione della soluzione

La cache è una tecnica per memorizzare i dati in una memoria più veloce (di solito RAM) per servire più velocemente le richieste future. Sotto ci sono alcuni esempi comuni in cui viene usata la cache:

• La cache di un processore viene usata per leggere i dati più velocemente dalla memoria principale (RAM).
• La cache nella RAM può essere usata per memorizzare parte dei dati del disco nella RAM e servire le richieste future più velocemente.
• Le risposte della rete possono essere memorizzate nella RAM per evitare troppe chiamate alla rete.

Tuttavia, la cache non è solitamente abbastanza grande per memorizzare l’intero set di dati. Quindi abbiamo bisogno di espellere i dati dalla cache ogni volta che diventa piena. Ci sono diversi algoritmi di caching per implementare una politica di evacuazione della cache. LRU è molto semplice e un algoritmo comunemente usato. Il concetto centrale dell’algoritmo LRU è quello di eliminare i dati più vecchi dalla cache per ospitare più dati.

Per implementare una cache LRU usiamo due strutture dati: una hashmap e una lista doppiamente collegata. Una lista doppiamente collegata aiuta a mantenere l’ordine di evacuazione e una hashmap aiuta con O(1) la ricerca delle chiavi della cache. Ecco l’algoritmo per la 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

Nota che la lista doppiamente collegata è usata per tenere traccia degli elementi più recentemente acceduti. L’elemento in coda alla lista doppiamente collegata è l’elemento ad accesso più recente. Tutti i nuovi elementi inseriti (in put) vanno in coda alla lista. Allo stesso modo, ogni elemento a cui si accede (nell’operazione get) va in coda alla lista.