Вычисление процентилей с использованием фиксированного объема памяти

У меня есть поток значений int, достигающих определенной скорости. Каждые 5 минут я хотел бы вычислить некоторые процентили из значений и начать все заново.

Проблема: я не хочу тратить слишком много памяти, поэтому я бы хотел сохранить только несколько килобайт для значений. Если мой буфер не заполняется в течение 5 минут, я могу отлично вычислить процентили. Однако, если буфер заполняется, я хотел бы начать отбрасывать некоторые значения (возможно, используя выборку коллектора и случайное выселение, как предлагается здесь - Percentiles of Data Data Capture). К сожалению, я не могу найти решение, которое хорошо работает в обоих сценариях - если буфер не заполнен, я не хочу вытеснять или игнорировать значения, и как только он заполняется, и я начинаю выходить, я неизменно внедряю предвзятость.

1 ответ

ОК, я думаю, я понял это - я могу использовать алгоритм R для равномерного выбора подмножества фиксированного размера входящих элементов. Затем я могу вычислить процентили из этого подмножества.

licensed under cc by-sa 3.0 with attribution.