.NET6 中的 PriorityQueue

Intro

.NET 6 中引入了一個(gè)新的集合類(lèi)型 PriorityQueue，正如它的名字那樣，在普通的 Queue 基礎(chǔ)之上增加了優(yōu)先級(jí)的支持，接下來(lái)就一起來(lái)看一下怎么使用，以及一些常用的使用場(chǎng)景介紹。

Get Started

來(lái)看一個(gè)簡(jiǎn)單的使用示例：

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

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

輸出示例：

可以看到輸出的順序和我們添加的順序是相反的， PriorityQueue 在 Dequeue 的時(shí)候是從優(yōu)先級(jí)最小開(kāi)始的，值越小優(yōu)先級(jí)越高，優(yōu)先級(jí)越高越優(yōu)先輸出，如果我們希望最大先輸出是不是可以呢，答案是肯定的，只是我們需要指定我們自己的優(yōu)先級(jí)比較規(guī)則就可以了，可以參考后面的示例

Scenes

借助帶優(yōu)先級(jí)的自動(dòng)排序，我們可以做一些自動(dòng)排序的需求的時(shí)候可以考慮使用 PriorityQueue

Message Queue

借助 PriorityQueue 可以來(lái)實(shí)現(xiàn)一個(gè)優(yōu)先級(jí)消息隊(duì)列，允許用戶(hù)在發(fā)消息的時(shí)候指定一個(gè)消息的優(yōu)先級(jí)，在消費(fèi)的時(shí)候就會(huì)按優(yōu)先級(jí)

var random = new Random();

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

while (queue.TryDequeue(out var message, out _))
{
    Console.WriteLine(message);
}

在上面的示例里我們默認(rèn)指定了一個(gè) int 作為 Priority 的類(lèi)型，并入隊(duì)了一些消息，但是往往會(huì)有很多的消息，可能會(huì)出現(xiàn)優(yōu)先級(jí)相同的情況，我們可以使用時(shí)間和int 作為一個(gè)聯(lián)合的 Priority 類(lèi)型，可以參考下面的示例：

var random = new Random();

var queue = new PriorityQueue<string, (DateTime time, int priority)>(new DateTimePriorityComparer());

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

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

輸出示例如下：

internal class DateTimePriorityComparer : IComparer<(DateTime time, int priority)>
{
    public int Compare((DateTime time, int priority) x, (DateTime time, int priority) y)
    {
        var priorityComparison = x.priority.CompareTo(y.priority);
        if (priorityComparison != 0) return priorityComparison;
        return x.time.CompareTo(y.time);
    }
}

Rank

在很多做排行榜的應(yīng)用中也可以使用 PriorityQueue 來(lái)實(shí)現(xiàn)，比如我們來(lái)做一個(gè)學(xué)生成績(jī)的排名

來(lái)看下面的示例代碼：

var list = new List<(string name, int score)>
{
    ("Mike", 99),
    ("Ming", 100),
    ("Jane", 96),
    ("Yi", 94),
    ("Harry", 90),
};

var priorityQueue = new PriorityQueue<string, int>();
priorityQueue.EnqueueRange(list);

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

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

Console.WriteLine("-----TOP 3");
priorityQueue = new PriorityQueue<string, int>(new High2LowComparer());
priorityQueue.EnqueueRange(list);
var rank = 0;
while (rank++ < 3 && priorityQueue.TryDequeue(out var name, out var score))
{
    Console.WriteLine($"Rank({rank}):Name:{name}, score:{score}");
}

上面的 list 就是一個(gè)成績(jī)清單，隨便寫(xiě)了幾個(gè)測(cè)試數(shù)據(jù)，通過(guò) PriorityQueue 的 UnorderedItems 我們可以拿到排序之前的數(shù)據(jù)，也是我們加入隊(duì)列(Enqueue)的順序，默認(rèn)的比較是小的在前，也就是成績(jī)低的在前，那我們想按從大到小排序的話(huà)就需要自定義比較方式。

上面的 High2LowComparer 就是一個(gè)自定義的比較，其實(shí)就是把比較的結(jié)果取了一個(gè)反，代碼如下：

internal class High2LowComparer : IComparer<int>
{
    public int Compare(int x, int y)
    {
        return y.CompareTo(x);
    }
}

上面的輸出結(jié)果如下：

More

Redis 里有一個(gè) zset(sortedSet) 類(lèi)型的數(shù)據(jù)也可以做類(lèi)似的事情，但是 zset 和 PriorityQueue 還是有一些不同的，zset 是一個(gè) set，是一個(gè)自動(dòng)去重的集合，而 PriorityQueue 還是一個(gè) Queue 不會(huì)去重，zset 可以修改對(duì)應(yīng)元素的 priority（score)，但是 PriorityQueue 目前不支持修改元素對(duì)應(yīng)的優(yōu)先級(jí)

PriorityQueue  可以解決我們的一些問(wèn)題，但是有一些使用要注意的地方：

1. 首先如果 Priority 是一樣的話(huà)，輸出的順序是有可能不一樣的，這是由它內(nèi)部的實(shí)現(xiàn)算法決定的，不能?chē)?yán)格的保證順序
2. PriorityQueue 是非線程安全的，需要注意線程安全問(wèn)題
3. PriorityQueue 中的 Peek 方法只會(huì)獲取 queue 里即將出隊(duì)的元素，但是不會(huì)從隊(duì)列中移除這個(gè)元素

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