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

wbgh16ku  于 2023-07-01  发布在  .NET
关注(0)|答案(9)|浏览(173)

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

46qrfjad

46qrfjad1#

msdn上的“使用. NETFramework进行并行编程的示例”中有一个实现。参见ParallelExtensionsExtras
直接链接到文件ConcurrentPriorityQueue.cs的源代码

ffvjumwh

ffvjumwh2#

你可能需要自己卷。一个相对简单的方法是有一个规则队列的数组,优先级递减。
基本上,您将插入到队列中以获得适当的优先级。然后,在消费者端,您将沿着列表,从最高到最低优先级,检查队列是否为非空,如果是,则消费一个条目。

zbwhf8kr

zbwhf8kr3#

也许你可以使用我自己的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;
    }
}
sdnqo3pr

sdnqo3pr4#

7年过去了,但为了子孙后代,我想用我的实现来回答。
Documentation: Optionally awaitable simple to use Concurrent Priority Queue
Sourcecodes: github
nuget package

  • 无锁
  • 高度并发,
  • 在存储项类型中是通用的,
  • 在优先级类型中是泛型的,但被限制为.net enum表示的优先级,强类型优先级,
  • 在构造期间明确定义的优先级降序,
  • 检测项目计数和每个优先级项目计数的能力,
  • 出队的能力-优先级的降序,
  • 超控出队优先级的能力,
  • 潜在地可等待,
  • 潜在地基于优先级的等待,
k2fxgqgv

k2fxgqgv5#

由于目前所有的答案都过时了,或者没有提供可行的解决方案,因此有一个可用的implementation on MSDN。请注意,在此实现中,优先级较低的优先级首先得到处理。

ki1q1bka

ki1q1bka6#

检查Thread-safe Collections in .NET Framework 4 and Their Performance Characteristics,但AFAIK没有准备好使用优先级队列。所有新的线程安全集合都不维护顺序,但您可以在它们之上创建自己的集合。检查@Steven的方式。

l7wslrjt

l7wslrjt7#

选项:
1)如果你的队列永远不会变大,那么就使用堆,并在每次插入和删除时锁定整个结构。
2)如果你的队列变得很大,你可以使用这样的算法:
http://www.research.ibm.com/people/m/michael/ipl-1996.pdf
该算法允许多个线程同时处理堆结构,而不会有损坏或死锁的风险,因为它支持同时对树的某些部分进行细粒度锁定。您必须进行基准测试,以查看额外的锁定和解锁操作的开销是否比锁定整个堆的争用开销更大。
3)如果你的目标是完全避免锁,另一个算法,在上面的链接中提到,建议使用一个FIFO请求队列(很容易实现,没有锁),和一个单独的线程,这是唯一接触堆的东西。您必须测量使用同步对象在线程之间切换焦点的开销与普通直接锁定的开销相比如何。
在您开始之前,有必要了解一下使用锁定的直接实现的效果有多糟糕。它可能不是最有效的实现,但如果它的执行速度仍然比您所需要的快几个数量级,那么维护的容易性(也就是说,任何人,包括您自己,现在都可以简单地查看代码并理解它的功能)可能超过在排队机制忙碌的CPU时间的一小部分。
希望这有帮助:-)

hfsqlsce

hfsqlsce8#

最近,我正在创建一个状态机,其中我需要时间戳事件。我需要的不仅仅是一个简单的时钟滴答声,而是带有自己ID的定时事件,以便能够区分不同的事件。
对这个问题的研究使我想到了使用优先级队列的想法。我可以将定时事件沿着它们的信息以任意顺序排队;优先级队列将负责正确地对事件进行排序。定时器将周期性地检查优先级队列,以查看是否到了触发队列头部的事件的时间。如果是,它将事件出队并调用与之关联的委托。这种方法正是我所寻找的。
在CodeProject上搜索
https://www.codeproject.com/Articles/13295/A-Priority-Queue-in-C
我发现已经写了一个优先级队列[^]类。然而,我突然想到,我可以很容易地写我自己的使用我的老朋友,跳读列表。这样做的好处是,出队操作只需要O(1)时间,而入队操作的平均时间仍然是log(n)。我认为以这种方式使用跳读列表是足够新颖的,它值得自己的文章。
这就是了我希望你会觉得有趣。

5ssjco0h

5ssjco0h9#

我发现了一个很好的并发优先级队列here的例子。希望对你有一点帮助。

var priorityQueue = new ConcurrentPriorityQueue<TKey, TValue>();

此队列上下文中的TKey可以是int值或实现IComparable的任何其他对象。
要使用这样的队列,您可以执行以下操作:

var priorityQueue = new ConcurrentPriorityQueue<int, object>(); 

// Add elements
priorityQueue.Enqueue(2, elementP2); 
priorityQueue.Enqueue(1, elementP1);

// Here you will receive elementP1
bool result = priorityQueue.TryDequeue(out KeyValuePair<int, object> element);

相关问题