Soluzione efficiente per gli aggiornamenti del dizionario

Question

Soluzione efficiente per gli aggiornamenti del dizionario

#1 da (9 voti)
#2 da (4 voti)

3

Iniziamo con il problema:

C'è un grande dizionario X che contiene coppie {chiave, valore}, cioè:

X = [{100, 10}, {101, 0}, {103, 0}, {106, 2}, {110, 1}]

Ogni t secondi, X deve essere aggiornato con i valori del sottotitolo U e 0 impostati su ciascun valore per una chiave che non è presente nella nuova U aggiornata, ma che era nell'aggiornamento precedente.

I requisiti più importanti sono che un aggiornamento deve essere eseguito in modo tale che sia stato eseguito il numero minimo di operazioni di aggiornamento di ciascuna coppia di chiavi {valore,} nel dizionario X, cioè.

X aggiornato da U dove

U = [{100, 10}, {102, 5}, {103, 0}, {105, 1}, {110, 0}]

diventerebbe:

X = [{100, 10}, {101, 0}, {102, 5}, {103, 0}, {105, 1}, {106, 2}, {110, 0}]

ma solo le seguenti coppie sono state aggiornate / aggiunte in X:

{102, 5}
{105, 1}
{110, 0}

Per rendere le cose un po 'più interessanti, ci sono alcuni vincoli:

è molto costoso iterare sul dizionario X. Supponiamo che X sia molto grande.
è molto costoso effettuare un aggiornamento alla coppia {chiave, valore}, quindi l'operazione è di minimizzare questo costo.

Quindi questo era il problema dichiarato. Ecco la mia soluzione:

La prima idea che avevo era di salvare il dizionario U dopo aver aggiornato X. Al prossimo aggiornamento prendo ogni tasto da Uprev e lo metto a 0 in X.

foreach (var pair in Uprev)
{
    X[pair.Key] = 0;
}

Dopo che questo è stato fatto, vorrei fare un ciclo per impostare nuovi valori per le chiavi presenti nel nuovo dizionario U:

foreach (var pair in U)
{
    if (X.ContainsKey(pair.Key))
       X[pair.Key] = pair.Value;
    else
       X.Add(pair.Key, pair.Value);
}

Quindi ... la domanda: c'è una soluzione migliore per il problema che ho descritto sopra? È possibile gestire meglio gli aggiornamenti? Tutte le idee sono benvenute, quindi sentiti libero di postare qualsiasi cosa ti venga in mente.

Grazie per il contributo

c# dictionary

posta Macin 18.12.2013 - 12:39

fonte

2 risposte

Leggi altre domande sui tag c# dictionary

Ha senso avere un'interfaccia a scheda singola? Come evitare un downcast eccessivo quando si utilizza l'ereditarietà

score 9 · Answer 1

Invece di

foreach (var pair in U)
{
    if (X.ContainsKey(pair.Key))
       X[pair.Key] = pair.Value;
    else
       X.Add(pair.Key, pair.Value);
}

utilizzo

foreach (var pair in U)
{
     X[pair.Key] = pair.Value;
}

(l'operatore indice [] funziona come Add quando la chiave non esiste finora). Questo ti evita una ricerca inutile del dizionario. Oltre a questo, non mi aspetto grandi miglioramenti, dato che è ovvio che devi visitare ogni elemento di U una volta e il tuo algoritmo lo fa solo due volte, non di più.

score 4 · Answer 2

Puoi renderlo più efficiente sviluppando una struttura dati specializzata. Sia X 'una coppia (D, S) dove D è un dizionario e S è un insieme. Corrisponde al dizionario X del tuo esempio con le seguenti sostituzioni:

non ci sono tasti vincolati a 0 in D
se una chiave è vincolata in D allora X 'si comporta come se fosse X e tale associazione fosse anche in X
se una chiave non è vincolata in D ma in S, X 'si comporta come se fosse X e quella chiave era vincolata a 0 in X.

È possibile definire le operazioni di ricerca e aggiornamento come.

 lookup(key):
   if key is bound in D then D[key] elseif key is in S then 0 else Not_found

 update(U):
   set D to U
   add all keys bound in U to S

Se U è abbastanza piccolo, questo migliorerà le prestazioni: se il tuo dizionario X è implementato con una tabella hash e cresce molto grande, hai molte collisioni hash e il tempo di ricerca si comporta come O (N). Con X 'la ricerca della chiave è O (size (U)) + O (log N) che diventa O (log N) se la dimensione di U è limitata.