Come progettare un ultimo nascondiglio di recente usato?

Question

Come progettare un ultimo nascondiglio di recente usato?

Si supponga che avete visitato alcuni elementi. È necessario progettare una struttura di dati di attesa questi articoli. Ogni elemento è associato con l'ultimo tempo visitato.

Ogni volta quando si visita un elemento, controllare nella struttura dati. Se l'articolo è stato nella cache, aggiornare il suo tempo di visita. In caso contrario, inserirla nella cache. La dimensione della cache è fisso, se è pieno, eliminare l'elemento più antico.

La mia soluzione:

1. Utilizza una mappa

2. Initaliztion: Ordina la mappa con f (visitTime) con ordine decrescente. O (NLG n)

3. Se un elemento viene visitato, cercatela nella mappa con O (lg n).

4. Se è stato nella mappa, aggiornare il tempo O (1). Ordina la mappa O (lg n).

5. In caso contrario, inserirlo nella mappa e quindi ordinare. O (lg n)

6. Se la dimensione della mappa> dimensione fissa, DELET l'ultimo elemento O (1).

Un'altra soluzione:

1. Usa tabella hash

2. Ordina è O (n LGN).

3. Se un elemento viene visitato, cercatela nel talbe con O (1).

4. Se è stato nella tabella, aggiornare il tempo O (1). Ordinare la tabella O (n lg n).

5. In caso contrario, inserirlo nella tabella e poi sorta. O (n lg n)

6. Se dimensione della tabella> dimensione fissa, DELET l'ultimo elemento O (1).

sono soluzioni là migliori? Su) ?

Answer 1

Se si utilizza una lista doppiamente concatenata, si otterrà O (1) inserimento (di ricerca dopo), O (1) la cancellazione, O (n) la ricerca.

Supponendo che si inseriscono nuovi elementi nella parte anteriore:

Se la cache non è pieno, basta aggiungere alla parte anteriore (O (1)).

Se è necessario aggiornare una voce, trovano (O (n)), rimuoverlo dalla lista collegata (O (1)), quindi aggiungere alla parte anteriore (O (1)).

Se è necessario eliminare il più vecchio per inserire un nuovo elemento, eliminare l'elemento terminale (O (1)), e inserire in avanti (O (1)) [nota: è necessario cercare l'elenco prima di questo caso per vedere se l'articolo non è già nella cache, in modo da O (n)].

una lista collegata può anche dare allo stesso tempo, dal momento che la ricerca vi lascerà all'ultimo elemento.

Answer 2

Python LRU cache di ha O (1) inserimento, la cancellazione e la ricerca. Il suo design utilizza una lista doppiamente concatenata di voci (organizzato più antica alla più recente) e una tabella di hash per individuare un particolare link.

Ecco una versione semplificata (ma veloce) in meno di 40 linee di Python molto di base. Non dovrebbe essere difficile da tradurre soluzione di Python in C ++:

class LRU_Cache(object):

    def __init__(self, original_function, maxsize=1000):
        self.original_function = original_function
        self.maxsize = maxsize
        self.mapping = {}

        PREV, NEXT, KEY, VALUE = 0, 1, 2, 3
        self.head = [None, None, None, None]        # oldest
        self.tail = [self.head, None, None, None]   # newest
        self.head[NEXT] = self.tail

    def __call__(self, *key):
        PREV, NEXT, KEY, VALUE = 0, 1, 2, 3
        mapping, head, tail = self.mapping, self.head, self.tail
        sentinel = object()

        link = mapping.get(key, sentinel)
        if link is sentinel:
            value = self.original_function(*key)
            if len(mapping) >= self.maxsize:
                oldest = head[NEXT]
                next_oldest = oldest[NEXT]
                head[NEXT] = next_oldest
                next_oldest[PREV] = head
                del mapping[oldest[KEY]]
            last = tail[PREV]
            link = [last, tail, key, value]
            mapping[key] = last[NEXT] = tail[PREV] = link
        else:
            link_prev, link_next, key, value = link
            link_prev[NEXT] = link_next
            link_next[PREV] = link_prev
            last = tail[PREV]
            last[NEXT] = tail[PREV] = link
            link[PREV] = last
            link[NEXT] = tail
        return value

if __name__ == '__main__':
    p = LRU_Cache(ord, maxsize=3)
    for c in 'abcdecaeaa':
        print(c, p(c))

Answer 3

Si può farlo in Java con la java.util.LinkedHashSet . Si tratta di una tabella hash accoppiato con una lista collegata che conserva l'ordine in cui sono stati inseriti gli articoli. Si dovrebbe ottenere (expected) costante di tempo look-up, inserimenti e rimozioni se la dispersione chiave funziona bene.

Si può anche voler guardare WeakHashMap che implementa un meccanismo automatico dove elementi possono essere garbage collection.

Answer 4

Utilizzare due raccolte che condividono gli stessi dati. Avere una tabella hash e una sola lista. Utilizzare tabella hash per verificare se esiste oggetto, e di trovare nella lista (valore della mappa di hash è iteratore di lista). Utilizzare la lista per mantenere l'ordine tra gli elementi. Sincronizzare due collezioni (quando si rimuove elemento dall'elenco, rimuovere elemento corrispondente dal hashtable). Lista iteratore deve essere tale da non cambia quando si riposizionare l'elemento all'interno dell'elenco.

Modifica: std :: iteratore di lista è valida in tutta l'aggiunta e l'eliminazione di elementi, a condizione che l'elemento molto iteratore fa riferimento alla non viene rimosso. Vedere ultime righe nella sezione Capacità e allocazione in Wikipedia.

Answer 5

Non hai veramente per ordinare il contenitore. Basta aggiungere gli elementi alla mappa o vettore, e andare su di esso in modo lineare per trovare un prodotto necessario (o la voce più vecchia).

Allora sarà O(n).

Answer 6

Date un'occhiata al boost :: multi_index . Uno degli esempi che si vede è un MRU List .