минимальный каток и максимальная скорость прокатки для повышения C++?

Question

У меня есть код, в котором используется аккумулятор 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 documentation говорит, что min и max вычисляются по всем образцам, не ограничиваясь прокатным окном. Похоже, что они не обеспечивают способ ограничения или веса образцов.

Хотелось бы иметь возможность сообщать среднее/минимальное/максимальное значение в поперечном окне.

В настоящее время я использую Boost версии 1.48.0. Я просмотрел документацию для последней версии (1.54.0) и не вижу, чтобы ее выполняли min/max.

Я нашел способ не-Boost для отслеживания sliding window minimum, но это, похоже, не то, что я хочу. Я не хочу удалять значения только потому, что они больше/меньше, чем предыдущий мин/макс, так как это сделало бы roll_mean неточным.

Answer 1

Я не думаю, что аккумулятор может выполнять свертывание min/max.

Проблема довольно проста: накопитель в значительной степени по определению использует только данные O (1) - он не хранит обрабатываемые данные. Он может поддерживать мин или макс с данными O (1), поскольку он просто меняет ток min/max, когда число выходит за пределы диапазона min/max.

Для окна, однако, оно должно быть подготовлено к противоположному: когда текущий мин выходит из окна, ему необходимо найти новый минимум - следующее наименьшее число в окне. Точно так же для максимума, конечно.

Теперь рассмотрим, что происходит с минимумом, если (например) сортировка ввода. Каждый раз, когда элемент удаляется из окна, мы получаем другое минимальное значение. Другими словами, аккумулятору необходимо будет хранить все данные в окне, чтобы поддерживать текущий минимум должным образом. Аналогично, для максимума с сортировкой в ​​порядке убывания.

Одним словом, вы не можете использовать аккумулятор для этого. Вам нужно сохранить все данные в окне.

Answer 2

Может быть, более умный алгоритм (на самом деле, вероятно, есть), но с верхней части моей головы я бы просто сохранил окно в круговом буфере и вычислил скорость min/max по требованию. Загрузите результат и установите грязный флаг, когда окно изменится. Это дает операцию накопления O (1) и операцию извлечения O (1) с наихудшим случаем O (K), где K - размер окна.