java - 滑动窗口 : Implementation and Performance (Java)

Question

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

我想到了一个 LinkedList 或一个 ArrayDeque - 可能后者是更好的选择，因为据我所知，插入和删除到/从任何一端对于 ArrayDeque 来说都是 O(1) 的持续努力，这是LinkedList 不是这种情况。是吗？

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

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

Answer 1

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

这要快很多倍，而且对于较短的时间间隔，结果大致相同。