为什么当我使用 std::algorithms 而不是普通循环时这段代码变慢了?
Why this code is getting slower when I use std::algorithms instead of plain loops?
我正在计算向量元素的均值和标准差。我有两个版本,我完全不明白为什么使用标准算法的版本比使用普通循环的版本慢。
两个版本都使用此结构作为 return 类型:
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
(顺便说一句,只是 typedef std::vector<double>
)。但是,我对标准算法不够熟悉,无法改进第二个版本。所以,现在我的问题是:
如何改进算法版本,使其比使用普通循环的版本更快?
我不认为这些程序是等效的。在第二个版本中(使用算法)一个新的双精度向量被填充并且还涉及额外的迭代。
你可以试试这个(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;
}
没有 lambda(未测试,可能需要一些小改动)
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;
}
我正在计算向量元素的均值和标准差。我有两个版本,我完全不明白为什么使用标准算法的版本比使用普通循环的版本慢。
两个版本都使用此结构作为 return 类型:
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
(顺便说一句,只是 typedef std::vector<double>
)。但是,我对标准算法不够熟悉,无法改进第二个版本。所以,现在我的问题是:
如何改进算法版本,使其比使用普通循环的版本更快?
我不认为这些程序是等效的。在第二个版本中(使用算法)一个新的双精度向量被填充并且还涉及额外的迭代。
你可以试试这个(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;
}
没有 lambda(未测试,可能需要一些小改动)
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;
}