为什么这段代码这么慢？

Question

所以我有这个用来计算统计数据的函数(min/max/std/mean).现在的问题是它通常在10,000乘15,000矩阵上运行.矩阵存储vector<vector<int> >在类中.现在创建和填充所述矩阵变得非常快,但是当它归结为统计部分时,它变得非常缓慢.

例如,为了一次读取地理基准的所有像素值,一个像素大约需要30秒.(它涉及大量复杂的数学运算,以便将像素值正确地映射到相应的点),以计算整个矩阵的统计数据,大约需要6分钟.

void CalculateStats()
{
    //OHGOD
    double new_mean = 0;
    double new_standard_dev = 0;

    int new_min = 256;
    int new_max = 0;

    size_t cnt = 0;
    for(size_t row = 0; row < vals.size(); row++)
    {
        for(size_t col = 0; col < vals.at(row).size(); col++)
        {
            double mean_prev = new_mean;
            T value = get(row, col);
            new_mean += (value - new_mean) / (cnt + 1);
            new_standard_dev += (value - new_mean) * (value - mean_prev);

            // find new max/min's
            new_min = value < new_min ? value : new_min;
            new_max = value > new_max ? value : new_max;
            cnt++;
        }
    }

    stats_standard_dev = sqrt(new_standard_dev / (vals.size() * vals.at(0).size()) + 1);
    std::cout << stats_standard_dev << std::endl;
}

我在这做些可怕的事吗？

编辑

为了回应评论,T将是一个int.

编辑2

我修复了我的std算法,这是最终产品:

void CalculateStats(const std::vector<double>& ignore_values)
{
    //OHGOD
    double new_mean = 0;
    double new_standard_dev = 0;

    int new_min = 256;
    int new_max = 0;

    size_t cnt = 0;

    int n = 0;
    double delta = 0.0;
    double mean2 = 0.0;

    std::vector<double>::const_iterator ignore_begin = ignore_values.begin();
    std::vector<double>::const_iterator ignore_end = ignore_values.end();

    for(std::vector<std::vector<T> >::const_iterator row = vals.begin(), row_end = vals.end();  row != row_end; ++row)
    {
        for(std::vector<T>::const_iterator col = row->begin(), col_end = row->end(); col != col_end; ++col)
        {
            // This method of calculation is based on Knuth's algorithm.
            T value = *col;
            if(std::find(ignore_begin, ignore_end, value) != ignore_end)
                continue;
            n++;
            delta = value - new_mean;
            new_mean = new_mean + (delta / n);
            mean2 = mean2 + (delta * (value - new_mean));

            // Find new max/min's.
            new_min = value < new_min ? value : new_min;
            new_max = value > new_max ? value : new_max;
        }
    }
    stats_standard_dev = mean2 / (n - 1);
    stats_min = new_min;
    stats_max = new_max;
    stats_mean = new_mean;

这仍然需要大约120-130秒,但这是一个巨大的改进:)!

Answer 1

您是否尝试过编写代码？

你甚至不需要花哨的探查器.只需在那里粘贴一些调试时序语句.

我告诉你的任何事情都只是一个有根据的猜测(可能是错误的)

由于您访问矢量内容的方式,您可能会遇到大量缓存未命中.您可能希望将一些结果缓存到size()但我不知道这是否是问题.

Answer 2

我只是简介它.90%的执行时间在这一行:

new_mean + =(value - new_mean)/(cnt + 1);

Answer 3

你应该计算第一个循环中的值,最小值,最大值和计数的总和,然后通过除以总和/计数来计算一个操作中的平均值,然后在第二个循环中计算std_dev的总和

那可能会快一点.

Answer 4

我发现的第一件事是你vals.at(row).size()在循环中进行评估,显然,这不应该提高性能.它也适用于vals.size(),但当然内循环更糟.如果vals是向量的向量,最好使用迭代器或者至少保留外向量的引用(因为get()使用indices参数肯定会耗费相当长的时间).

这段代码样本应该用来说明我的意图;-)

for(TVO::const_iterator i=vals.begin(),ie=vals.end();i!=ie;++i) {
    for(TVI::const_iterator ii=i->begin(),iie=i->end();ii!=iie;++ii) {
        T value = *ii;
        // the rest
    }
}