6

我正在用 Java 实现事件流上的滑动窗口。所以我想要一个允许我执行以下操作的数据结构:

  1. 当新事件发生时添加到数据结构的末尾;

  2. 处理旧事件时从数据结构的开头删除;

  3. 获得对数据结构元素的标准随机访问(size(), );get(i)一般来说,典型的列表“读取”操作;

  4. 对上述所有操作都是有效的;

  5. 是无界的。

不需要其他访问权限。并且不需要线程安全。

我目前正在使用ArrayList执行此操作,以启动和运行。但我想要更有效的东西;remove(0)方法 (2. above)对于ArrayList.

数字 1. 和 2. 是标准的Queue式操作。但是,QueueJDK 中的实现(例如ArrayDeque)不允许get(i)in 3.

所以,我想知道是否有任何有这样的实现,并且适合商业用途。

如果没有,我想我会求助于自己写...

4

8 回答 8

4

我遇到了这个问题,并尝试通过复制源代码ArrayDeque并添加以下内容来解决它:

E get(index){ return elements[(head + index) % size];}
于 2011-11-16T09:04:05.373 回答
4

似乎是循环缓冲区的任务- 只要队列具有固定容量就可以了。不过,我不知道任何标准实现。但这里有一个很好的食谱来制作你自己的

于 2009-11-05T18:41:16.050 回答
3

如果你有一个足够大的数组,你可以用一个基本数组来实现一个队列,并且只使用一个索引作为列表的头部,并使用 mod 运算符,这样你就可以在需要时进行环绕。

所以,你基本上有一个支持插入和删除功能的循环数组。

更新:

将数组复制到更大的数组是一种快速操作,因此在接近末尾时,可能只需将大小翻倍,然后复制数组,作为插入的一个步骤。总的来说,您仍然可以非常快速地访问,因为规范不应该是增加和复制。

于 2009-11-05T18:42:16.430 回答
2

事件进出此队列的速度有多快?

一方面,您可以拥有一个“足够大”的循环缓冲区。

虽然它在技术上是“有界的”,但您可以通过根据需要增长它来使其“无界”。

出于同样的原因,当它“安静”时,您可以在整体容量方面“缩小”它。

但是,对于许多应用程序来说,100、1000 甚至 10000 项容量的循环缓冲区实际上是无界的。

于 2009-11-05T18:57:10.003 回答
1

只是把它扔在那里作为自己滚动的替代方案,所以请谨慎对待:取决于您需要随机访问的频率以及您需要的get(i)性能(以及您的队列大小通常有多大),ArrayDeque.toArray()[i]当你需要访问一个元素时,你总是可以使用。对于小队列大小和偶尔toArray()使用System.arraycopy()应该非常快的幕后用途。将有助于理解为什么需要随机访问队列以及需要的频率——没有它可能有不同的方法来实现你的算法。

于 2009-11-05T19:00:10.777 回答
1

我能想到的唯一能实现这样一个接口的库是LinkedList,但坦率地说,我不确定性能特征是什么。

于 2009-11-05T18:32:39.157 回答
1

如果它确实必须是无界的,那么 ConcurrentSkipListMap 之类的东西可能很有用,如果您为每个事件分配一个递增序列以用作映射中的键。它提供了 pollFirst/LastEntry 等方法。如果您可以牺牲它的无限特性,那么您可能需要一个环形缓冲区。

于 2009-11-05T19:46:48.773 回答
0

二项式堆可以有 O(1) 分期插入和 O(log n) 分期删除 min;我相信它也可以有 O(log**2 n) 摊销随机访问。Queue-push 会将元素插入到堆中,并以连续的整数作为键。

使用 rbtree,您可以对所有插入、删除最小和随机访问进行 O(log n) 悲观的队列推送。那是因为树将有一组连续的整数作为键,队列的第 k 个元素将是树中具有第 k 个键的元素。

于 2009-11-05T19:37:06.530 回答