Come implementare un QueueDictionary, una combinazione di coda e dizionario in C#?

Question

Fondamentalmente la struttura dati che vorrei rispecchierebbe un MSMQ ma sarebbe in memoria, perché viene utilizzata in un unico processo. Mediante il mirroring di MSMQ, intendo che si accoderebbe gli oggetti, quindi è possibile rimuovere o deselezionare gli oggetti o recuperarli utilizzando una chiave. Ecco il primo tentativo. Il mio problema principale con questo tentativo è che Get by id verrebbe usato frequentemente e quindi la coda finirebbe per avere un sacco di oggetti "morti".

public class QueueDictionary<TKey, TValue> 
{ 
    private readonly Queue _queue = new Queue(); 
    private readonly Dictionary<TKey, TValue> _dictionary = new Dictionary<TKey, TValue>(); 
    private readonly object _syncRoot = new object(); 

    public TValue Dequeue() 
    { 
     lock (_syncRoot) 
     { 
      TKey key = (TKey)_queue.Dequeue(); 
      while (!_dictionary.ContainsKey(key)) 
       key = (TKey)_queue.Dequeue(); 
      return _dictionary[key]; 
     } 
    } 

    public TValue Get(TKey key) 
    { 
     lock (_syncRoot) 
     { 
      TValue result = _dictionary[key]; 
      _dictionary.Remove(key); 
      return result; 
     } 
    } 

    public void Enqueue(TKey key, TValue value) 
    { 
     lock (_syncRoot) 
     { 
      _dictionary.Add(key, value); 
      _queue.Enqueue(key); 
     } 
    } 
} 

Answer 1

Piuttosto che utilizzare una coda internamente, è possibile utilizzare una lista collegata. Quindi nel dizionario è possibile memorizzare la chiave e il LinkedListNode. Quindi, quando si rimuove l'elemento dal Dizionario, è possibile scollegare il LinkedListNode dall'elenco collegato. Ovviamente perdi la località della coda, ma ottieni le prestazioni dell'accesso casuale.

Ecco un esempio rapido e sporco, non testato in modo da scusare eventuali errori e nessun controllo degli errori. Per esempio si dovrebbe verificare se la coda è vuota, assicurarsi che un elemento con la stessa chiave non è già presente nel dizionario ecc

public class QueueDictionary<TKey, TValue> 
{ 
    private readonly LinkedList<Tuple<TKey, TValue>> _queue = 
    new LinkedList<Tuple<TKey, TValue>>(); 

    private readonly Dictionary<TKey, LinkedListNode<Tuple<TKey, TValue>>> 
    _dictionary = new Dictionary<TKey, LinkedListNode<Tuple<TKey, TValue>>>(); 

    private readonly object _syncRoot = new object(); 

    public TValue Dequeue() 
    { 
    lock (_syncRoot) 
    { 
     Tuple<TKey, TValue> item = _queue.First(); 
     _queue.RemoveFirst(); 
     _dictionary.Remove(item.Item1); 
     return item.Item2; 
    } 
    } 

    public TValue Dequeue(TKey key) 
    { 
    lock (_syncRoot) 
    { 
     LinkedListNode<Tuple<TKey, TValue>> node = _dictionary[key]; 
     _dictionary.Remove(key); 
     _queue.Remove(node); 
     return node.Value.Item2; 
    } 
    } 

    public void Enqueue(TKey key, TValue value) 
    { 
    lock (_syncRoot) 
    { 
     LinkedListNode<Tuple<TKey, TValue>> node = 
     _queue.AddLast(new Tuple<TKey, TValue>(key, value)); 
     _dictionary.Add(key, node); 
    } 
    } 
} 

Answer 2

Che cosa succede se si è utilizzato un elenco doppio legata ad agire come la coda e che in questo modo puoi avere il pieno controllo di Enqueue, Dequeue e specialmente del metodo Get. Quindi nel metodo Get puoi semplicemente rimuovere la chiave dall'elenco a doppio collegamento.

Answer 3

Bene il tuo oggetto può atto come una coda senza effettivamente utilizzare la classe Coda come sua memoria interna. A seconda del numero di elementi che si intende mantenere, potrebbe essere più semplice mantenere una singola LinkedList (T) invece di archiviare l'elemento sia in LinkedList (T) che in Dizionario (K, V).

Ma in pratica, invece di utilizzare una coda internamente, è possibile utilizzare una LinkedList (T) e aggiungere nuovi elementi alla fine dell'elenco e rimuoverli dalla parte anteriore dell'elenco. Quando è necessario trovarne uno per chiave, è sufficiente scansionare l'elenco per la chiave corrispondente o se il numero di elementi lo rende scarsamente performante, è possibile raddoppiare lo spazio di archiviazione con un dizionario (K, LinkedListNode (T)) e utilizzare il dizionario per le tue ricerche chiave.