Possible Duplicate:
C#. Need to optimise counting positive and negative values




我需要最大化以下功能的速度:


一种。传入一个值。value具有2个属性-int值和较长的时间戳记(以刻度为单位)。
b。需要计算以前存储的小于1毫秒(当前值)的值。
C。需要分别计算负数和正数。
d。我只需要知道是否有10个neg或pos值。我不需要保留任何其他有关值的知识。


我认为-分别为pos和neg实施2个环形数组,用0跟踪过期的pos.neg计数来替换过期的数组。

有什么想法吗?

最佳答案

维持2个缓冲区以保持正负与负负分开听起来很痛苦且效率低下。

取而代之的是,您可以使用一个包含所有值的缓冲区,并使用std::accumulate计算正数和负数。如果从所有元组的集合开始(每个元组都有一个年龄和一个值),则可以按照年龄对集合进行排序,找到最后一个小于等于1 ms的元素,然后使用从accumulate到该点。这是一些演示最后一点的代码:

#include <algorithm>
#include <numeric>
#include <iterator>
#include <vector>
#include <string>
#include <ctime>
using namespace std;

struct Counter
{
    Counter(unsigned pos=0, unsigned neg=0) : pos_(pos), neg_(neg) {};
    unsigned pos_, neg_;
    Counter& operator+(int n)
    {
        if( n < 0 )
            ++neg_;
        else if( n > 0 )
            ++pos_;
        return * this;
    }
};

int main()
{
    srand((unsigned)time(0));

    vector<int> vals;
    generate_n(back_inserter(vals), 1000, []()
    {
        return (rand() / (RAND_MAX/40)) - 20;
    });

    Counter cnt = accumulate(vals.begin(), vals.end(), Counter());
}


如果按年龄对集合进行排序,然后搜索最后一个符合条件的条目的排序结果听起来效果不佳,则可以使用begin()而不是for_each_if并仅对整个集合进行一次迭代。 accumulate不是标准库的一部分,但它是easy enough to write。如果您不想编写自己的for_each_if,也很好。您可以简单地对累加器进行一些调整,以免累加过旧的元素:

#include <algorithm>

#include <numeric>
#include <iterator>
#include <vector>
#include <string>
#include <ctime>
using namespace std;

struct Tuple
{
    int val_;
    unsigned age_;
};

struct Counter
{
    Counter(unsigned pos=0, unsigned neg=0) : pos_(pos), neg_(neg) {};
    unsigned pos_, neg_;
    Counter& operator+(const Tuple& tuple)
    {
        if( tuple.age_ > 1 )
            return * this;

        if( tuple.val_ < 0 )
            ++neg_;
        else if( tuple.val_ > 0 )
            ++pos_;

        return * this;
    }
};

int main()
{
    srand((unsigned)time(0));

    vector<Tuple> tuples;
    generate_n(back_inserter(tuples), 1000, []() -> Tuple
    {
        Tuple retval;
        retval.val_ = (rand() / (RAND_MAX/40)) - 20;
        retval.age_ = (rand() / (RAND_MAX/5));
        return retval;
    });

    Counter cnt = accumulate(tuples.begin(), tuples.end(), Counter());
}

关于c++ - 提供优化算法以处理带有时间戳记的值,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/7714685/

10-11 23:01
查看更多