c# - 结构比 SortedSet 更快地添加 1-by-1，然后从末尾访问少量项目

Question

我正在经历 a List<>，对每个项目执行一些操作，然后根据这些操作的结果，可能将每个项目添加到另一个数据结构中，我目前正在为此使用SortedSet<>. 在此之后，我希望将排名靠前的n项目作为列表。

我唯一需要做的另一件事SortedSet<>就是清除整个事情并重新开始。有什么办法可以让我从中获得更多的性能？

我看到了这个类似的问题，其中发布者使用自定义红黑树（在他们的问题得到回答后）能够将运行时间减少约 1/6。但是 SortedSet<> 不是已经是红黑树了吗？在这种情况下，我是否值得通过创建自己的数据结构来尝试提高性能？

Answer 1

您可以尝试通过不为您的程序不使用的东西“付费”来获得更好的性能：而不是使用保持所有元素排序的树结构，您可以使用不对元素进行排序但让您提取最大的堆k时间元素k * log(n)。

堆在插入和删除方面往往比平衡树更快，并且它们还占用内存的连续区域，这在某些情况下可能会提高“缓存友好性”。当然，加速不是免费的：堆不支持快速排序或删除顶部以外的项目。