Обновление квантилей, а не перекомпонование

Question

Есть ли Java-библиотека, которая позволяет мне обновлять, а не перекомпоновать квантили большого набора данных с добавлением/удалением точек данных? Я предполагаю, что эффективные алгоритмы должны принимать постоянное время для обновления (а не функцию количества уже существующих).

Известные алгоритмы перечислены, но «не есть способ удаления точек из множества образцов:

• Colt Stream Quantiles: Это один не имеет никакого способа удаления кусок данных после добавил
• Apache Math Percentile: этот просто вычисляет квантильности массива, не удаляет данные из массива.

Вот пример проблемы: Скажем, я хочу вычислить произнесенную произвольную, но постоянную процентную скорость вентилятора набора ветряных мельниц (в качестве оценки скорости ветра). Скорости вентиляторов обновляются асинхронно каждые несколько миллисекунд. Эта библиотека должна позволять мне обновлять скорости ветра одной ветряной мельницы за один раз, не переучитывая медиану.

Answer 1

Если вы поддерживаете обновляемое упорядоченное представление данных, получение квантилей легко и эффективно, просто используя длину вашего массива. Например, если у вас есть N элементов, медиана будет в позиции N/2 и так далее. Когда вы вставляете новый элемент в свою структуру данных, это все равно будет удерживаться. Эффективность тогда просто зависит от вставки нового элемента.

Answer 2

У вас может быть несколько партий данных. Вы можете комбинировать процентили/квартили этих партий для оценки совокупности. Преимущество состоит в том, что вы можете эффективно отказаться от нескольких партий без перерасчета других партий.