0

Here are the requirements:

  1. Store objects that have multiple properties, including unique ID in addition to a Priority integer used for sorting.
  2. Priority will have duplicate values.
  3. Retrieval / checking for the existence of an object by its ID (i.e., Dictionary / Hashtable key) is O(1).
  4. Retrieval of "the top 10 items" by Priority must be as fast as possible. My assumption is this means there must be a separate List / LinkedList that keeps references to the items in the dictionary / hash table. If so, this List / LinkedList must be maintained whenever an item is added or removed, or an item's Priority value changes.
  5. Re-sorting the items upon adding / removing an item, or changing an item's Priority, is as fast as possible.

What data structure would you use? Does one already exist in .NET? Or should it be custom built? I'm leaning toward the latter.

4

1 回答 1

2

SortedList为您提供顺序访问和 O(log n) 检索，这是您可以使用提供的 .NET 集合做的最好的事情。

当我需要这样做时，我结合了优先队列和字典。它看起来像：

var myqueue = new PriorityQueue<DataType>();
var myDictionary = new Dictionary<KeyType, PriorityQueueNode<DataType>>();

每当我插入一个项目时，我都会将它插入到队列中，该队列返回一个PriorityQueueNode. 我把它插入字典。

这给了我 O(1) 检索和 O(log n) 插入。如果您使用配对堆而不是我使用的二进制堆优先级队列，您可以获得分期 O(1) 插入。

检索前 k 个项目是 O(n log k)，其中 n 是优先级队列中的项目数。我为此使用了堆选择。我在当理论遇到实践时写了一些关于堆选择的文章。考虑到项目已经在堆中，您应该能够在 O(k) 中完成，使用基于最小堆中选择的最优算法的技术。我认为这是可能的，但我还没有做到。

我有一个基于堆的优先级队列，可能会为您解决问题。来源位于http://mischel.com/pubs/priqueue.zip。不幸的是，我写的关于它的文章不再在线提供。但是，如果你给我发电子邮件（jim AT mischel.com）并提到这个帖子，我会看看我能不能把它挖出来。

不过，我不再拥有组合字典/优先级队列的代码。对不起。

回答评论中的问题

您是否想要优先级队列或列表/链表实际上取决于您如何使用它以及集合中有多少项目。如果使用线性列表，添加和更改优先级为 O(n)。如果您按键删除，则删除时间为 O(1)。按优先级删除是 O(n)，因为您必须先找到该项目才能将其删除。但是找到前 k 个项目是微不足道的：你拿前 k 个项目。

在二进制堆优先级队列中，插入、删除和更改优先级为 O(log n)。获取前 k 个项目是 O(k)，但实际上比线性列表慢。尽管如果您知道它始终是您想要的前 10 名，您可以在单独的列表中找到并缓存它们。这样，您可以在大多数情况下快速归还它们。每当您添加、删除或更改优先级时，您都会设置一个脏标志，以便您知道在下次有人要求时重新生成前 10 个列表。

配对堆很可能就是您正在寻找的。它确实在 O(1) 摊销时间内添加和删除。更改优先级并不算太糟糕（请参阅链接的 Wikipedia 文章和原始论文 [上面链接]）。删除是 O(log n)。找到前 10 名的最坏情况是 O(n log k)，但是您可以再次缓存这些项目，并且仅在堆更改时才重新生成前 10 名。如果 k 是常数或最大 k 是项目总数的一小部分，则缓存的想法最有效。

您可以看看C5 Generic Collection Library，它有几个优先级队列实现。我没有使用它，但听说过它的好东西。

这实际上归结为集合中有多少项目以及更改的频率与前 10 名的请求之间的关系。线性列表中的操作成本并不需要很多项目（我怀疑是几千）真的要杀了你。而且由于您可以轻松地缓存前 10 个列表并根据需要重新创建它，因此当集合大小增加时，优先级队列对其他操作的较低成本非常有吸引力。

想一想，SortedList考虑到您的操作组合，这可能是您想要的。获得前 10 项的速度非常快。它很容易使用。为什么不制作一个原型，看看它是否能提供足够好的性能呢？

于 2013-09-12T00:03:57.797 回答