什么更快:排序集合或列表以及它上的linq查询(密集的插入/删除)？

Question

我进退两难。我必须实现优先级队列(自定义排序顺序)。我需要使用它每秒插入/处理/删除大量消息(~100-1000)。

哪种设计在运行时更快？

1)按优先级集合排序的自定义(列表)

2)当我需要处理(去队列)消息时，list(非排序集合)+ linq查询。

3)其他东西

添加：

解决方案：

按优先级排列的队列列表(字典)：SortedList<int, VPair<bool, Queue<MyMessage>>>其中int -优先级，如果它不是空队列，则为bool - true

Answer 1

你的读写比率是多少？是否涉及多个线程，如果涉及，如何涉及？

与以往一样，在询问性能时，对代码路径进行基准测试，并亲自查看(问题域越具体，这一点就越准确)。

Answer 2

唯一能确定的方法就是为自己衡量自己的表现。

Answer 3

在未排序的数据结构中找到元素平均需要O(n) (超过数据结构一次)。二进制搜索树在O(log )上具有平均插入复杂度，平均查找复杂度为O(log )。所以从理论上讲，使用这样的东西会更快。实际上，开销或数据的形状可能会扼杀理论上的优势。

此外，如果您的自定义排序顺序可以在运行时更改，则可能必须重新构建排序的数据结构，这是额外的性能问题。

最后:如果它对您的应用程序很重要，那么尝试不同的方法并自己对其进行基准测试--这是确保其工作正常的唯一方法。