允许有效优先级更新的优先级队列? [英] A priority queue which allows efficient priority update?

问题描述

更新:这是我对哈希计时轮的实现.如果您有提高性能和并发性的想法，请告诉我.(2009 年 1 月 20 日)

UPDATE: Here's my implementation of Hashed Timing Wheels. Please let me know if you have an idea to improve the performance and concurrency. (20-Jan-2009)

// 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);
    }
}

更新:我使用 分层和散列计时轮.(2009 年 1 月 19 日)

UPDATE: I solved this problem by using Hierarchical and Hashed Timing Wheels. (19-Jan-2009)

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

I'm trying to implement a special purpose timer in Java which is optimized for timeout handling. For example, a user can register a task with a dead line and the timer could notify a user's callback method when the dead line is over. In most cases, a registered task will be done within a very short amount of time, so most tasks will be canceled (e.g. task.cancel()) or rescheduled to the future (e.g. task.rescheduleToLater(1, TimeUnit.SECOND)).

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

I want to use this timer to detect an idle socket connection (e.g. close the connection when no message is received in 10 seconds) and write timeout (e.g. raise an exception when the write operation is not finished in 30 seconds.) In most cases, the timeout will not occur, client will send a message and the response will be sent unless there's a weird network issue..

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

I can't use java.util.Timer or java.util.concurrent.ScheduledThreadPoolExecutor because they assume most tasks are supposed to be timed out. If a task is cancelled, the cancelled task is stored in its internal heap until ScheduledThreadPoolExecutor.purge() is called, and it's a very expensive operation. (O(NlogN) perhaps?)

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

In traditional heaps or priority queues I've learned in my CS classes, updating the priority of an element was an expensive operation (O(logN) in many cases because it can only be achieved by removing the element and re-inserting it with a new priority value. Some heaps like Fibonacci heap has O(1) time of decreaseKey() and min() operation, but what I need at least is fast increaseKey() and min() (or decreaseKey() and max()).

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

Do you know any data structure which is highly optimized for this particular use case? One strategy I'm thinking of is just storing all tasks in a hash table and iterating all tasks every second or so, but it's not that beautiful.

推荐答案

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

How about trying to separate the handing of the normal case where things complete quickly from the error cases?

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

Use both a hash table and a priority queue. When a task is started it gets put in the hash table and if it finishes quickly it gets removed in O(1) time.

您扫描哈希表的每一秒，任何已经很长时间的任务，比如 0.75 秒，都会被移动到优先级队列中.优先级队列应该总是很小并且易于处理.这假设一秒远小于您正在寻找的超时时间.

Every one second you scan the hash table and any tasks that have been a long time, say .75 seconds, get moved to the priority queue. The priority queue should always be small and easy to handle. This assumes that one second is much less than the timeout times you are looking for.

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

If scanning the hash table is too slow, you could use two hash tables, essentially one for even-numbered seconds and one for odd-numbered seconds. When a task gets started it is put in the current hash table. Every second move all the tasks from the non-current hash table into the priority queue and swap the hash tables so that the current hash table is now empty and the non-current table contains the tasks started between one and two seconds ago.

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

There options are a lot more complicated than just using a priority queue, but are pretty easily implemented should be stable.

这篇关于允许有效优先级更新的优先级队列?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！