我想实现一个非常简单的滑动窗口。换句话说，我将拥有某种列表，其中对象从该列表的右端插入而从左端删除。在每次插入中，先前的对象向左移动一个索引。当列表中充满对象时，在从右端开始的每次插入中，都会从左端删除一个对象(当然，以前的对象通常也会向左移动一个索引)。
我想到的是LinkedList或ArrayDeque-也许后者是一个更好的选择，因为据我所知，对ArrayDeque进行插入和从任一端插入/从两端移除都是持续工作O(1)，情况并非如此一个LinkedList。那正确吗？
此外，我想提出以下问题:在插入一个新对象时，向左移动存储在滑动窗口中的所有先前对象对于像我这样的具有100,000个或什至1,000,000个对象的大型滑动窗口来说，处理量很大。是否有其他数据结构可能在我的应用程序中表现更好？
注意:我将术语“滑动窗口”用于要实现的对象，也许还有其他一些术语可以更好地对其进行描述，但是从以上描述中我很清楚我想做什么。
最佳答案
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);
}
这快了好几倍，而且间隔很短，结果也差不多。