Раздвижные окна

Question

Я ищу способ эффективно поддерживать набор значений из 1-минутного скользящего окна из заданного потока данных (~100 тыс. Значений в секунду).

Я ищу решение с максимальным логарифмическим временем вставки (так как основной упорядоченный по времени вектор значений имеет o(n))

Answer 1

Если я не понимаю ваш вопрос, это может быть сделано в постоянное время (постоянное на вставку), с круговым буфером. Выделение буфера со степенью длины на 2 больше, чем максимальное количество элементов в вашем окне. Например, максимум 100 000 значений в секунду, 6 миллионов значений в минуту, поэтому выделите буфер длиной 8388608 байт. Сохраняйте абсолютный индекс в этом буфере, но вставляйте в него и удаляйте из него элементы, маскируя индекс с помощью 0x7FFFFF.