滑动窗口:实现和性能(Java)

Question

我想实现一个非常简单的滑动窗口.换句话说,我会有一些列表,其中的对象从该列表的右端插入并从左端删除.在每次插入中,先前的对象被左移一个索引.当列表被对象填充时,在每次从右端插入时,对象将从左端删除(并且前一个对象当然会像往常一样左移一个索引).

我记得有一个LinkedList或一个ArrayDeque - 可能后者是一个更好的选择,因为据我所知,插入和从任一端移除是对ArrayDeque的持续努力O(1),但事实并非如此对于LinkedList.是对的吗？

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

注意:我使用术语"滑动窗口"来表示我想要实现的内容,也许还有一些其他术语可以更好地描述它,但我认为从上面的描述可以清楚地知道我想做什么.

Answer 1

ArrayDeque做你想要的.它不会移动元素.它移动开始和结束的索引.添加元素时,结束计数器会移动,当您删除元素时,启动计数器会移动.

ArrayDeque的一个优点是它可以使用更少的内存并创建垃圾.在不利方面,它具有固定的最大尺寸.LinkedList增长和缩小.

BTW如果你想要一个轻量级滑动窗口或一些值的平均值,指数加权移动平均值要便宜得多,因为你只需要记录两个值,即前一次和最后一次.

例如

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

这要快很多倍,而且间隔时间短得多.