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

Question

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

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

Answer 1

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