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

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

我有一些代码,使用Boost累加器来跟踪滚动窗口中的均值--“滚动均值”。除了滚动平均值之外,我还想在同一个滚动窗口中跟踪最小值和最大值。
有没有办法用Boost累加器计算滚动最小值和滚动最大值?我看不出...
我已经尝试将min和max标记添加到用于rolling_mean的累加器中,但这并不能给予我想要的结果。

  1. typedef accumulator_set<uint32_t, stats<tag::rolling_mean> > rollingMeanAcc_t;

成为

  1. 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的工作示例:

  1. #include <boost/accumulators/accumulators.hpp>
  2. #include <boost/accumulators/statistics/stats.hpp>
  3. #include <boost/accumulators/statistics/rolling_count.hpp>
  4. #include <boost/accumulators/statistics/rolling_sum.hpp>
  5. #include <iostream>
  6. #include <queue>
  7. namespace boost {
  8. namespace accumulators {
  9. namespace impl {
  10. template <typename Sample>
  11. struct rolling_min : accumulator_base {
  12. typedef Sample result_type;
  13. template <typename Args>
  14. rolling_min(Args const& args){}
  15. template <typename Args>
  16. void operator()(Args const& args) {
  17. if (is_rolling_window_plus1_full(args)) {
  18. // if full remove the front element
  19. auto front_value = rolling_window_plus1(args).front();
  20. deleted_.push(front_value);
  21. }
  22. min_queue_.push(args[sample | Sample()]);
  23. }
  24. template <typename Args>
  25. result_type result(Args const& args) const {
  26. while (!deleted_.empty() && min_queue_.top() == deleted_.top()) {
  27. min_queue_.pop();
  28. deleted_.pop();
  29. }
  30. return min_queue_.top();
  31. }
  32. private:
  33. // using trick presented here
  34. // https://stackoverflow.com/a/25793796/1854834
  35. mutable std::priority_queue<Sample, std::vector<Sample>, std::greater<Sample>> min_queue_;
  36. mutable std::priority_queue<Sample, std::vector<Sample>, std::greater<Sample>> deleted_;
  37. };
  38. } // namespace impl
  39. namespace tag {
  40. struct rolling_min : depends_on<rolling_window_plus1> {
  41. typedef accumulators::impl::rolling_min<mpl::_1> impl;
  42. };
  43. } // namespace tag
  44. namespace extract {
  45. extractor<tag::rolling_min> const rolling_min = {};
  46. }
  47. using extract::rolling_min;
  48. } // namespace accumulators
  49. } // namespace boost
  50. using namespace boost::accumulators;
  51. template <typename Sample, typename Acc>
  52. void demo_print(Sample s, Acc& acc) {
  53. std::cout << "sample = " << s << ' ' << "cnt = " << rolling_count(acc) << ' ' << "sum = " << rolling_sum(acc) << ' '
  54. << "rolling min = " << rolling_min(acc) << '\n';
  55. }
  56. int main() {
  57. accumulator_set<double, features<tag::rolling_min, tag::rolling_count, tag::rolling_sum>> acc(
  58. tag::rolling_window::window_size = 3);
  59. acc(1);
  60. demo_print(1, acc);
  61. acc(2);
  62. demo_print(2, acc);
  63. acc(3);
  64. demo_print(3, acc);
  65. acc(4);
  66. demo_print(4, acc);
  67. acc(0);
  68. demo_print(0, acc);
  69. acc(5);
  70. demo_print(5, acc);
  71. acc(8);
  72. demo_print(8, acc);
  73. acc(8);
  74. demo_print(8, acc);
  75. }

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

展开查看全部

相关问题