.NET 4.0中的并发优先级队列

Question

似乎.NET 4.0中有很多与并发相关的改进可能依赖于并发优先级队列.框架内是否有可靠的优先级队列实现可供重用？

Answer 1

msdn中有一个实现作为".NET Framework并行编程示例"的一部分.请参见ParallelExtensionsExtras.

直接链接到文件ConcurrentPriorityQueue.cs的源代码

Answer 2

你可能需要自己动手.一种相对简单的方法是拥有一组常规队列,优先级降低.

基本上,您将插入队列以获得适当的优先级.然后,在消费者方面,您将从列表中下拉,从最高优先级到最低优先级,检查队列是否为非空,如果是,则使用条目.

Answer 3

也许您可以使用我自己的PriorityQueue实现。它比通常的push / pop / peek实现了更多功能，这些功能在我发现有此需要时便实现。它还具有并发锁。

对代码的注释非常感激:)

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

检查.NET Framework 4 中的线程安全集合及其性能特征，但据我所知，没有现成的优先级队列。所有新的线程安全集合都不会维持顺序，但您可以在它们之上创建自己的集合。检查@Steven 的方式。