集合修改项目

Question

我已经阅读了很多关于为特定实现选择正确集合的文章,我理解最终它将归结为对真实数据进行基准测试,但是我正忙着这样做:

• c#中的哪些排序集合允许修改包含的项目？我似乎无法找到任何？

• 这是因为修改可能会被实现为删除然后重新插入,从而使显式的"修改"功能毫无意义吗？

我需要一个集合(自定义或标准库),并对其执行以下操作.

• 插入 - 经常
• 删除 - 经常
• 修改 - 经常
• 选择Top X元素 - 每次上述任何一种情况发生时,以及更多,同时发生.

目前我使用的是SortedSet,因为它提供了O(logn)插入,但我不清楚删除性能以及如何最好地修改项目.

Answer 1

首先，我们需要明确修改集合的含义。

一般来说，操作集合是指从列表中插入/删除项目。要修改单个项目，基本上是访问该项目并修改其属性。访问项目的成本取决于集合实现，但项目属性的修改不依赖于集合。另请注意，如果集合项不可变，则无法修改它。

如果您只是想找到最好的内置集合，那么您基本上是在 SortedList 和 SortedSet 之间进行选择（SortedDictionary 与 SortedSet 相同）。

SortedList 在内部将数据存储为数组，因此它可以通过索引进行有效访问（用于获取前 X 个项目）；SortedSet 具有更快的插入和删除速度（通过常数因子），但是索引访问需要在树中搜索下一项，最坏情况下为 O(log n)，最好情况下为 O(1)。

除此之外，两者之间的差异很小，因为它们都实现了红黑树，只是实现细节不同。

必须根据您的用户案例来衡量实际性能。但你已经知道了。