滑动窗口集

Question

我正在寻找一种方法来有效地维护来自给定数据流的1分钟滑动窗口中的一组值(~100k值/秒)。

我正在寻找最多具有对数插入时间的解决方案(因为值的基本时间有序向量具有o(n))

Answer 1

除非我误解了你的问题，否则这可以用循环缓冲区在固定的时间内完成(每次插入都是固定的)。使用比窗口中元素的最大数量大2倍的长度来分配缓冲区。例如，每秒最多100k个值，每分钟600万个值，因此分配一个8388608字节长的缓冲区。在此缓冲区中保留一个绝对索引，但将其插入其中，并通过使用0x7FFFFF掩码索引来删除其中的元素。