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

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

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

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

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

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

也许你可以使用我自己的PriorityQueue实现。 它实现了比通常的push / pop / peek更多的function,每当我发现它需要时我实现的function。 它还具有并发锁。

对代码的评论非常感谢:)

public class PriorityQueue where T : class { private readonly object lockObject = new object(); private readonly SortedList> list = new SortedList>(); 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()); 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 PopAllPriority(int priority) { List ret = new List(); 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 PeekAll() { List ret = new List(); lock (this.lockObject) { foreach (KeyValuePair> keyValuePair in list) ret.AddRange(keyValuePair.Value.AsEnumerable()); } return ret; } public IEnumerable PopAll() { List ret = new List(); lock (this.lockObject) { while (this.list.Count > 0) ret.Add(Pop()); } return ret; } } 

由于所有当前的答案都已过时或者没有提供可行的解决方案,因此MSDN上的实现可以使用。 请注意,在此实现中首先处理较低优先级。

检查.NET Framework 4中的线程安全集合及其性能特征,但AFAIK没有准备好使用优先级队列。 所有新的线程安全集合都不会维护顺序,但您可以自己创建它们。 检查@ Steven的方式。

选项:

1)如果您的队列不会变大,请使用堆并锁定整个结构以进行每次插入和删除。

2)如果你的队列变得很大,你可以使用这样的算法:

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

此算法允许多个线程同时使用堆结构,而不会立即支持对树的部分细粒度锁定,从而存在损坏或死锁的风险。 您必须进行基准测试,以查看额外锁定和解锁操作的开销是否比锁定整个堆的争用成本高。

3)如果您的目标是完全避免锁定,上面链接中提到的另一种算法建议使用FIFO队列请求(很容易实现没有锁定),以及一个单独的线程,它是唯一触及堆的东西。 您必须测量以查看使用同步对象在线程之间切换焦点的开销与简单直接锁定的开销相比如何。

在你开始之前,有必要看一下使用锁定直接实现的命中有多糟糕。 它可能不是最有效的实现,但如果它仍然比你需要的速度快几个数量级,那么易于维护(也就是说,任何人,包括你自己一年都可以,只需查看代码并且了解它的作用)可能超过在排队机制中忙碌的CPU时间的一小部分。

希望这可以帮助 :-)

最近,我正在创建一个状态机,我需要时间戳事件。 我不需要只是一个简单的时钟滴答,而是需要带有自己ID的定时事件,这样我就能将一个事件与另一个事件区分开来。

研究这个问题让我想到了使用优先级队列。 我可以按时间顺序排列定时事件及其信息; 优先级队列将负责正确排序事件。 计时器会定期检查优先级队列,以查看是否需要时间点击队列头部的事件。 如果是这样,它会对事件进行排队并调用与之关联的委托。 这种方法正是我想要的。

在CodeProject搜索

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

我发现已经编写了一个优先级队列[^]类。 然而,在我看来,我可以使用我的老朋友,跳过列表轻松编写自己的内容。 这将具有以下优点:出队操作仅花费O(1)时间,而入队操作仍然是平均log(n)。 我认为以这种方式使用跳过列表是足够新颖的,它值得自己的文章。

所以在这里。 我希望你觉得它很有趣。

好吧,7年过去了,但是对于子孙后代,我想回答一下我的实施情况。

文档:可选择等待简单易用的并发优先级队列

源代码:github

nuget包

  • 无锁的,
  • 高度并发,
  • 存储项类型中的通用,
  • 优先级类型的通用,但受限于.net枚举表示的优先级,强类型优先级,
  • 明确定义施工期间优先顺序的降序,
  • 能够检测项目数和每个优先级项目数,
  • 出列的能力 – 优先顺序递减,
  • 能够覆盖出列优先级,
  • 可能是等待的,
  • 潜在的优先权等待,