C++ boost 的滚动最小值和滚动最大值？

Question

我有一些代码使用Boost累加器来跟踪滚动窗口的平均值——“滚动平均值”。除了滚动平均值之外，我还想跟踪同一滚动窗口中的最小值和最大值。

有没有办法用Boost累加器计算滚动最小值和滚动最大值？我没有看到办法...

我尝试将 min 和 max 标签添加到用于 moving_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 文档表示最小值和最大值是在所有样本中计算的，不限于滚动窗口。他们似乎没有提供限制或称重样品的方法。

我希望能够在滚动窗口中报告平均值/最小值/最大值。

我目前使用的是Boost版本1.48.0。我查看了最新版本（1.54.0）的文档，但没有看到其中实现的滚动最小/最大。

我找到了一种非Boost方式来跟踪滑动窗口最小值，但这似乎也不是我想要的。我不想仅仅因为它们大于/小于之前的最小值/最大值而删除值，因为这会使rolling_mean 不准确。

Answer 1

我不认为累加器可以滚动最小值/最大值。

问题非常简单：根据定义，累加器几乎只使用 O(1) 数据——它不存储正在处理的数据。它可以用 O(1) 数据维护最小值或最大值，因为当数字超出当前最小值/最大值范围时，它只是更改当前最小值/最大值。

然而，对于窗口来说，它需要准备做相反的事情：当当前最小值超出窗口时，它需要找到新的最小值——窗口中下一个最小的数字。当然，对于最大值也是如此。

现在，考虑如果（例如）输入已排序，最小值会发生什么。每次从窗口中删除一个项目时，我们都会得到不同的最小值。换句话说，累加器需要存储窗口中的所有数据以正确维持当前最小值。同样，对于输入按降序排序的最大值。

简而言之，您不能为此使用累加器。您需要存储窗口中的所有数据。

Answer 2

可能有更聪明的算法（事实上可能有），但在我的脑海中，我只是将窗口存储在循环缓冲区中并按需计算滚动最小/最大。缓存结果并在窗口更改时设置脏标志。这给出了 O(1) 累积操作和摊销 O(1) 提取操作，最坏情况为 O(K)，其中 K 是窗口的大小。

Answer 3

没有什么可以阻止您扩展 boost 累加器来实现您自己的rolling_min/rolling_max。

rolling_min 的工作示例：

#include <boost/accumulators/accumulators.hpp>
#include <boost/accumulators/statistics/stats.hpp>
#include <boost/accumulators/statistics/rolling_count.hpp>
#include <boost/accumulators/statistics/rolling_sum.hpp>
#include <iostream>
#include <queue>

namespace boost {
namespace accumulators {
namespace impl {
template <typename Sample>
struct rolling_min : accumulator_base {
    typedef Sample result_type;

    template <typename Args>
    rolling_min(Args const& args){}

    template <typename Args>
    void operator()(Args const& args) {
        if (is_rolling_window_plus1_full(args)) {
            // if full remove the front element
            auto front_value = rolling_window_plus1(args).front();
            deleted_.push(front_value);
        }
        min_queue_.push(args[sample | Sample()]);
    }
    template <typename Args>
    result_type result(Args const& args) const {
        while (!deleted_.empty() && min_queue_.top() == deleted_.top()) {
            min_queue_.pop();
            deleted_.pop();
        }

      return min_queue_.top();
    }

   private:
    // using tick presented here
    // https://stackoverflow.com/questions/25755985/do-we-have-priority-queue-which-supports-delete-operation-with-same-complexity-a
    mutable std::priority_queue<Sample, std::vector<Sample>, std::greater<Sample>> min_queue_;
    mutable std::priority_queue<Sample, std::vector<Sample>, std::greater<Sample>> deleted_;
};
}  // namespace impl

namespace tag {
struct rolling_min : depends_on<rolling_window_plus1> {
    typedef accumulators::impl::rolling_min<mpl::_1> impl;
};
}  // namespace tag

namespace extract {
extractor<tag::rolling_min> const rolling_min = {};
}
using extract::rolling_min;
}  // namespace accumulators
}  // namespace boost

using namespace boost::accumulators;

template <typename Sample, typename Acc>
void demo_print(Sample s, Acc& acc) {
    std::cout << "sample = " << s << ' ' << "cnt = " << rolling_count(acc) << ' ' << "sum = " << rolling_sum(acc) << ' '
              << "rolling min = " << rolling_min(acc) << '\n';
}
int main() {
    accumulator_set<double, features<tag::rolling_min, tag::rolling_count, tag::rolling_sum>> acc(
        tag::rolling_window::window_size = 3);

    acc(1);
    demo_print(1, acc);
    acc(2);
    demo_print(2, acc);
    acc(3);
    demo_print(3, acc);
    acc(4);
    demo_print(4, acc);
    acc(0);
    demo_print(0, acc);
    acc(5);
    demo_print(5, acc);
    acc(8);
    demo_print(8, acc);
    acc(8);
    demo_print(8, acc);
}