Qual è la raccolta più veloce in C# per implementare una coda di priorità?

Question

Ho bisogno di implementare una coda FIFO per i messaggi su un server di gioco, quindi deve essere il più veloce possibile. Ci sarà una coda per ogni utente.

La coda avrà una dimensione massima (diciamo 2000). La dimensione non cambierà durante il runtime.

Ho bisogno di dare la priorità ai messaggi SOLO se la coda raggiunge la sua dimensione massima lavorando all'indietro e rimuovendo un messaggio con priorità più bassa (se ne esiste uno) prima di aggiungere il nuovo messaggio.

Una priorità è un int con possibili valori di 1, 3, 5, 7, 10.

Ci possono essere più messaggi con la stessa priorità.

Un messaggio non può cambiare la sua priorità una volta assegnato.

L'applicazione è asincrona pertanto è necessario bloccare l'accesso alla coda.

Attualmente lo sto implementando utilizzando una LinkedList come memoria sottostante, ma temo che la ricerca e la rimozione dei nodi la mantengano bloccata troppo a lungo.

Heres il codice di base che ho in questo momento:

public class ActionQueue 
{ 
    private LinkedList<ClientAction> _actions = new LinkedList<ClientAction>(); 
    private int _maxSize; 

    /// <summary> 
    /// Initializes a new instance of the ActionQueue class. 
    /// </summary> 
    public ActionQueue(int maxSize) 
    { 
     _maxSize = maxSize; 
    } 

    public int Count 
    { 
     get { return _actions.Count; }    
    } 

    public void Enqueue(ClientAction action) 
    { 
     lock (_actions) 
     { 
      if (Count < _maxSize) 
       _actions.AddLast(action); 
      else 
      { 
       LinkedListNode<ClientAction> node = _actions.Last; 
       while (node != null) 
       { 
        if (node.Value.Priority < action.Priority) 
        { 
         _actions.Remove(node); 
         _actions.AddLast(action); 
         break; 
        } 

        node = node.Previous; 

       }      
      } 
     } 
    } 

    public ClientAction Dequeue() 
    { 
     ClientAction action = null; 

     lock (_actions) 
     { 
      action = _actions.First.Value; 
      _actions.RemoveFirst(); 
     } 

     return action; 
    } 

} 

Answer 1

Così abbiamo le seguenti proprietà:

• priorità sono ben definita e delimitata
• deve essere thread-safe
dimensioni
• coda è fissata a 2000 messaggi , dove gli oggetti oltre questo lasciano l'articolo più basso

È molto facile scrivere una coda di priorità che supporta tutte queste proprietà:

public class BoundedPriorityQueue<T> 
{ 
    private object locker; 
    private int maxSize; 
    private int count; 
    private LinkedList<T>[] Buckets; 

    public BoundedPriorityQueue(int buckets, int maxSize) 
    { 
     this.locker = new object(); 
     this.maxSize = maxSize; 
     this.count = 0; 
     this.Buckets = new LinkedList<T>[buckets]; 
     for (int i = 0; i < Buckets.Length; i++) 
     { 
      this.Buckets[i] = new LinkedList<T>(); 
     } 
    } 

    public bool TryUnsafeEnqueue(T item, int priority) 
    { 
     if (priority < 0 || priority >= Buckets.Length) 
      throw new IndexOutOfRangeException("priority"); 

     Buckets[priority].AddLast(item); 
     count++; 

     if (count > maxSize) 
     { 
      UnsafeDiscardLowestItem(); 
      Debug.Assert(count <= maxSize, "Collection Count should be less than or equal to MaxSize"); 
     } 

     return true; // always succeeds 
    } 

    public bool TryUnsafeDequeue(out T res) 
    { 
     LinkedList<T> bucket = Buckets.FirstOrDefault(x => x.Count > 0); 
     if (bucket != null) 
     { 
      res = bucket.First.Value; 
      bucket.RemoveFirst(); 
      count--; 
      return true; // found item, succeeds 
     } 
     res = default(T); 
     return false; // didn't find an item, fail 
    } 

    private void UnsafeDiscardLowestItem() 
    { 
     LinkedList<T> bucket = Buckets.Reverse().FirstOrDefault(x => x.Count > 0); 
     if (bucket != null) 
     { 
      bucket.RemoveLast(); 
      count--; 
     } 
    } 

    public bool TryEnqueue(T item, int priority) 
    { 
     lock (locker) 
     { 
      return TryUnsafeEnqueue(item, priority); 
     } 
    } 

    public bool TryDequeue(out T res) 
    { 
     lock (locker) 
     { 
      return TryUnsafeDequeue(out res); 
     } 
    } 

    public int Count 
    { 
     get { lock (locker) { return count; } } 
    } 

    public int MaxSize 
    { 
     get { return maxSize; } 
    } 

    public object SyncRoot 
    { 
     get { return locker; } 
    } 
} 

Supporta Enqueue/rimozione in O (1) tempo, i metodi TryEnqueue e TryDequeue sono garantiti per essere thread-safe, e la dimensione della raccolta non supererà mai la dimensione massima specificata nel costruttore.

I blocchi su TryEnqueue e TryDequeue sono piuttosto granulosi, quindi è possibile che si verifichi un problema di prestazioni ogni volta che è necessario caricare o scaricare in blocco i dati. Se è necessario caricare la coda con un sacco di dati in primo piano, quindi bloccare il SyncRoot e chiamare i metodi non sicuri, se necessario.

Answer 2

sto supponendo che si può avere priorità duplicati.

Non c'è alcun contenitore in .NET che consente chiavi duplicate simili a un multimap C++. Puoi farlo in diversi modi, con una SortedList che ha una matrice di valori per ogni chiave di priorità (e prendi il primo elemento da quella matrice come valore di ritorno); the SortedList è un albero bilanciato sotto (IIRC) e dovrebbe fornire buone prestazioni di inserimento e recupero.

Answer 3

Un'implementazione controllata della coda di priorità per C# /. NET può essere trovata nel C5 Generic Collection Library nella classe C5.IntervalHeap<T>.

Answer 4

Se si dispone di un numero fisso di priorità, creerei una classe di coda composita che avvolga due o più code private.

Segue un esempio drasticamente semplificato, anche se è possibile espandere su di esso aggiungendo un enum di priorità e un interruttore per determinare dove accodare un articolo.

class PriorityQueue { 

    private readonly Queue normalQueue = new Queue(); 
    private readonly Queue urgentQueue = new Queue(); 

    public object Dequeue() { 
     if (urgentQueue.Count > 0) { return urgentQueue.Dequeue(); } 
     if (normalQueue.Count > 0) { return normalQueue.Dequeue(); } 
     return null; 
    } 

    public void Enqueue(object item, bool urgent) { 
     if (urgent) { urgentQueue.Enqueue(item); } 
     else { normalQueue.Enqueue(item); } 
    } 
} 

Answer 5

Dipende molto dalla distribuzione delle lunghezze di coda che è probabile che si vedano. Il 2000 è il massimo ma qual è la media e come si presenta la distribuzione? Se N è in genere piccolo, una semplice lista <> con una ricerca forza bruta per il successivo più basso potrebbe essere una buona scelta.

Hai profilato la tua domanda a sa questo è un collo di bottiglia?

  "Never underestimate the power of a smart compiler 
      and a smart CPU with registers and on-chip memory 
      to run dumb algorithms really fast"