优先级队列,允许有效的优先级更新？

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

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

1> David Norman..：

---

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

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

每隔一秒扫描一次哈希表,任何已经很长时间的任务,比如说.75秒,都会被移动到优先级队列.优先级队列应该总是很小并且易于处理.这假设一秒钟远小于您要查找的超时时间.

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

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

---

这很有意义,因为它涵盖了大多数情况下的哈希表,因此每条消息的更新/取消时间为O(1).如果正常响应时间范围从0到60秒,我可以创建更多的哈希表.谢谢!

2> A. Rex..：

---

据我所知(我写了一篇关于新优先级队列的文章,其中也回顾了过去的结果),没有优先级队列实现获得斐波纳契堆的界限,以及常数时间增加键.

从字面上理解这个问题有一个小问题.如果你可以在O(1)中获得增加键,那么你可以在O(1)中删除 - 只需将键增加到+无穷大(你可以使用一些标准的摊销技巧处理充满大量+无穷大的队列) ).但是如果find-min也是O(1),那意味着delete-min = find-min + delete变为O(1).这在基于比较的优先级队列中是不可能的,因为排序绑定意味着(插入所有内容,然后一个一个地删除)

n*insert + n*delete-min> n log n.

这里的要点是,如果您希望优先级队列支持O(1)中的增加键,那么您必须接受以下处罚之一:

不是基于比较.实际上,这是解决问题的好方法,例如vEB树.

接受O(log n)表示插入,接受O(n log n)表示make-heap(给定n个起始值).这很糟糕.

接受O(log n)的find-min.如果你从未真正做过 find-min(没有附带的删除),这是完全可以接受的.

但是,据我所知,没有人做过最后一个选择.我一直认为这是在一个非常基本的数据结构领域取得新成果的机会.

---

你有纸的链接吗？

3> trustin..：

---

使用哈希定时轮 - 谷歌'哈希分层定时轮'获取更多信息.这是对这里人们所作答案的概括.我更喜欢具有大轮尺寸的散列定时轮到分级定时轮.

4> Die in Sente..：

---

哈希和O(logN)结构的某些组合应该按照您的要求进行.

我很想用你分析问题的方式来狡辩.在上面的评论中,你说

因为更新将非常频繁地发生.假设我们每个连接发送M个消息,那么总时间变为O(MNlogN),这是非常大的. - Trustin Lee(6小时前)

这是完全正确的.但是我认识的大多数人都会专注于每条消息的成本,理论上当你的应用程序有越来越多的工作要做时,显然它需要更多的资源.

因此,如果您的应用程序同时打开了十亿个套接字 (真的可能吗？),则每个消息的插入成本仅为60左右.

我敢打赌,这是不成熟的优化:你还没有用CodeAnalyst或VTune这样的性能分析工具来测量系统中的瓶颈.

无论如何,一旦你决定没有一个结构可以做你想要的东西,并且你想要不同算法的优点和缺点的某种组合,可能有无数种方法可以做你所要求的.

一种可能性是将套接字域N划分为一些大小为B的桶,然后将每个套接字散列到这些(N/B)桶中的​​一个桶中.在那个桶中是一个堆(或其他)具有O(log B)更新时间.如果N的上限没有提前修复,但可以变化,那么你可以动态创建更多的桶,这会增加一点复杂性,但肯定是可行的.

在最坏的情况下,看门狗定时器必须搜索(N/B)队列以进行到期,但我认为看门狗定时器不需要以任何特定顺序杀死空闲套接字! 也就是说,如果10个套接字在最后一个时间片中空闲,那么它不必搜索那个超时的域,处理它,然后找到那个超时的套接字等等.它只是必须扫描(N/B)一组桶并枚举所有超时.

如果您对线性数组桶不满意,可以使用队列的优先级队列,但是您希望避免在每条消息上更新该队列,否则您就会回到起始位置.相反,定义一些小于实际超时的时间.(比如,3/4或7/8)并且只有当最长时间超过该队列时才将低级队列放入高级队列.

并且存在说明显而易见的风险,您不希望您的队列按经过时间键入.键应该是开始时间.对于队列中的每个记录,必须不断更新已用时间,但每个记录的开始时间不会更改.