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