结构比SortedSet更快地添加1乘1，然后从末尾访问少量项目
本文关键字：访问 项目 然后 SortedSet 结构 添加 | 更新日期: 2023-09-27 18:26:04
我正在执行List<>，对每个项执行一些操作，然后根据这些操作的结果，可能会将每个项添加到另一个数据结构中，我目前正在使用SortedSet<>。在这之后，我想要排序靠前的n项目作为一个列表。
我对这个SortedSet<>唯一要做的另一件事就是清理整个事情，重新开始。有什么办法可以让我从中获得更多的表现吗？
我看到了这个类似的问题，海报能够使用定制的红黑树（在他们的问题得到回答后）将运行时间减少约1/6。但是SortedSet<>不是已经是一棵红黑树了？在这种情况下，我是否值得尝试通过创建自己的数据结构来提高性能？
您可以尝试通过不为程序不使用的内容"付费"来获得更好的性能：您可以使用一个不排序元素的堆，但可以在k * log(n)时间内提取k最大的元素，而不是使用保持所有元素排序的树结构。
堆在插入和删除时往往比平衡树更快，而且它们还占用连续的内存区域，这在某些情况下可能会提高"缓存友好性"。当然，加速不是免费的：堆不支持快速排序或删除顶部以外的项目。