一个优先级队列，允许高效的优先级更新？ [英] A priority queue which allows efficient priority update?

问题描述

更新：以下是我的Hashed Timing Wheels的实施。如果您有改进性能和并发性的想法，请让我知道。 （2009年1月20日）

  //示例用法：
 public static void main（String [] args）抛出异常{
定时器定时器=新的HashedWheelTimer（）; （int i = 0; i <100000; i ++）{
 timer.newTimeout（new TimerTask（）{
 public void run（Timeout timeout）throws Exception {
 //扩展另一秒
 timeout.extend（）; 
} 
}，1000，TimeUnit.MILLISECONDS）; 
} 
} 
  

更新：我解决了这个问题使用分级和哈希计时轮。 （2009年1月19日）

我试图在Java中实现一个针对超时处理进行了优化的专用定时器。例如，用户可以用死线注册任务，并且当死线结束时，定时器可以通知用户的回调方法。在大多数情况下，注册的任务将在很短的时间内完成，因此大部分任务将被取消（例如task.cancel（））或重新安排到未来（例如task.rescheduleToLater（1，TimeUnit.SECOND））

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

我不能使用java.util.Timer或java.util.concurrent.ScheduledThreadPoolExecutor，因为它们假定大多数任务应该超时。如果任务被取消，则被取消的任务将存储在其内部堆中，直到调用ScheduledThreadPoolExecutor.purge（），并且这是非常昂贵的操作。 （O（NlogN））？

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

你知道任何高度优化的数据结构这个特殊的用例？我正在考虑的一个策略是将所有任务存储在散列表中，并且每隔一秒钟重复一次所有任务，但是并不那么漂亮。

解决方案

如何尝试分开正常情况的处理，从错误情况快速完成事情？

同时使用哈希表和优先级队列。当任务启动时，它被放入哈希值t中如果快速完成，它将在O（1）时间内被删除。

每隔一秒你扫描哈希表和任何已经很长时间的任务，说.75秒，移动到优先级队列。优先级队列应该始终小而易于处理。这假设一秒钟比您正在寻找的超时时间要小得多。

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

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

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

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

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)).

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..

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?)

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?

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.

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屋！