当我使用std :: algorithms而不是plain循环时,为什么这段代码会变慢？

Question

我正在计算向量元素的均值和标准差.我有两个版本,我很困惑为什么使用标准算法的版本比使用普通循环的版本慢.

两个版本都使用此结构作为返回类型:

struct MeanAndSigma {
    double mean;
    double sigma;
};

带循环的版本是这样的:

MeanAndSigma getMeanAndSigma(const DVector& v){
    MeanAndSigma ms;
    ms.mean = 0;
    for (int i=0;i<v.size();++i){ms.mean += v[i];}
    ms.mean = ms.mean / v.size();
    double sqsum = 0;
    for (int i=0;i<v.size();++i){sqsum += (v[i]-ms.mean)*(v[i]-ms.mean);}
    ms.sigma = std::sqrt(sqsum / (v.size()-1));   
    return ms;
}

而算法的那个:

MeanAndSigma getMeanAndSigma2(const DVector& v){
    MeanAndSigma ms;
    ms.mean = std::accumulate(v.begin(),v.end(),0.0) / v.size();
    DVector diff(v.size());
    std::transform(v.begin(),v.end(),diff.begin(),
             std::bind2nd(std::minus<double>(), ms.mean));
    double sqsum = std::inner_product(diff.begin(),diff.end(),diff.begin(),0.0);
    ms.sigma = std::sqrt(sqsum / (v.size()-1));
    return ms;
}

当我使用带有10k元素的向量测量每10k调用的时间时,对于带有循环的版本,我得到~2.0秒,对于具有算法的版本,我得到~3.2秒.为什么是这样？

我已经比较了cpu时间和实时,但似乎两个都在单个cpu上运行(如预期的那样).我在使用算法时做了一些愚蠢的错误吗？

编辑:我没有声称,这两个版本是等价的.不过我原本预计第二个版本会更快.正如在评论和答案中所指出的那样,第二个版本对元素使用额外的迭代和额外的迭代DVector(这只是一个btw typedef std::vector<double>).但是,我对标准算法不够熟悉,无法改进第二版.那么,现在我的问题是:

如何使用算法改进版本比使用普通循环的版本更快？

Answer 1

我不认为这些程序是等价的.在第二个版本(使用算法)中,正在填充新的双精度矢量,并且还涉及额外的迭代.

你可以尝试这个(c ++ 11版本),它相当于第一个版本.我没有尝试过运行它,它应该有一些小的改动.

MeanAndSigma getMeanAndSigma2(const DVector& v){
    MeanAndSigma ms;
    ms.mean = std::accumulate(v.begin(),v.end(),0.0) / v.size();
    double sqsum = std::accumulate(v.begin(),v.end(),
       [ms](double sum, double ve){ return sum + (ve-ms.mean)*(ve-ms.mean);}
    );
    ms.sigma = std::sqrt(sqsum / (v.size()-1));
    return ms;
}

没有lambdas(未测试,可能需要一些小的改动)

class DiffSquare
{
    public:
        DiffSquare(double m) : _m(m) {}
        double operator()(double sum, double e)
        {
            return sum + (e - _m) * (e - _m);   
        }
    private:
        double _m;
};

MeanAndSigma getMeanAndSigma2(const DVector& v) {
    MeanAndSigma ms;
    ms.mean = std::accumulate(v.begin(),v.end(),0.0) / v.size();
    DiffSquare diff_square(ms.mean);
    double sqsum = std::accumulate(v.begin(),v.end(),
        0.0,
        diff_square
    );
    ms.sigma = std::sqrt(sqsum / (v.size()-1));
    return ms;
}