Cola de prioridad concurrente en .NET 4.0

Question

Parece que hay muchas mejoras en .NET 4.0 relacionadas con la concurrencia que pueden depender de colas de prioridad concurrentes. ¿Hay una implementación de cola de prioridad decente dentro del marco disponible para su reutilización?

Answer 1

Compruebe Thread-safe Collections in .NET Framework 4 and Their Performance Characteristics pero AFAIK no hay ninguna cola de prioridad lista para usar. Todas las nuevas colecciones seguras para hilos no mantienen el orden, pero puedes hacer las tuyas encima de ellas. Comprueba el camino de Steven.

Answer 2

Es posible que deba hacer las suyas propias. Una forma relativamente fácil sería tener una serie de colas regulares, con prioridad decreciente.

Básicamente, debe insertar en la cola la prioridad adecuada. Luego, en el lado del consumidor, pasaría a la lista, de mayor a menor prioridad, verificando si la cola no está vacía y consumiendo una entrada si es así.

Answer 3

Tal vez pueda usar mi propia implementación de PriorityQueue. Implementa mucho más que las funciones habituales push/pop/peek, que implementé cada vez que lo necesitaba. También tiene bloqueos para concurrencia.

Comentarios al código es muy apreciada :)

public class PriorityQueue<T> where T : class 
{ 
    private readonly object lockObject = new object(); 
    private readonly SortedList<int, Queue<T>> list = new SortedList<int, Queue<T>>(); 

    public int Count 
    { 
     get 
     { 
      lock (this.lockObject) 
      { 
       return list.Sum(keyValuePair => keyValuePair.Value.Count); 
      } 
     } 
    } 

    public void Push(int priority, T item) 
    { 
     lock (this.lockObject) 
     { 
      if (!this.list.ContainsKey(priority)) 
       this.list.Add(priority, new Queue<T>()); 
      this.list[priority].Enqueue(item); 
     } 
    } 
    public T Pop() 
    { 
     lock (this.lockObject) 
     { 
      if (this.list.Count > 0) 
      { 
       T obj = this.list.First().Value.Dequeue(); 
       if (this.list.First().Value.Count == 0) 
        this.list.Remove(this.list.First().Key); 
       return obj; 
      } 
     } 
     return null; 
    } 
    public T PopPriority(int priority) 
    { 
     lock (this.lockObject) 
     { 
      if (this.list.ContainsKey(priority)) 
      { 
       T obj = this.list[priority].Dequeue(); 
       if (this.list[priority].Count == 0) 
        this.list.Remove(priority); 
       return obj; 
      } 
     } 
     return null; 
    } 
    public IEnumerable<T> PopAllPriority(int priority) 
    { 
     List<T> ret = new List<T>(); 
     lock(this.lockObject) 
     { 
      if (this.list.ContainsKey(priority)) 
      { 
       while(this.list.ContainsKey(priority) && this.list[priority].Count > 0) 
        ret.Add(PopPriority(priority)); 
       return ret; 
      } 
     } 
     return ret; 
    } 
    public T Peek() 
    { 
     lock (this.lockObject) 
     { 
      if (this.list.Count > 0) 
       return this.list.First().Value.Peek(); 
     } 
     return null; 
    } 
    public IEnumerable<T> PeekAll() 
    { 
     List<T> ret = new List<T>(); 
     lock (this.lockObject) 
     { 
      foreach (KeyValuePair<int, Queue<T>> keyValuePair in list) 
       ret.AddRange(keyValuePair.Value.AsEnumerable()); 
     } 
     return ret; 
    } 
    public IEnumerable<T> PopAll() 
    { 
     List<T> ret = new List<T>(); 
     lock (this.lockObject) 
     { 
      while (this.list.Count > 0) 
       ret.Add(Pop()); 
     } 
     return ret; 
    } 
} 

Answer 4

Hay una aplicación como parte de "Las muestras para programación paralela con .NET Framework" en MSDN. Ver ParallelExtensionsExtras.

Enlace directo al código fuente para el archivo ConcurrentPriorityQueue.cs

