data-structures - 允许高效优先级更新的优先级队列？

Question

更新:这是my implementation of Hashed Timing Wheels 。如果您有提高性能和并发性的想法，请告诉我。 (2009 年 1 月 20 日)

// Sample usage:
public static void main(String[] args) throws Exception {
    Timer timer = new HashedWheelTimer();
    for (int i = 0; i < 100000; i ++) {
        timer.newTimeout(new TimerTask() {
            public void run(Timeout timeout) throws Exception {
                // Extend another second.
                timeout.extend();
            }
        }, 1000, TimeUnit.MILLISECONDS);
    }
}

更新:我通过使用 Hierarchical and Hashed Timing Wheels 解决了这个问题。 (2009 年 1 月 19 日)

我正在尝试在 Java 中实现一个特殊用途的计时器，它针对超时处理进行了优化。例如，用户可以注册一个具有截止时间的任务，并且计时器可以在截止时间结束时通知用户的回调方法。在大多数情况下，注册的任务将在很短的时间内完成，因此大多数任务将被取消(例如task.cancel())或重新安排到 future (例如task.rescheduleToLater(1, TimeUnit.SECOND)) .

我想使用这个计时器来检测空闲的套接字连接(例如，当10秒内没有收到消息时关闭连接)和写入超时(例如，当写入操作在30秒内没有完成时引发异常。)大多数情况下，不会发生超时，客户端将发送消息并发送响应，除非出现奇怪的网络问题..

我无法使用 java.util.Timer 或 java.util.concurrent.ScheduledThreadPoolExecutor 因为它们假设大多数任务都应该超时。如果任务被取消，取消的任务将存储在其内部堆中，直到调用 ScheduledThreadPoolExecutor.purge() 为止，这是一个非常昂贵的操作。 (也许是 O(NlogN)？)

在我在 CS 类(class)中学到的传统堆或优先级队列中，更新元素的优先级是一项昂贵的操作(在许多情况下为 O(logN)，因为它只能通过删除元素并重新插入来实现)它有一个新的优先级值。像斐波那契堆这样的堆有O(1)的decreaseKey()和min()操作时间，但我至少需要的是快速的increaseKey()和min()(或decreaseKey()和max ())。

您知道针对此特定用例高度优化的任何数据结构吗？我正在考虑的一种策略是将所有任务存储在哈希表中，并每秒左右迭代所有任务，但这并不是那么漂亮。

Answer 1

尝试将事情快速完成的正常情况与错误情况的处理分开怎么样？

同时使用哈希表和优先级队列。当一个任务开始时，它会被放入哈希表中，如果它很快完成，它会在 O(1) 时间内被删除。

每隔一秒扫描哈希表，任何已经很长时间(例如 0.75 秒)的任务都会移至优先级队列。优先级队列应该始终很小且易于处理。这假设一秒远小于您正在寻找的超时时间。

如果扫描哈希表太慢，您可以使用两个哈希表，一个用于偶数秒，一个用于奇数秒。当任务开始时，它被放入当前哈希表中。每秒将所有任务从非当前哈希表移动到优先级队列中，并交换哈希表，以便当前哈希表现在为空，非当前表包含一到两秒前启动的任务。

这些选项比仅使用优先级队列复杂得多，但很容易实现，应该是稳定的。