我有一些代码,使用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的方法来跟踪sliding window minimum,但这似乎也不是我想要的。我不想仅仅因为值大于/小于之前的最小值/最大值就删除它们,因为这会使rolling_mean不准确。
3条答案
按热度按时间evrscar21#
我不认为累加器可以做一个滚动的最小/最大值(至少不违反许多人对“累加器”的理解,尽管我想我可能误解了人们对它的理解)。
问题很简单:我想大多数人都希望累加器只使用O(1)的数据--它不存储正在处理的数据。它可以用O(1)的数据来维护最小值或最大值,因为当一个数字福尔斯在当前最小值/最大值的范围之外时,它只是改变当前最小值/最大值。
然而,对于一个窗口,它需要准备做相反的事情:当当前最小值超出窗口时,它需要找到新的最小值--窗口中的下一个最小值。当然,最大值也是如此。
现在,考虑一下如果(例如)输入被排序,最小值会发生什么。每次从窗口中删除一个项目时,我们都会得到一个不同的最小值。换句话说,累加器需要存储窗口中的所有数据,以正确地保持当前最小值。同样,对于输入按降序排序的最大值。
简而言之,您需要将所有数据存储在窗口中。
另一方面,如果你认为它仍然是一个累加器(这可能是合理的),它是相当简单的。当然,你可以用一些东西来完成这项工作,至少使用你通常期望的累加器接口。
wnrlj8wa2#
可能有一个更聪明的算法(事实上可能有),但在我的脑海中,我会简单地将窗口存储在一个循环缓冲区中,并按需计算滚动的最小值/最大值。缓存结果并在窗口更改时设置脏标志。这给出了O(1)的累加操作和O(1)的摊销提取操作,最坏情况为O(K),其中K是窗口的大小。
mzaanser3#
没有什么能阻止你扩展boost函数来实现你自己的rolling_min/rolling_max。
rolling_min的工作示例:
测试d使用c++17与gcc版本9.4.0(Ubuntu 9.4.0- 1ubuntu 1 ~20.04.1)