频繁插入到已排序的集合中 [英] Frequent inserts into sorted collection

问题描述

我有排序的集合（List），我需要保持它排序的所有时间。

I have sorted collection (List) and I need to keep it sorted at all times.

我目前使用List.BinarySearch我的集合，然后插入元素在正确的地方。我也在每次插入后尝试排序列表，但性能不可接受。

I am currently using List.BinarySearch on my collection and then insert element in right place. I have also tried sorting list after every insertion but the performance in unacceptable.

有没有解决方案将提供更好的性能？也许我应该使用其他集合。

Is there a solution that will give better performance? Maybe I should use other collection.

（我知道SortedList，但它只限于唯一键）

(I am aware of SortedList but it is restricted to unique keys)

推荐答案

PowerCollections 有一个 OrderedBag 类型，这可能是有益于你所需要的。从文档

PowerCollections has an OrderedBag type which may be good for what you need. From the docs

插入，删除和查找
元素都是在 log（N）+ M
time ，其中N是
树中的键的数量，M是元素的副本的当前数量

处理。

Inserting, deleting, and looking up an an element all are done in log(N) + M time, where N is the number of keys in the tree, and M is the current number of copies of the element being handled.

但是，对于.NET 3.5内置类型，使用 List.BinarySearch 并将每个项目插入正确的位置是一个好的开始 - 但是在内部使用了一个数组，所以你的性能会下降，因为你在插入时做的所有复制。

However, for the .NET 3.5 built in types, using List.BinarySearch and inserting each item into the correct place is a good start - but that uses an Array internally so your performance will drop due to all the copying you're doing when you insert.

如果你可以将插入分组为批处理，这将改善的东西，但除非你只能在所有插入后只有一个排序操作，你可能最好使用 OrderedBag 从 PowerCollections 如果可以。

If you can group your inserts into batches that will improve things, but unless you can get down to only a single sort operation after all your inserting you're probably better off using OrderedBag from PowerCollections if you can.

这篇关于频繁插入到已排序的集合中的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！