C# 不提供优先级队列的本机实现。
在 Stackoverflow 上，此类问题的常见答案是使用Power Collections。
我应该继续这样做，还是有任何不利之处？
问问题
1381 次
1 回答
9
Power Collections 确实提供了一些在 .NET 框架中（尚未）存在的常用数据结构的出色实现。虽然使用该选项并不可怕，但我想指出这种方法的一个重要缺陷。
OrderedMultiDictionary（以及所有其他 Power Collection 类）使用红黑树来创建键值对的有序包。对于优先级队列，RB 树往往是一种劣等的数据结构。我假设优先级值可以散列为整数。
原因很简单——字典可以在 O(1) 中立即跳转到特定的优先级值，其中可以使用专门的数据结构来存储该优先级的值（即队列）。
测试
为了检查我的声明，我编写了一个简单的基准，根据 3 个不同的想法比较优先级队列结构：
- Power Collections OrderedMultiDictionary
- 排序字典
- 字典
第二个选项使用SortedDictionary，它在内部被实现为 BST。第三个选项使用具有 O(1) 查找的简单字典。
我测试了不同数量的元素，如 Y 轴所示，以及不同数量的不同值，如 X 轴所示。特定组合的结果显示为 3x3 值矩阵。第一行指的是选项 1（OrdererdMultiDictionary，第二行指的是 SortedDictionary，第三行指的是 Dictionary。这 3 行中的每一个中的第一个值显示了将相应数量的值排入队列所花费的时间，第二个是枚举所花费的时间在所有值上，第三次再次将所有值出列。
所有时间都是 log 2。值 10 表示 2^10ms = 1s，尽管绝对值不重要。元素的数量增加了一倍，这意味着，如果结构的行为类似于 O(n)，则时间应该每次增加 1。
横向上，不同值的数量每列乘以 32。因此，第一列（一遍又一遍地插入相同的值）显示了保存这些值的内部数据结构的性能。
使用的机器是带有 16 GB 加 SSD 的 i7。
| 1 | 32 | 1024 | 32768 | 1048576 |
128
| -4.9 / -4.3 / n/a | -4.7 / -4.1 / n/a | -4.8 / -2.9 / n/a | -4.9 / -2.9 / n/a | -4.9 / -2.9 / n/a |
| -7.5 / -6.1 / -5.3 | -6.5 / -5.7 / -5.1 | -4.7 / -4.9 / -4.3 | -4.6 / -4.7 / -4.2 | -4.6 / -4.8 / -4.2 |
| -7.5 / -7.6 / -6.6 | -6.8 / -7.3 / -6.3 | -5.9 / -5.9 / -3.0 | -6.2 / -6.4 / -2.8 | -6.2 / -6.3 / -2.8 |
256
| -3.8 / -3.2 / n/a | -3.7 / -3.1 / n/a | -3.7 / -2.2 / n/a | -3.8 / -1.8 / n/a | -3.7 / -1.8 / n/a |
| -6.8 / -5.5 / -4.4 | -5.8 / -5.4 / -4.2 | -3.8 / -4.3 / -3.4 | -3.5 / -4.1 / -3.2 | -3.5 / -4.1 / -3.1 |
| -6.6 / -6.9 / -5.7 | -6.1 / -6.7 / -5.7 | -5.5 / -5.3 / -1.8 | -5.3 / -5.0 / -0.9 | -5.3 / -5.6 / -1.0 |
512
| -2.7 / -2.1 / n/a | -2.5 / -2.1 / n/a | -2.5 / -1.5 / n/a | -2.6 / -0.7 / n/a | -2.6 / -0.7 / n/a |
| -5.9 / -5.2 / -3.4 | -4.9 / -5.0 / -3.3 | -3.2 / -4.2 / -2.6 | -2.4 / -3.2 / -2.1 | -2.3 / -3.2 / -2.0 |
| -5.7 / -6.1 / -4.9 | -5.2 / -6.1 / -4.8 | -4.8 / -5.0 / -1.7 | -4.3 / -4.0 / 1.0 | -4.4 / -4.7 / 1.0 |
1024
| -1.6 / -1.0 / n/a | -1.4 / -1.0 / n/a | -1.4 / -0.7 / n/a | -1.5 / 0.4 / n/a | -1.5 / 0.3 / n/a |
| -4.9 / -4.7 / -2.4 | -4.1 / -4.5 / -2.3 | -2.6 / -4.0 / -1.8 | -1.2 / -2.3 / -1.0 | -1.2 / -2.3 / -0.9 |
| -4.7 / -5.4 / -3.9 | -4.4 / -5.3 / -3.8 | -4.1 / -4.6 / -1.6 | -3.3 / -3.0 / 2.9 | -3.5 / -3.8 / 3.0 |
2048
| -0.4 / 0.1 / n/a | -0.3 / 0.1 / n/a | -0.3 / 0.3 / n/a | -0.3 / 1.5 / n/a | -0.5 / 1.4 / n/a |
| -4.0 / -4.1 / -1.4 | -3.2 / -4.0 / -1.3 | -1.7 / -3.5 / -0.9 | -0.2 / -1.4 / 0.1 | -0.2 / -1.3 / 0.1 |
| -3.8 / -4.5 / -2.9 | -3.5 / -4.4 / -2.9 | -3.2 / -3.9 / -1.0 | -2.5 / -2.0 / 4.9 | -2.4 / -2.1 / 4.9 |
4096
| 0.7 / 1.2 / n/a | 0.8 / 1.2 / n/a | 0.9 / 1.3 / n/a | 0.8 / 2.8 / n/a | 0.6 / 2.9 / n/a |
| -3.0 / -3.2 / -0.4 | -2.2 / -3.3 / -0.3 | -0.8 / -3.0 / 0.1 | 0.9 / -0.4 / 1.1 | 0.9 / -0.2 / 1.2 |
| -2.9 / -3.5 / -1.9 | -2.6 / -3.5 / -1.9 | -2.3 / -3.2 / -0.9 | -1.6 / -1.1 / 6.6 | -1.3 / -1.1 / 6.9 |
8192
| 1.8 / 2.8 / n/a | 1.9 / 3.0 / n/a | 2.0 / 3.0 / n/a | 1.9 / 4.0 / n/a | 1.8 / 4.1 / n/a |
| -2.0 / -2.4 / 0.6 | -1.3 / -2.4 / 0.7 | 0.1 / -2.2 / 1.1 | 1.8 / 0.4 / 2.1 | 2.1 / 0.9 / 2.3 |
| -1.9 / -2.6 / -1.0 | -1.6 / -2.5 / -0.9 | -1.4 / -2.4 / -0.3 | -0.6 / -0.3 / 8.0 | -0.5 / 0.1 / 8.9 |
16384
| 2.9 / 3.7 / n/a | 3.0 / 3.6 / n/a | 3.1 / 3.8 / n/a | 3.1 / 4.6 / n/a | 3.0 / 5.2 / n/a |
| -1.0 / -1.5 / 1.6 | -0.3 / -1.5 / 1.7 | 1.1 / -1.4 / 2.0 | 2.4 / 0.7 / 2.9 | 3.2 / 1.9 / 3.6 |
| -0.9 / -1.6 / 0.0 | -0.6 / -1.6 / 0.1 | -0.5 / -1.5 / 0.4 | 0.0 / -0.1 / 8.0 | 0.6 / 1.2 / 10.9 |
32768
| 4.0 / 5.0 / n/a | 4.1 / 5.0 / n/a | 4.3 / 5.0 / n/a | 4.2 / 5.5 / n/a | 4.1 / 6.4 / n/a |
| -0.1 / -0.5 / 2.6 | 0.7 / -0.5 / 2.7 | 2.0 / -0.5 / 3.1 | 3.1 / 0.9 / 3.8 | 4.3 / 3.0 / 4.8 |
| 0.1 / -0.6 / 1.0 | 0.4 / -0.6 / 1.1 | 0.5 / -0.5 / 1.3 | 0.9 / 0.4 / 8.0 | 1.6 / 2.3 / 12.9 |
65536
| 5.2 / 6.6 / n/a | 5.4 / 6.4 / n/a | 5.5 / 6.4 / n/a | 5.5 / 6.8 / n/a | 5.4 / 7.4 / n/a |
| 1.0 / 0.4 / 3.6 | 1.8 / 0.5 / 3.7 | 3.0 / 0.4 / 4.1 | 4.2 / 1.9 / 4.9 | 5.5 / 4.2 / 6.0 |
| 1.1 / 0.4 / 2.0 | 1.4 / 0.4 / 2.1 | 1.5 / 0.5 / 2.4 | 2.0 / 1.4 / 9.8 | 3.2 / 3.4 / 14.8 |
131072
| 6.5 / 7.8 / n/a | 6.6 / 7.6 / n/a | 6.8 / 7.4 / n/a | 6.9 / 7.7 / n/a | 6.8 / 8.6 / n/a |
| 2.0 / 1.4 / 4.6 | 2.9 / 1.4 / 4.8 | 4.1 / 1.5 / 5.2 | 5.2 / 2.4 / 5.8 | 6.8 / 5.4 / 7.0 |
| 2.1 / 1.4 / 3.1 | 2.4 / 1.4 / 3.1 | 2.5 / 1.5 / 3.3 | 3.0 / 2.0 / 9.9 | 4.4 / 4.6 / 16.6 |
262144
| 7.5 / 8.9 / n/a | 7.6 / 8.9 / n/a | 7.8 / 8.6 / n/a | 8.0 / 8.8 / n/a | 8.2 / 9.6 / n/a |
| 3.0 / 2.4 / 5.6 | 3.9 / 2.4 / 5.7 | 5.1 / 2.4 / 6.1 | 6.1 / 2.9 / 6.7 | 8.1 / 6.4 / 8.1 |
| 3.1 / 2.5 / 4.1 | 3.3 / 2.4 / 4.1 | 3.5 / 2.4 / 4.2 | 4.7 / 3.6 / 9.9 | 5.7 / 5.8 / 18.2 |
524288
| 8.6 / 10.0 / n/a | 8.8 / 10.0 / n/a | 9.0 / 9.6 / n/a | 9.4 / 9.7 / n/a | 9.3 / 10.4 / n/a |
| 4.0 / 3.4 / 6.6 | 4.9 / 3.4 / 6.7 | 6.1 / 3.4 / 7.1 | 7.0 / 3.7 / 7.6 | 8.9 / 7.0 / 8.8 |
| 4.1 / 3.5 / 5.0 | 4.4 / 3.4 / 5.1 | 4.5 / 3.4 / 5.2 | 4.9 / 3.6 / 9.9 | 6.8 / 6.5 / 19.2 |
1048576
| 9.7 / 11.0 / n/a | 9.9 / 11.1 / n/a | 10.2 / 10.7 / n/a | 10.7 / 10.7 / n/a | 10.7 / 11.2 / n/a |
| 5.0 / 4.4 / 7.5 | 5.9 / 4.4 / 7.7 | 7.1 / 4.4 / 8.1 | 8.0 / 4.6 / 8.5 | 9.7 / 7.3 / 9.8 |
| 5.1 / 4.4 / n/a | 5.3 / 4.4 / n/a | 5.5 / 4.4 / n/a | 5.9 / 4.6 / n/a | 7.7 / 6.8 / n/a |
2097152
| 10.8 / 12.0 / n/a | 11.0 / 12.1 / n/a | 11.3 / 11.8 / n/a | 12.1 / 11.8 / n/a | 12.0 / 12.1 / n/a |
| 6.0 / 5.4 / 8.5 | 7.0 / 5.4 / 8.7 | 8.1 / 5.4 / 9.1 | 9.0 / 5.6 / 9.5 | 10.6 / 7.6 / 10.3 |
| 6.1 / 5.4 / n/a | 6.4 / 5.4 / n/a | 6.6 / 5.4 / n/a | 6.9 / 5.6 / n/a | 8.8 / 7.2 / n/a |
4194304
| 11.9 / 13.0 / n/a | 12.0 / 13.1 / n/a | 12.5 / 12.9 / n/a | 13.3 / 12.8 / n/a | 13.2 / 13.0 / n/a |
| 7.0 / 6.4 / 9.5 | 8.0 / 6.4 / 9.7 | 9.2 / 6.4 / 10.1 | 10.1 / 6.5 / 10.5 | 11.6 / 8.0 / 11.1 |
| 7.1 / 6.4 / n/a | 7.3 / 6.4 / n/a | 7.6 / 6.4 / n/a | 8.0 / 6.5 / n/a | 9.9 / 7.7 / n/a |
8388608
| n/a / n/a / n/a | n/a / n/a / n/a | 13.7 / 14.1 / n/a | 14.5 / 13.8 / n/a | 14.4 / 13.9 / n/a |
| 8.0 / 7.4 / 10.5 | 9.0 / 7.4 / 10.7 | 10.2 / 7.4 / 11.1 | 11.1 / 7.5 / 11.5 | 12.6 / 8.5 / 12.0 |
| 8.1 / 7.4 / n/a | 8.4 / 7.4 / n/a | 8.6 / 7.4 / n/a | 9.1 / 7.5 / n/a | 10.8 / 8.3 / n/a |
16777216
| n/a / n/a / n/a | n/a / n/a / n/a | n/a / n/a / n/a | n/a / n/a / n/a | n/a / n/a / n/a |
| 9.0 / 8.4 / 11.6 | 10.0 / 8.4 / 11.7 | 11.2 / 8.4 / 12.1 | 12.2 / 8.4 / 12.5 | 13.6 / 9.1 / 12.9 |
| 9.1 / 8.4 / n/a | 9.3 / 8.4 / n/a | 9.6 / 8.4 / n/a | 10.1 / 8.4 / n/a | 11.9 / 9.0 / n/a |
测试的缺陷
所有小于 100 个值的行都没有显示，因为它们没有实际意义，可以被认为是热身。
所有测试只执行一次，没有进行平滑处理，因此任何方向的尖峰都是可能的。超过 10000 的值的测试运行了相当长的时间，以至少排除短尖峰。我将整个基准测试重复了几次，差异在 10% 以内。
数据结构尚未使用它们可能期望保存的适当数量的元素进行初始化。这部分是由于较大集合的内存消耗。
OMD Dequeuing 没有值，因为我还没有找到合理的方法来实现它。我将不胜感激这方面的任何帮助。
结果
对于较大的值，结果非常一致。
- 对于较小的桶数（不同值的数量），基于选项 2 或 3 的方法在排队时比 OMD 快几倍，在枚举时甚至更快。出队不存在比较。
- 对于较大的桶数，OMD 不会减慢，而选项 2+3 会减慢（因子 10）。最终，选项 2 在入队时稍差，但在枚举时仍然非常快，选项 3（简单字典）胜过两者。
- 然而，选项 3 在大桶数出列时变得很糟糕，到了确定不可用的地步。这是由于对 SortedDictionary 中不存在的最小键的永久搜索。
关于内存使用，OMD 使用的内存比选项 2 和 3 多几倍，并且持续抛出超过 500 万个值的 OutOfMemory 异常。选项 3 再次使用的内存明显少于选项 2。每次测试后，都会强制执行完整的垃圾回收。
总之，我建议使用队列排序字典，因为它往往与 Power Collections 中使用的 RB-tree 方法一样快，同时使用更少的内存。如果不同的优先级值很少，则优势会增加。当然，这仅在您处理大量数据时才重要。
源代码
添加 SortedDictionary 的源代码。更多信息请访问http://pastebin.com/J4snVYzb
public class PriorityQueue<TK, TV>
{
private readonly SortedDictionary<TK, Queue<TV>> _D = new SortedDictionary<TK, Queue<TV>> ();
public void Enqueue (TK key, TV value)
{
Queue<TV> list;
if (!_D.TryGetValue (key, out list)) {
list = new Queue<TV> ();
_D.Add (key, list);
}
list.Enqueue (value);
Count++;
}
public int Count
{
get;
private set;
}
public TV Dequeue ()
{
var first = _D.First ();
var item = first.Value.Dequeue ();
if (!first.Value.Any ()) {
_D.Remove (first.Key);
}
return item;
}
public IEnumerable<TV> Values
{
get
{
var keys = _D.Keys.ToArray ();
foreach (var key in keys) {
foreach (var item in _D[key]) {
yield return item;
}
}
}
}
}
于 2013-03-28T14:10:55.340 回答