Answer 5

Opciones:

1) Si la cola no es nunca va a ser grande, utilice una pila y bloquee toda la estructura para cada inserción y eliminación.

2) Si la cola va a llegar a ser grandes, se puede utilizar un algoritmo de esta manera:

http://www.research.ibm.com/people/m/michael/ipl-1996.pdf

Este algoritmo permite múltiples hilos de estar trabajando con la estructura del montón al mismo tiempo sin correr el riesgo de corrupción o los puntos muertos apoyando el bloqueo fino de solo partes del árbol a la vez. Tendría que comparar para ver si la sobrecarga de las operaciones adicionales de bloqueo y desbloqueo costaba más que la contención por bloquear todo el montón.

3) Si intenta evitar bloqueos por completo, otro algoritmo, mencionado en el enlace anterior, sugiere utilizar una cola FIFO de solicitudes (fácilmente implementable sin bloqueos), y un hilo separado que es lo único que toca el montón. Tendría que medir para ver cómo la sobrecarga de cambiar el foco entre los hilos utilizando objetos de sincronización en comparación con la sobrecarga del bloqueo plano directo.

Antes de empezar, valdría la pena ver cuán malo es el impacto en una implementación directa mediante el bloqueo. Puede que no sea la implementación más eficiente, pero si aún realiza órdenes de magnitud más rápido de lo que nunca necesitará, entonces la facilidad de mantenimiento (es decir, cualquiera, incluyéndose a sí mismo un año puede ahora, ser capaz de simplemente mirar el código y entender lo que hace) puede superar la pequeña fracción del tiempo de CPU ocupado ocupado en el mecanismo de puesta en cola.

Esperanza esto ayuda :-)

Answer 6

Dado que todas las respuestas actuales son fuera de fecha o no ofrecen una solución viable, hay una implementation on MSDN que es utilizable. Tenga en cuenta que las prioridades más bajas se procesan primero en esta implementación.

Answer 7

Recientemente, estaba creando una máquina de estado en la que necesitaba eventos con marca de tiempo. En lugar de un simple tic del reloj, necesitaba eventos temporizados con sus propios ID para poder distinguir un evento de otro.

Investigar este problema me llevó a la idea de utilizar una cola de prioridad. Podría poner en cola los eventos programados junto con su información en cualquier orden; la cola de prioridad se encargaría de ordenar los eventos adecuadamente. Un temporizador verificará periódicamente la cola de prioridad para ver si es hora de que el evento en la cabecera de la cola se dispare. Si es así, elimina la cola del evento e invoca al delegado asociado a él. Este enfoque era exactamente lo que estaba buscando.

busca aquí en CodeProject

https://www.codeproject.com/Articles/13295/A-Priority-Queue-in-C

me encontré con que una cola de prioridad [^] clase ya había sido escrito. Sin embargo, se me ocurrió que podía escribir fácilmente el mío usando mi viejo amigo, la lista de omisiones. Esto tendría la ventaja de que la operación de descarte solo tomaría O (1) vez, mientras que la operación en cola seguiría siendo log (n) en promedio. Pensé que el uso de listas de omisiones de este modo era lo suficientemente novedoso como para merecer su propio artículo.

Así que aquí está. Espero lo encuentres interesante.

Answer 8

Bueno, pasaron 7 años, pero para la posteridad, me gustaría responder con mi implementación.

Documentation: Optionally awaitable simple to use Concurrent Priority Queue

Sourcecodes: github

nuget package

• Lock-Libre,
• altamente concurrente,
• genérico en el tipo de elemento almacenado,
• genérico en el tipo de prioridad, pero limitado a priori lazos representados por enumeración .net, prioridad estricta de tipos,
• define explícitamente el orden de prioridades durante la construcción descendente,
• capacidad de detectar elementos cuentan y por elementos de nivel de prioridad contar,
• capacidad de quitar de la cola - orden descendente de prioridades,
• capacidad de anular dequeue nivel de prioridad,
• potencialmente awaitable,
• potencialmente prioridad basada awaitable,