c# - 我应该将Power Collection的OrderedMultiDictionary用作优先级队列吗？

Question

C＃不提供优先级队列的本地实现。

在Stackoverflow上，对此类问题的常见答案是使用Power Collections。

我应该继续这样做，还是有不利之处？

Answer 1

实际上，Power Collections提供了.NET框架中尚未存在的常用数据结构的出色实现。尽管使用该选项并不可怕，但我想指出这种方法的一个重要缺陷。

OrderedMultiDictionary（以及所有其他Power Collection类）使用一棵红黑树来创建键值对的有序包。对于优先级队列，RB树往往是劣等的数据结构。我假设优先级值可哈希为整数。

原因很简单-字典可以立即在O（1）中跳转到特定的优先级值，在字典中可以使用专门的数据结构来存储该优先级的值（即队列）。

测试

为了检查我的主张，我编写了一个简单的基准，该基准根据3种不同的思想比较优先级队列结构：


订购了Power CollectionsMultiDictionary
分类词典
字典


第二个选项使用SortedDictionary，其内部实现为BST。第三个选项使用带有O（1）查找的简单Dictionary。

我用Y轴上显示的各种元素和X轴上显示的不同值进行了测试。特定组合的结果显示为3x3值矩阵。第一行引用选项1（OrdererdMultiDictionary，第二行引用SortedDictionary，第三行引用Dictionary。这三行中的第一行值表示对相应数量的值进行排队的时间，第二行表示对值进行枚举的时间在所有值上，第三次再次使所有值出队。

所有时间均为对数2。值10表示2 ^ 10ms = 1s，尽管绝对值的重要性不高。元素的数量增加了一倍，这意味着，如果该结构的行为类似于O（n），则时间每次应增加1。

在水平方向上，每列将不同值的数量乘以32。因此，第一列（一遍又一遍地插入相同的值）显示了保存这些值的内部数据结构的性能。

所使用的计算机是具有16 GB固态硬盘的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出队没有任何价值，因为我还没有找到实现此目的的合理方法。我将不胜感激。

结果

对于较大的值，结果非常一致。


对于较小的存储桶计数（不同值的数量），基于选项2或3的方法在排队时比OMD快几倍，而在枚举时甚至要快得多。不存在用于出队的比较。
对于较大数量的存储区，OMD不会降低速度，而选项2 + 3会降低速度（系数10）。最终，选项2入队稍差，但枚举仍然非常快，选项3（简单的Dictionary）胜过两者。
但是，对于大存储桶数量而言，选项3变得很糟糕，以至于无法使用。这是由于永久搜索了SortedDictionary中不存在的最小键。


关于内存使用情况，OMD使用的内存比选项2和3多出几倍，并且始终抛出OutOfMemory异常，超过500万个值。选项3再次使用的内存明显少于选项2。在每次测试之后，都执行了完整的垃圾回收。

最后，我建议使用SortedDictionary of Queue，因为它往往与Power Collections中使用的RB树方法一样快，同时使用的内存更少。如果几乎没有不同的优先级值，则优势会增加。当然，这仅在处理大量数据时才重要。

源代码

添加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;
                }
            }
        }
    }
}