搜索算法（已实现排序算法）

Question

我正在开发一款Java应用程序，关于性能方面我遇到了一些疑问。

我有一个PriorityQueue，它保证删除的元素是具有更高优先级的元素。该PriorityQueue具有Event类的实例（实现了Comparable接口）。每个Event都与一个Entity相关联。

该priorityqueue的大小可能非常大，而且我经常需要删除与某个实体相关的事件。

目前，我使用迭代器来运行整个priorityqueue。但我发现这很耗费时间，我想知道是否有更好的方法来查找和删除与实体“xpto”相关的事件。

有什么建议吗？

谢谢！

- rasgo

Answer 1

有几个选项：

1. 您可以为每个实体使用单独的队列吗？因此，当您获得“xpto”的事件时，将其放入XptoPriorityQueue中？这将减少每个队列的大小，但也可能导致其他一些管理问题。
2. 您是否正在删除特定实体的事件以更快地处理它们？如果是，则应该简单地为这些实体提供更高的优先级，并将它们推到队列的顶部。
3. 您是否正在删除特定实体的事件以将它们从队列中移除并忽略它们？如果是，则它们应该永远不会进入队列，或者应该获得较低的优先级。

- Freiheit

---

谢谢您的建议！这是第三个选项。该应用程序与进化编程有关。我有三种事件：复制、突变和死亡。这三种事件会随机添加到优先队列中（优先级由事件时间定义）。然而，当发生死亡事件时，必须删除所有在优先队列中并且优先级较低的事件。 在我的情况下，防止其他事件在死亡事件之前被添加并不是那么简单的事情，我想... - rasgo

它们必须从队列中删除吗？还是只需不处理？如果您从队列中取出一个“已死”事件，只需丢弃并获取下一个。当然，这假设有一种方法可以检查任何给定的事件是否“死亡”。 - Freiheit

必须删除这些事件，否则PriorityQueue将会变得非常大，从而增加“内存不足”的风险，并且从PriorityQueue中添加或轮询事件将需要更长的时间。 - rasgo

你可以做的是保留一小部分额外状态（用于“死亡实体”）并监视优先队列的大小。 当从队列中获取一个死亡实体的事件时，忽略它并获取下一个。如果队列达到预定义的限制（或者您获得足够数量的已死亡实体），则扫描整个优先队列并删除所有与死亡实体相关的事件。 - Vatine

Answer 2

一些想法：

1. 使用 treap 按实体键排序来实现您的优先队列。如果键是随机分布的，则应能够在 O(log n) 时间内删除元素。
2. 维护一个独立的实体到当前在队列中的事件的映射。而不是立即从队列中删除事件，只需在事件对象上翻转一个位，指示它在到达队列前面时应被忽略。

- Christopher Barber

Answer 3

由于remove是一种线性时间操作，因此您将获得O(N*N)的性能。

如果您创建一个新方法（例如命名为removeIf）来继承PriorityQueue并结合迭代器和remove方法，则可以将其降低到O(N log(N))。

- Doug Currie

Answer 4

我建议您创建一个由PriorityQueue和Set组成的类，具有以下操作：

• 要添加元素，请从Set中删除它，如果不存在，则将其添加到PriorityQueue中。
• 要删除元素，请将其添加到Set中。
• 要取消排队元素，请从PriorityQueue中取消排队元素，直到取消排队的元素不在Set中为止。从Set中删除任何取消排队的元素。

- Daniel C. Sobral

Answer 5

看起来你需要实现一个升级版的优先队列。特别地，你需要O(logN)的删除时间。你可以通过维护两个数据结构来实现：一个是基本上存储你的优先队列的二叉堆事件数组，另一个是从事件到该事件在数组中的偏移量的HashMap（或者从实体到该数组中事件偏移量的列表）。

然后，你可以像对待优先队列一样执行正常的堆操作，只要每次移动Event时更新哈希映射即可。要删除一个事件，查找哈希表中该事件的索引，并在从该索引开始的堆上执行删除操作。

- Keith Randall