相关疑难解决方法(0)

我正在尝试使用a PriorityQueue来命令对象Comparator.

这可以很容易地实现,但是对象类变量(比较器计算优先级)可能在初始插入后发生变化.大多数人都提出了删除对象,更新值并再次重新插入的简单解决方案,因为这是优先级队列的比较器付诸行动的时候.

除了在PriorityQueue周围创建一个包装类之外,还有更好的方法吗？

我正在实现一个线程池机制,我想在其中执行不同优先级的任务.我想有一个很好的机制,我可以向服务提交一个高优先级的任务,并在其他任务之前安排它.任务的优先级是任务本身的内在属性(我是否表达任务作为Callable或Runnable不重要的是我).

现在,从表面上看,我可以使用a PriorityBlockingQueue作为我的任务队列ThreadPoolExecutor,但该队列包含Runnable对象,这可能是也可能不是Runnable我提交给它的任务.而且,如果我已经提交了Callable任务,那么就不清楚它是如何映射的.

有没有办法做到这一点？我真的宁愿不为此而努力,因为我更有可能以这种方式弄错.

(旁白;是的,我知道在这样的事情中,低优先级工作可能会出现饥饿.对于有合理保证公平性的解决方案,可以加分(？!))

更新:这是我实施的哈希定时轮.如果您有提高性能和并发性的想法,请告诉我.(20月- 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);
    }
}

更新:我通过使用Hierarchical和Hashed Timing Wheels解决了这个问题.(19月- 2009年)

我正在尝试在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堆的一些堆有减少Key()和min()操作的O(1)时间,但我至少需要快速的raiseKey()和min()(或者reduceKey()和max()) .

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

假设数百万客户端在固定时间间隔内向一台服务器发送心跳,因此服务器判断客户端停止发送心跳的时间大于间隔时间.如果服务器只维护一个映射并继续迭代每个客户端以检查客户端是否超时,那将产生O(n)复杂性,这对数百万客户来说是可怕的.是否存在一些算法来制作O(log(n))复杂度,就像一些堆或二叉树来解决这样的问题？谢谢.