1

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

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

4

1 回答 1

1

除非我误解了您的问题，否则可以使用循环缓冲区在恒定时间（每次插入恒定）内完成。分配一个长度为 2 的幂的缓冲区，该长度大于窗口中最大元素数。例如，每秒最多 100k 个值每分钟 600 万个值，因此分配一个长度为 8388608 字节的缓冲区。在此缓冲区中保留一个绝对索引，但插入其中，并通过使用 0x7FFFFF 屏蔽索引从中删除元素。

于 2013-05-13T15:57:17.363 回答