滚动最小值和滚动最大值为C++提升？

Question

我有一些代码使用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 文档说明在所有样本中计算最小值和最大值,不限于滚动窗口.它们似乎没有提供限制或加重样品的方法.

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

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

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

Answer 1

我不认为累加器可以做最小/最大滚动.

问题非常简单:根据定义,累加器只使用O(1)数据 - 它不存储正在处理的数据.它可以用O(1)数据保持最小值或最大值,因为它只是在数字超出当前最小值/最大值范围时改变当前最小值/最大值.

但是,对于一个窗口,它需要做好相反的准备:当当前min离开窗口时,它需要找到新的最小值 - 窗口中的下一个最小数字.当然,同样最大化.

现在,考虑输入被排序的最小值(例如).每次从窗口中删除项目时,我们都会获得不同的最小值.换句话说,累加器需要将所有数据存储在窗口中以适当地保持当前最小值.同样,最大输入按降序排序.

简而言之,您不能使用累加器.您需要在窗口中存储所有数据.