logo标签列表

固定大小的集合，保留前N个值的集合

c#arraysalgorithmsortingcollections
5
我的代码处理大量的值，我正在寻找一种高效的结构来跟踪前（N）个值，其中N小于10，因此收集所有数字然后对列表进行排序并取前（N）可能不是最有效的方法。
为此，我正在构建一个大小为N的固定集合，以按降序排序方式保持前（N）个值。如果值高于任何现有值（在这种情况下，最后一个元素将被删除），或者集合未满，则已排序集合的Add(T value)方法将向集合添加该值。
我能够使用双向LinkedList<T>实现我想要的内容，因为它具有快速插入和删除，但我想知道使用SortedDictionary<TKey, TValue>或优先队列是否更好？
谢谢。
可能是重复问题：有限空间的优先队列：寻找好的算法 - Aryabhatta
3
如果你谈论的是N<10，那么数据结构之间的性能差异可能是微不足道的。我会选择实现最简单且最容易理解的方式。 - Dan Bryant
请坚持您最初的实现。对于这个问题，LinkedList和二进制替换是最好的选择！ - instcode
8个回答
7

我建议使用一个有限深度的堆。我不知道是否已经有这样的库存在，但实现起来应该很容易。

2
如果可以的话，您还可以按相反顺序对堆进行排序，并在插入后大小大于N时删除最小项。 - mihi
1
@Svante 你如何实现一个有限深度的堆？当大小超过N时，必须清除最小的元素。在最大堆中查找最小元素需要O(N)时间。我能想到的唯一方法是拥有两个堆：一个最大堆和一个最小堆。将值插入两个堆中，直到有N个值。当您想要插入另一个值时，从最小堆中弹出最小值。在最大堆中查找该值（通常需要O(N)时间，但您可以维护一个值=>索引的哈希映射）并将其删除。将新值添加到两个堆中。还有其他方法吗？ - John Kurlak
@Svante 嗯，我想我们可以使用一个最小-最大堆 :) - John Kurlak
4
使用SortedDictionary或SortedList的主要优势在于可以跳过排序步骤，因为它们会自动处理（例如，每次添加一个值时，您只需删除第（n + 1）个元素）。 但是采用这种复杂结构处理10个元素就像使用核弹来杀死一只苍蝇...
也许链表是一个好方法，而在有序地插入值方面，简单的线性比较并不比二分查找慢（我们仍然谈论最多10次比较相对于~3次，当前CPU甚至感觉不到差异）。
编辑：
可以使用固定数组来构建具有二叉堆的优先队列，这可能是实现此目的的正确方式。
链表是次优的数据结构，因为插入操作的时间复杂度为O(N)。 - olegz
1
准确地说，插入是O(1)，因为不需要移位; 找到要插入的位置需要O(n)（最多）。我在提到“线性比较”时已经提到了它。无论如何，我刚刚编辑了它，用“好方法”替换了“最佳方法”;) - digEmAll
1
链表每个元素使用一个内存块，每添加一个新元素就需要预留一个新的内存块；这比数组要昂贵一些，因为数组可以一次性预留所有空间（因为其最大大小已知）。虽然垃圾回收机制运作良好，但最好还是尽量避免使用它。 - user192472
@fred-hh：是的，你说得对。实际上，最好的方法可能是将固定数组作为二叉堆。不管怎样，我认为最多只有10个元素，我们永远不会注意到差异... - digEmAll
3

对于这么小的数字，只需使用一个数组即可。扫描该数组并跟踪最小值及其位置。如果您的新数字大于集合中的最小值，请替换它。当然，在插入数字后，您应该扫描最低值一次，然后仅在有更大的数字时进行比较（替换并重新扫描）。

1
虽然这个集合很小（只有10个元素），但这听起来对我来说非常低效。如果新元素比列表中最大的元素还要大怎么办？你将用它替换最小的元素，列表变得无序。现在你必须通过所有元素进行线性搜索，以找到下一个插入中的最小值 :-s - instcode
对的，这个列表是未排序的。你只有在交换新值后才能扫描它。你存储最低值及其位置。检查后续值只需与存储的最低值进行比较。如果你有一个更大的值，那么就交换并重新扫描。 - phkahler
3

性能可能会真正发生变化。

对于 N < 10，任何过于复杂的数据结构都可能显著拖慢性能（尽管可能不至于灾难性），因此我建议使用数组来存储项目。

然后有三种主要可能性来安排数组中的项目：

  1. 排序可能是保持简单的最佳选择：
    • 确定是否插入新项的时间相同（与最低比较）
    • O(N) 时间插入 - 但这仅适用于在 N 个最佳项目中的项目。并且如果您的输入足够随机，则平均时间甚至会更低，因为大多数插入只会移动顶部底部的几个元素。
  2. 未排序：
    • 每个输入元素的时间复杂度为O(N)，与“排序”相比太多了
  3. 实现优先级队列的二叉堆：更复杂的实现，但可能比“排序”更快
    • 确定是否插入新项的时间相同（与最低比较）
    • O(log N) 时间插入 - 仅适用于在 N 个最佳项目中的项目
2
除非你有充分的理由，否则我建议使用优先队列。
有一个技巧可以简化逻辑。大多数人的第一个想法是查看每个传入的项目，并将其插入到集合中，当集合包含的项目少于所需数量时，或者新项目比当前集合中最小的项目大时。
如果你在集合中留出了一个额外的项目空间，那么你可以简化很多事情。始终将每个传入的项目插入到集合中，然后如果集合太大，则删除最小的项目。
虽然对于只有10个项目来说，使用优先队列可能过于复杂，但它使逻辑简单，并且在空间和时间上都很高效，因此如果你需要N = 10000（或其他任何数字），它仍然可以很好地工作。
1
如果速度真的很重要，我会避免“始终插入每个传入项”，因为插入不是很便宜（O(log N)），而且在前N个传入项之后，与优先级队列中的顶部项进行必要的比较（=最差的N个最佳项）就足够了。 - user192472
1

编辑：

如果只需要前N个值，而其他值并不重要，那么使用一个简单的数组就可以便宜地完成工作。

保持其排序并测试最大值。仅当需要存储时，才正确插入并移动剩余元素。对于小尺寸，这是一项廉价的操作，我猜它不会经常执行。

1
如果您有一个固定大小为10的数组，为什么不直接使用长度为10的排序数组和二分查找呢？但是我不确定在这种情况下，由于一些开销，二分查找是否比沿着数组进行愚蠢的搜索更加优越。
在这种情况下，搜索速度会很快，但插入元素的代价很高，因为它需要将数组复制到一个新数组中。 - alhazen
不，据我理解，大小应该始终限制为10个项目，您将会移除最后一个。您只需要将插入位置之后的所有项目向前移动一位。这样就完全避免了链表插入时对象实例化的问题。 - Frank
0

在原始数组上使用二进制插入排序，将最小值推出末尾。这通常是维护小型排序数组的最快方法，并且例如通常用作各种排序算法（例如MergeSort）的特殊情况。

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接