问C++求流数据的最大值
EN

Stack Overflow用户

提问于 2017-04-03 17:58:51

回答 3查看 319关注 0票数 1

我有一个数据流，它在随机时间间隔内产生数值。现在，我需要连续地获得在特定时间间隔内产生的流的最大值，例如100毫秒。

我天真的做法是有一个缺陷的对和一个变量的最大值。如果传入值大于最大值，我将清除deque，否则我循环遍历deque，如果- ts大于我的回溯间隔，我将忽略它，否则检查它是否大于以前的值(除非它是第一个值)。如果是这样的话，我会保存迭代器。循环结束后，我将deque删除到(不包括我的最大迭代器)并设置新的最大值。

我只是想知道是否有一种更聪明、更优雅的方法可以通过使用不同的容器来完成这个任务。理想情况下，我应该坚持使用c++标准库中的某个容器。

编辑:有人建议一个优先级队列(答案被删除)。在这种情况下，我会创建一个成双成对的堆并告诉堆按值排序(或者如果不可能，创建一个带有字段时间戳和值的结构，并添加一个>操作符)。然后每次我得到最大值，我检查它是否过期，如果是，弹出它，并采取新的最大.这比我最初的方法好吗？

编辑:值不是唯一的

c++

回答 3

Stack Overflow用户

回答已采纳

发布于 2017-04-03 21:07:58

如果数据足够小，可以很容易地适应您的CPU缓存(例如，100万float值)，那么我们都在考虑这个问题。

只需存储一个std::deque< std::pair<float, timestamp> >。

当出现新值时，请使用push_back()。
当您需要查询max元素时，请调用pop_front()，直到清除所有过期值为止。那就打电话给std::max_element()吧。

如果没有缓存丢失，它将具有与涉及priority_queue和multiset等更精细的解决方案相同(或更好)的性能。

票数 3

Stack Overflow用户

发布于 2017-04-03 18:17:02

==new update==

使用std：：对值和时间戳的(max)堆。在c++11中，我正在讨论的堆是一个std::priority_queue。如果将值类型(而不是时间戳类型)作为对的第一个元素(即

std::pair<val_t,time_t>

而不是

std::pair<time_t,val_t>

)，那么您甚至不需要自定义比较器，因为std：：结对比较将在默认情况下给出您想要的行为(优先比较pair.first，并且只在相同的情况下查看pair.second，在默认情况下使用std：：->给出对w.r.t的最大堆。(第一值类型)。

插入/推送所有新值到(max)堆中。最大的价值将永远在最上面。在轮询时，检查顶部示例的时间戳(sample.second)和now()减去最近的窗口时间。如果太老了，就把它扔掉。某些值序列会导致堆在最大值下面隐藏陈旧值。当堆超过一定大小的阈值时，将其清空到一个新的阈值中，同时过滤出过期的值。这种情况与新样品的到达率非常不成比例，因为这与最近的窗口大小有关。

感谢@chrise建议修改我过早放弃的一个好主意

==previous update==

我最初的答复只回答了问题的一部分。我建议使用max_heap (std::priority_queue，默认情况下使用std：：->最大堆)来维护最大值。这不包括最近的维修费用。您有两个独立的关注点，搜索最大成员资格和条件成员资格。更改现有堆上的成员资格规则(过期标准)将使堆失效，并给出难以根本原因的运行时错误。

相反，您可以使用一个成对列表(或deque，可能更好)，但我使用了std：：list的示例以及remove_if和一个跟踪最大值的谓词。这可以通过使用lambdas或创建函子类来实现。使用lambdas如下所示：

using sample = std::pair<unsigned,double>;
sample a{ 1,12.2 };
sample b{ 2,11.778 };
sample c{ 3,9.2 };
sample d{ 4,-2.6 };
sample e{ 5,10.1 };

std::list<sample> samples{ d,c,b,a };
cout << "list is: " << samples << endl << endl;
double maxval = -std::numeric_limits<double>::infinity();
unsigned cutoff = now() - timerange;
samples.remove_if([&maxval,cutoff](sample s) 
{
    //if older than cutoff, remove
    if (s.first < cutoff) return true;
    //otherwise, keep and update max
    maxval = std::max(maxval, s.second);
    return false;
});
cout << "max is: " << maxval << ", list is: " << samples << endl << endl;

有关完整示例，请参见http://ideone.com/O6UJPW。

使用函式类如下所示：

using sample = std::pair<unsigned,double>;
sample a{ 1,12.2 };
sample b{ 2,11.778 };
sample c{ 3,9.2 };
sample d{ 4,-2.6 };
sample e{ 5,10.1 };

std::list<sample> samples{ d,c,b,a };
cout << "original list is: " << samples << endl;

double maxval(-std::numeric_limits<double>::infinity());
//eliminate samples older than 2
using pred = PredRetainMax<sample>;
samples.remove_if(pred(now() - timerange, maxval));
cout << "max is: " << maxval << ", list is: " << samples << endl << endl;

谓词看起来如下所示

template<class T>
struct PredRetainMax;

template<class Time, class Val>
struct PredRetainMax<std::pair<Time, Val>>
{
    PredRetainMax(Time cutoff, Val& m) :_cutoff(cutoff), _max(m) {}
    bool operator()(const std::pair<Time, Val>& s)
    {
        //if older than cutoff, remove
        if (s.first < _cutoff) return true;
        //otherwise, keep and update max
        _max = std::max(_max, s.second);
        return false;
    }
    Val get() { return _max; }
private:
    Time _cutoff;
    Val& _max;
};