Perché questo codice diventa più lento quando utilizzo std :: algorithms invece di plain loop?

Question

Sto calcolando la media e la deviazione standard degli elementi di un vettore. Ho due versioni di questo e sono completamente perplesso sul motivo per cui la versione che utilizza gli algoritmi standard è più lenta di quella che utilizza i loop semplici.

Entrambe le versioni usano questo struct come tipo di ritorno:

struct MeanAndSigma { 
    double mean; 
    double sigma; 
}; 

E la versione con i loop è questa:

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; 
} 

E quella con algoritmi:

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; 
} 

Quando ho misurare il tempo che prendono per chiamate 10k con un vettore con elementi 10k ottengo ~ 2,0 secondi per la versione wit h cicli e ~ 3,2 secondi per quello con algoritmi. Perchè è questo?

Ho già confrontato la CPU e il tempo reale, ma sembra che entrambi siano in esecuzione (come previsto) su una singola CPU. Sto facendo qualcosa di stupidamente sbagliato nell'usare gli algoritmi?

EDIT: Non sto sostenendo che le due versioni sono equivalenti. Tuttavia mi sarei aspettato che la seconda versione sarebbe stata più veloce. Come indicato nei commenti e una risposta, la seconda versione utilizza un'iterazione extra sugli elementi e un extra DVector (che è solo uno typedef std::vector<double>). Tuttavia, non ho familiarità con gli algoritmi standard per migliorare la seconda versione. Quindi, ora la mia domanda è:

Come posso migliorare la versione con algoritmi per essere più veloce di quella che utilizza i loop normali?

Answer 1

Non penso che i programmi siano equivalenti. Nella seconda versione (utilizzando algoritmi) viene popolato un nuovo vettore di doppi e viene coinvolta anche un'ulteriore iterazione.

Si potrebbe provare questo (versione C++ 11), è equivalente della prima versione. Non ho provato a farlo funzionare, dovrebbe funzionare con alcune modifiche minori.

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; 
} 

Senza lambda (non testato, potrebbero aver bisogno di alcune piccole modifiche)

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; 
}