c++ rolling min和rolling max是什么意思?

bq3bfh9z  于 2023-10-21  发布在  其他
关注(0)|答案(3)|浏览(163)

我有一些代码,使用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不准确。

evrscar2

evrscar21#

我不认为累加器可以做一个滚动的最小/最大值(至少不违反许多人对“累加器”的理解,尽管我想我可能误解了人们对它的理解)。
问题很简单:我想大多数人都希望累加器只使用O(1)的数据--它不存储正在处理的数据。它可以用O(1)的数据来维护最小值或最大值,因为当一个数字福尔斯在当前最小值/最大值的范围之外时,它只是改变当前最小值/最大值。
然而,对于一个窗口,它需要准备做相反的事情:当当前最小值超出窗口时,它需要找到新的最小值--窗口中的下一个最小值。当然,最大值也是如此。
现在,考虑一下如果(例如)输入被排序,最小值会发生什么。每次从窗口中删除一个项目时,我们都会得到一个不同的最小值。换句话说,累加器需要存储窗口中的所有数据,以正确地保持当前最小值。同样,对于输入按降序排序的最大值。
简而言之,您需要将所有数据存储在窗口中。
另一方面,如果你认为它仍然是一个累加器(这可能是合理的),它是相当简单的。当然,你可以用一些东西来完成这项工作,至少使用你通常期望的累加器接口。

wnrlj8wa

wnrlj8wa2#

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

mzaanser

mzaanser3#

没有什么能阻止你扩展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 trick presented here
    // https://stackoverflow.com/a/25793796/1854834
    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);
}

测试d使用c++17与gcc版本9.4.0(Ubuntu 9.4.0- 1ubuntu 1 ~20.04.1)

相关问题