3

我想实现一个非常简单的滑动窗口。换句话说，我将有某种列表，其中包含从该列表的右端插入并从左端删除的对象。在每次插入中，先前的对象都会左移一个索引。当列表被对象填充时，在从右端每次插入时，都会从左端删除一个对象（当然，之前的对象将像往常一样左移一个索引）。

我想到的是 LinkedList 或 ArrayDeque - 可能后者是更好的选择，因为据我所知，对于 ArrayDeque，插入和删除到/从任一端都是持续的努力 O(1)，但事实并非如此对于链表。那正确吗？

此外，我想问以下问题：当我插入一个新对象时，左移存储在滑动窗口中的所有先前对象对于像我这样具有 100,000 甚至 1,000,000 个对象的大型滑动窗口来说是处理密集型的。是否有任何其他数据结构可能在我的应用程序中表现更好？

注意：我使用术语“滑动窗口”来表示我想要实现的功能，也许还有其他一些术语可以更好地描述它，但我认为从上面的描述中我想清楚我想要做什么。

4

2 回答 2

5

ArrayDeque 做你想做的事。它不会移动元素。它移动开始和结束位置的索引。添加元素时，结束计数器移动，删除元素时，开始计数器移动。

ArrayDeque 的一个优点是它可以使用更少的内存并且确实会产生垃圾。不利的一面是，它有一个固定的最大尺寸。LinkedList 增长和缩小。

顺便说一句，如果您想要一个轻量级的滑动窗口或某些值的平均值，那么指数加权移动平均线要便宜得多，因为您只需要记录两个值，即上一次和最后一次。

例如

double last = 0;
long lastTime = 0;
double halfLife = 60 * 1000; // 60 seconds for example.

public static double ewma(double sample, long time) {
    double alpha = Math.exp((lastTime - time) / halfLife);
    lastTime = time;
    return last = sample * alpha + last * (1 - alpha); 
}

或者你可以近似这个以避免调用 Math.exp

public static double ewma(double sample, long time) {
    long delay = time - lastTime
    double alpha = delay >= halfLife ? 1.0 : delta / halfLife;
    lastTime = time;
    return last = sample * alpha + last * (1 - alpha); 
}

这要快很多倍，并且在短时间间隔内会产生大致相同的结果。

于 2014-02-25T22:32:49.650 回答
0

你说的是队列吗？看一下java.util.LinkedListimplementation，因为它实现了Queue接口。同样LinkedList，push 和 pop 的复杂度都是 O(1)，但 get 的复杂度是 O(N)。

编辑：这是 LinkedList 的 add 方法的核心：

Link<ET> next = link.next;
Link<ET> newLink = new Link<ET>(object, link, next);
link.next = newLink;
next.previous = newLink;
link = newLink;
lastLink = null;
pos++;
expectedModCount++;
list.size++;
list.modCount++;
于 2014-02-25T22:20:48.457 回答