¿Cuál es la colección más rápida en C# para implementar una cola de priorización?

Question

Necesito implementar una cola FIFO para los mensajes en un servidor de juego, por lo que necesita hacerlo lo más rápido posible. Habrá una cola para cada usuario.

La cola tendrá un tamaño de maxiumem (digamos 2000). El tamaño no cambiará durante el tiempo de ejecución.

Necesito priorizar los mensajes SÓLO si la cola alcanza su tamaño máximo trabajando hacia atrás y eliminando un mensaje de prioridad más baja (si existe) antes de agregar el nuevo mensaje.

Una prioridad es un int con posibles valores de 1, 3, 5, 7, 10.

No pueden ser mensajes múltiples con la misma prioridad.

Un mensaje no puede cambiar su prioridad una vez asignado.

La aplicación es asincrónica, por lo que debe bloquearse el acceso a la cola.

Actualmente lo estoy implementando usando LinkedList como el almacenamiento subyacente, pero me preocupa que la búsqueda y eliminación de nodos lo mantendrá bloqueado por mucho tiempo.

Heres el código básico que tienen en la actualidad

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

Así tenemos las siguientes propiedades:

• prioridades están bien definidas y delimitadas
• necesita ser seguro para subprocesos
tamaño
• cola se fija a 2000 mensajes , donde más allá de este encola colocar el elemento más bajo

Es muy fácil de escribir una cola de prioridad que soporta todas estas propiedades:

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; } 
    } 
} 

Soporta Enqueue/Quitar de la cola en O (1) el tiempo, los métodos TryEnqueue y TryDequeue están garantizados para ser thread-safe, y el el tamaño de la colección nunca excederá el tamaño máximo que especifique en el constructor.

Las cerraduras de TryEnqueue y TryDequeue son bastante grano fino, por lo que podría tener un impacto en el rendimiento cada vez que necesite mayor-cargar o descargar datos. Si necesita cargar la cola con muchos datos por adelantado, bloquee el SyncRoot y llame a los métodos no seguros según sea necesario.

Answer 2

Asumo que puede tener prioridades duplicadas.

No hay ningún contenedor dentro de .NET que permita claves duplicadas similares a una multimapa en C++. Puede hacer esto de diferentes formas, ya sea con una SortedList que tenga una matriz de valores para cada clave de prioridad (y obtenga el primer elemento de esa matriz como valor de retorno); SortedList es un árbol equilibrado debajo (IIRC) y debería proporcionarle un buen rendimiento de inserción y recuperación.

Answer 3

Una aplicación de cola de prioridad para C#/vetados. NET se puede encontrar en el C5 Generic Collection Library en la clase C5.IntervalHeap<T>.

Answer 4

Si tiene un número fijo de prioridades, solo crearía una clase compuesta Queue que envuelva dos o más colas privadas.

Un ejemplo drásticamente simplificado se muestra a continuación, aunque podría ampliarlo agregando una Enumeración de prioridad y un interruptor para determinar dónde Enquear un elemento.

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

Realmente depende de la distribución de las longitudes de las colas que probablemente verá. 2000 es el máximo, pero ¿cuál es el promedio y cómo se ve la distribución? Si N es típicamente pequeño, una simple lista <> con una búsqueda de fuerza bruta para el próximo más bajo puede ser una buena elección.

¿Ha perfilado su aplicación a sabe esto es un cuello de botella?

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