Я ищу способ эффективного поддержания набора значений с 1-минутного скользящего окна из заданного потока данных (~ 100 тыс. Значений/с).Скользящий оконный набор
Я ищу решение с не более чем логарифмическим временем вставки (так как основное время упорядоченного вектор значений имеет O (N))
Если не поняли ваш вопрос, это может быть сделано в постоянное время (постоянном на вставку), с круговым буфером. Выделить буфер с мощностью 2 длины больше максимального количества элементов в вашем окне. Например. max 100 тыс. значений в секунду 6 миллионов значений в минуту, поэтому распределите буфер длиной 8388608 байт. Храните абсолютный индекс в этом буфере, но вставляйте в него и удаляйте из него элементы, маскируя индекс 0x7FFFFF.
Если это * скользящее окно, я считаю, что вам нужен только буфер размером, равным размеру окна, хотя это немного изменит ситуацию (требуется смещение, а не маска). – Dukeling
Никто не будет удалять элементы через одну минуту, поэтому эта структура данных должна отслеживать значения по возрасту. – discobot
Как вы получите доступ к элементам внутри окна? Deque позволяет амортизировать добавочные и удаленные по времени и времени из фронта и обратно (соответственно) набора, но только O (n) доступ к случайным элементам в середине. – chepner