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

Question

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

有没有一种方法可以使用 Boost 累加器计算滚动最小值和滚动最大值？我看不到办法...

我已经尝试将最小和最大标签添加到用于 rolling_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说最小值和最大值是在所有样本中计算的，不限于滚动窗口。它们似乎没有提供限制或加权样本的方法。

我希望能够报告整个滚动窗口的平均值/最小值/最大值。

我目前使用的是 Boost 版本 1.48.0。我查看了最新版本 (1.54.0) 的文档，但没有看到那里实现了滚动最小/最大值。

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

Answer 1

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

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

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

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

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