微软MVP精选 |.NET6 中的 PriorityQueue

李卫涵

微软MVP,来自上海的 .NET 研发工程师,运营公众号 amazingdotnet(www.26663.net)。

2013 年开始接触 .NET,.NET Core出世之后主要关注点在.NET Core 上。喜欢探索.NET 的新特性和一些不一样的实践。

Ibtro

.NET 6 中引入了一个新的集合类型 PriorityQueue,正如它的名字那样,在普通的 Queue基础之上增加了优先级的支持,接下来就一起来看一下怎么使用,以及一些常用的使用场景介绍。

Get Started

来看一个简单的使用示例:

varpriorityQueue = newPriorityQueue< string, int>; priorityQueue.Enqueue( "Alice", 100); priorityQueue.EnqueueRange(Enumerable.Range( 1, 5) .Select(x => ( $"X_ {x}" , 100- x)) );

while(priorityQueue.TryDequeue( outvarelement, outvarpriority)) {Console.WriteLine( $"Element: {element}, {priority}" ); }

输出示例:

可以看到输出的顺序和我们添加的顺序是相反的, PriorityQueue 在 Dequeue 的时候是从优先级最小开始的,值越小优先级越高,优先级越高越优先输出,如果我们希望最大先输出是不是可以呢,答案是肯定的,只是我们需要指定我们自己的优先级比较规则就可以了,可以参考后面的示例。

Scenes

借助带优先级的自动排序,我们可以做一些自动排序的需求的时候可以考虑使用 PriorityQueue

Message Queue

借助 PriorityQueue可以来实现一个优先级消息队列,允许用户在发消息的时候指定一个消息的优先级,在消费的时候就会按优先级

varrandom = newRandom;

varqueue = newPriorityQueue< string, int>; for( vari = 1; i <= 10; i++) {queue.Enqueue( $"Message_ {i}" , random.Next( 10, 100)); }

while(queue.TryDequeue( outvarmessage, out_)) {Console.WriteLine(message);}

在上面的示例里我们默认指定了一个 int 作为 Priority 的类型,并入队了一些消息,但是往往会有很多的消息,可能会出现优先级相同的情况,我们可以使用时间和 int 作为一个联合的 Priority 类型,可以参考下面的示例:

varrandom = newRandom;

varqueue = newPriorityQueue< string, (DateTime time, intpriority)>( newDateTimePriorityComparer);

vartime = DateTime.UtcNow; Thread.Sleep( 1000); for( vark = 0; k < 3; k++) {for( vari = 1; i <= 3; i++) {queue.Enqueue( $"Message_ {i}_ {k}" , (i > 2? time : DateTime.UtcNow, random.Next( 5, 10))); }}

while(queue.TryDequeue( outvarmessage, outvarpriority)) {Console.WriteLine( $" {message}, {priority.priority}, {priority.time}" ); }

输出示例如下:

由上面的结果可以看出来,在 priority 一样的情况下,我们会先处理时间较小的消息,也可以根据自己的需要进行定制排序方式,自定义 Priority 比较逻辑即可,上面的自定义优先级比较代码如下:

internal classDateTimePriorityComparer: IComparer<(DateTime time, intpriority)> {publicintCompare((DateTime time, intpriority) x, (DateTime time, intpriority) y) {var priorityComparison = x.priority.CompareTo(y.priority);if(priorityComparison != 0) returnpriorityComparison; returnx.time.CompareTo(y.time); }}

Rank

在很多做排行榜的应用中也可以使用 PriorityQueue来实现,比如我们来做一个学生成绩的排名

来看下面的示例代码:

varlist = newList<( stringname, intscore)> {( "Mike", 99), ( "Ming", 100), ( "Jane", 96), ( "Yi", 94), ( "Harry", 90), };

varpriorityQueue = newPriorityQueue< string, int>; priorityQueue.EnqueueRange(list);

Console.WriteLine( "--Unordered:"); foreach( varitem inpriorityQueue.UnorderedItems) {Console.WriteLine( $"Name: {item.Element}, score: {item.Priority}" ); }

Console.WriteLine( "--Ordered:"); while(priorityQueue.TryDequeue( outvarname, outvarscore)) {Console.WriteLine( $"Name: {name}, score: {score}" ); }

Console.WriteLine( "-----TOP 3"); priorityQueue = newPriorityQueue< string, int>( newHigh4LowComparer); priorityQueue.EnqueueRange(list);varrank = 0; while(rank++ < 3&& priorityQueue.TryDequeue( outvarname, outvarscore)) {Console.WriteLine( $"Rank( {rank}):Name: {name}, score: {score}" ); }

上面的 list 就是一个成绩清单,随便写了几个测试数据,通过 PriorityQueueUnorderedItems我们可以拿到排序之前的数据,也是我们加入队列(Enqueue)的顺序,默认的比较是小的在前,也就是成绩低的在前,那我们想按从大到小排序的话就需要自定义比较方式。

上面的 High4LowComparer就是一个自定义的比较,其实就是把比较的结果取了一个反,代码如下:

internal classHigh4LowComparer: IComparer< int> {publicintCompare( intx, inty) {returny.CompareTo(x); }}

上面的输出结果如下:

More

Redis 里有一个 zset(sortedSet) 类型的数据也可以做类似的事情,但是 zset 和 PriorityQueue还是有一些不同的,zset 是一个 set,是一个自动去重的集合,而 PriorityQueue还是一个 Queue不会去重,zset 可以修改对应元素的 priority(score),但是 PriorityQueue目前不支持修改元素对应的优先级

PriorityQueue可以解决我们的一些问题,但是有一些使用要注意的地方:

  1. 首先如果 Priority是一样的话,输出的顺序是有可能不一样的,这是由它内部的实现算法决定的,不能严格的保证顺序

  2. PriorityQueue是非线程安全的,需要注意线程安全问题

  3. PriorityQueue中的 Peek方法只会获取 queue 里即将出队的元素,但是不会从队列中移除这个元素

References

  • https://devblogs.microsoft.com/dotnet/announcing-net-6-preview-2/

  • https://github.com/dotnet/runtime/blob/v6.0.0-preview.2.21154.6/src/libraries/System.Collections/src/System/Collections/Generic/PriorityQueue.cs

  • https://github.com/WeihanLi/SamplesInPractice/blob/master/net6sample/PriorityQueueSample/Program.cs

微软最有价值专家是微软公司授予第三方技术专业人士的一个全球奖项。27年来,世界各地的技术社区领导者,因其在线上和线下的技术社区中分享专业知识和经验而获得此奖项。

MVP是经过严格挑选的专家团队,他们代表着技术最精湛且最具智慧的人,是对社区投入极大的热情并乐于助人的专家。MVP致力于通过演讲、论坛问答、创建网站、撰写博客、分享视频、开源项目、组织会议等方式来帮助他人,并最大程度地帮助微软技术社区用户使用Microsoft技术。

更多详情请登录官方网站:

https://mvp.microsoft.com/zh-cn

主营产品:液压渣浆泵,立式清淤泵,耐腐蚀泵,JHQ潜水渣浆泵