Struttura dei dati efficiente per creare un dizionario a dimensione limitata

Question

Struttura dei dati efficiente per creare un dizionario a dimensione limitata

#1 da (1 voti)
#2 da (0 voti)

1

Ho bisogno di una classe che funzioni come un dizionario, ma vincolerà il numero totale di coppie chiave / valore che contiene. Ad esempio, supponiamo che il numero massimo di voci sia 1000 e che la classe già contenga 1000 coppie chiave / valore. Se aggiungo una coppia chiave / valore aggiuntiva, la classe dovrebbe rimuovere la coppia chiave-valore che è stata aggiornata meno di recente.

Ecco la mia attuale implementazione in python:

class SizeLimitedDefaultDict(defaultdict):
    last_changed = []

    def __init__(self, default, max_size, *args, **kwargs):
        max_size = 0
        super(SizeLimitedDict, self).__init__(default, *args, **kwargs)

    def __setitem__(self, key, val):
        if len(self) >= self.max_size:
            remove_oldest_entry()
        super.__setitem__(self, key, val)
        update_newest_entry(key)

    def update_newest_entry(self, key):
        key_index = last_changed.index(key) #will slow it down
        last_changed.insert(0, last_changed.pop(key_index))

Questa chiaramente non è una soluzione praticabile. Tutti i guadagni prestazionali del dizionario sono persi. Sto avendo problemi a trovare una soluzione migliore però. Esiste una struttura dei dati che può facilmente conservare le chiavi aggiornate più di recente.

python data-structures algorithms

posta sinθ 16.03.2015 - 01:15

fonte

2 risposte

Leggi altre domande sui tag python data-structures algorithms

Esperienze con C ++ Async / modello di attore Biblioteca [chiuso] Come ottenere tratti e riempimenti per allineare i limiti dei pixel

score 1 · Answer 1

Dovresti memorizzare le chiavi in due strutture contemporaneamente: un albero (o un heap) e una lista doppiamente collegata. Ogni nodo dell'albero deve includere un puntatore alla voce corrispondente nell'elenco collegato. I valori dovrebbero essere memorizzati con i nodi dell'albero; le voci dell'elenco necessitano solo delle chiavi.

Per cercare un valore, l'elenco collegato non deve essere consultato o modificato.

Per aggiornare una coppia chiave / valore, trovarla nell'albero e sovrascriverne il valore. Quindi utilizzare il puntatore dell'elenco per identificare la voce dell'elenco corrispondente. Scollegare la voce dalla posizione corrente e collegarla alla fine dell'elenco. Questa azione mantiene l'elenco in ordine di aggiornamento.

Per identificare la voce meno recente aggiornata, leggi semplicemente la chiave dal primo elemento nell'elenco collegato.

Penso che tu sappia il resto. Cerca quel nodo nell'albero, sovrascrivi la sua chiave e il suo valore e spostalo nella sua posizione corretta nell'albero, ma senza alterarne il puntatore. Inoltre, sovrascrivi la chiave nella voce della lista e non trascurare di scollegarla e spostarla alla fine dell'elenco.

score 0 · Answer 2

Utilizza una coda per gestire le chiavi per recency:

from collections import deque

class SizeLimitedDefaultDict(defaultdict):
    last_changed = deque()

    def __setitem__(self, key, val):
        if len(self) >= self.max_size:
            del self[last_changed.popleft()]

        super.__setitem__(self, key, val)
        last_changed.append(key)

In parole povere, quando il dizionario diventa "pieno", pagherai per una ricerca del dizionario per ogni inserto.