5

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

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

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

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

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

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

4

2 回答 2

7

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

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

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

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

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

于 2013-08-09T18:23:34.390 回答
0

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

于 2013-08-22T00:09:20.717 回答