мин. прокатки и максимум прокатки для C ++ boost?
У меня есть некоторый код, который использует аккумулятор Boost для отслеживания среднего значения по скользящему окну — «скользящее среднее». В дополнение к скользящему среднему значению я хотел бы отслеживать минимальное и максимальное значения в этом же окне.
Есть ли способ вычислить минимальную и максимальную частоту вращения с помощью аккумулятора Boost? Я не вижу пути …
Я попытался добавить теги min и max к аккумулятору, который используется для roll_mean, но это не дает мне того, что я хочу.
typedef accumulator_set<uint32_t, stats<tag::rolling_mean> > rollingMeanAcc_t;
становится
typedef accumulator_set<uint32_t, stats<tag::rolling_mean,tag::min,tag::max> > rollingMeanAcc_t;
Однако предоставленные здесь минимальное и максимальное значения рассчитываются по всему аккумулятору, а не ограничиваются тем же скользящим окном, что и среднее значение.
Повышение документация говорит, что мин и макс вычисляются через все образцы, не ограничивающиеся окном прокрутки. Они, по-видимому, не обеспечивают способ ограничения или взвешивания образцов.
Я хотел бы иметь возможность сообщать среднее / мин / макс по всему скользящему окну.
Я в настоящее время использую Boost версии 1.48.0. Я посмотрел на документацию для последней версии (1.54.0) и не вижу, реализован там скользящий мин / макс.
Я нашел не-Boost способ отследить минимум скользящего окна, но это тоже не то, чего я хочу. Я не хочу удалять значения только потому, что они больше / меньше, чем предыдущий мин / макс, так как это может привести к неточности roll_mean.
Решение
Я не думаю, что аккумулятор может делать вращение мин / макс.
Проблема довольно проста: аккумулятор по определению использует только данные O (1) — он не хранит обрабатываемые данные. Он может поддерживать минимальное или максимальное значение с данными O (1), потому что он просто меняет текущий минимум / максимум, когда число выходит за пределы диапазона текущего минимального / максимального значения.
Для окна, однако, он должен быть готов поступить наоборот: когда текущий минимум выходит за пределы окна, ему нужно найти новый минимум — следующее наименьшее число в окне. Точно так же для максимума, конечно.
Теперь рассмотрим, что происходит с минимумом, если (например) вход отсортирован. Каждый раз, когда элемент удаляется из окна, мы получаем другое минимальное значение. Другими словами, аккумулятор должен хранить все данные в окне, чтобы правильно поддерживать текущий минимум. Аналогично, для максимума с входом, отсортированным в порядке убывания.
Короче говоря, вы не можете использовать аккумулятор для этого. Вам нужно хранить все данные в окне.
Другие решения
Может быть, есть более умный алгоритм (на самом деле, вероятно, так и есть), но, не смотря на это, я бы просто сохранил окно в круговом буфере и вычислил скользящий минимум / максимум по требованию. Кэшируйте результат и устанавливайте грязный флаг при изменении окна. Это дает операцию накопления O (1) и операцию извлечения амортизированного O (1) с наихудшим случаем O (K), где K — размер окна.