2

我需要创建一个排序列表，一次添加一个项目。所以我决定使用LinkedList<T>，因为它在插入操作中很有效。但是在找到合适的位置时，似乎需要更长的时间。我正在使用线性搜索来获取位置。如果我使用二进制搜索来获取正确的位置ElementAt，它会提高性能吗？据此，它仍然是一个 O(n) 操作。你怎么看？如果是这样，有没有其他更好的数据结构来做这项工作？因为如果我使用不同的数据结构，当向中间插入一个新值时，我将不得不将该位置之后的所有数据移动一个位置，这显然是不希望的。

4

2 回答 2

1

你的问题有一些误解。

对 LinkedList 进行二分搜索以将值插入排序值列表的中间是否会提高性能？

二进制搜索仅对已排序的集合有意义。LinkedList<T>不是一个。这是一个尊重集合的插入订单。要对 a 执行二进制搜索LinkedList<T>：

  • 您将不得不对链表进行排序，这不仅效率很低（对链表的操作）而且对于仅仅插入来说工作量太大

  • 否则您将不得不在插入时通过插入正确的位置来保持排序顺序，这又是太多的工作了。

从您的问题中，我了解到您想要一个尊重集合的排序顺序，但插入必须更快（不像 O(n) 的特征，比如典型的List<T>）。我的建议是在 .NET 中使用排序的集合类型。里面有一个SortedSet<T>。system.dll这不会让你有重复，因为它是一个集合，在这种情况下，你可以实现一个自定义SortedBag<T>（SortedList<T>或任何名称），如此处所示。

我正在使用线性搜索来获取位置。

我的建议是你不要那样做。让集合本身找到执行插入的位置。排序的集合类型最适合这里。

如果我使用二进制搜索来获取正确的位置ElementAt ，它会提高性能吗

ElementAt方法不执行二进制搜索。充其量它会检查集合类型是否为 anIList<T>并相应地使用索引器。不，在您的情况下，它对性能没有影响。

当向中间插入一个新值时，我将不得不将该位置之后的所有数据移动一个位置，这显然是不希望的。

你是对的，在基于数组的结构中间插入List<T>是一个 O(n) 操作。我不确定您是否也需要索引操作，但这会更昂贵。您可以拥有一个带有高效插入的排序集合类型，它没有索引意义，或者您可以拥有一个索引排序集合类型，但插入将是 O(n)。它是你必须付出的代价。

于 2014-06-05T14:35:13.237 回答
0

出于您的目的，使用SortedDictionary 类（或者可能是 SortedList）可能会更好

SortedDictionary 给出 O(log n) 的插入和检索时间。

于 2012-10-15T00:37:09.607 回答