Как я могу ускорить свою функцию, используя библиотеку Eigen на С++?

Я пытаюсь получить серию остаточной суммы Squarts (RSS) из программы C++, используя цикл for. И я использовал RcppEigen.package.skeleton() для плавного объединения C++ и R. В то время как, когда я запускаю данные X с 788 строк * 857 столбцов и Y с 788 строк * 1 столбец, время выполнения программы C++ составляет пользователь (4,62 с) система (3,87 с) истекло (8,51 с), а время выполнения программы R составляет пользовательское (8,68 с) системное (1,78 с) прошедшее (10,53 с). Программа на C++ менее быстрая, чем R. Я использовал платформу win7 (X64) с 8G RAM. Как я могу ускорить свою программу? Любая помощь будет оценена.

Вот программа на С++:

#include <RcppEigen.h>

//*---get Residual Sum of Squarts via Matrix Operation
//fastLm()
double getRSS(const Eigen::MatrixXd& X, const Eigen::MatrixXd& Y){
   Eigen::MatrixXd RSS=((Y-X*((X.transpose()*X).inverse()*X.transpose()*Y)).transpose())*(Y-X*((X.transpose()*X).inverse()*X.transpose()*Y));
   double RSSd = RSS.determinant();   
   return RSSd;             
}

//*---get F value from RSS and df
double getFval(double RSS1,double RSS2, int n1,int n2,int nObs){
  return (RSS1-RSS2)/(n1-n2)/(RSS2/(nObs-n2-1));      
}

//*---remove p columns from  i-th collumn of matrix
Eigen::MatrixXd removeColumn(const Eigen::MatrixXd& matrix, unsigned int i,int p){
    unsigned int numRows = matrix.rows();
    unsigned int numCols = matrix.cols()-p;

    Eigen::MatrixXd X;
    X=matrix;
    if( i < numCols )
        X.block(0,i,numRows,numCols-i) = matrix.block(0,i+p,numRows,numCols-i);

    X.conservativeResize(numRows,numCols);
    return X;
}

// [[Rcpp::export]]
Rcpp::List getPIcvalue(bool findIn,int p,int n, const Eigen::VectorXd& varIn, const Eigen::MatrixXd& Y,const Eigen::MatrixXd& Xf,const Eigen::MatrixXd& X0){
          //  varIn=(0,1,0,1...,0); p=1 :addition or elimination column; findIn=false,add 1 column of Xf to X0, findIn=false,eliminate 1 column to X0. n=X0.rows();
    bool valid;     
    valid=true;  
    double FitStat1;
    FitStat1 = 1e+10;              

    int pointer;
    pointer=-2;
    double FitStat;
    int nR = n-X0.cols();   // n is the X0.rows()
    int nF;     //nF=nR-1  //findIn=false
    double RSSr;
    double RSSf;
    double F_value;
    RSSr = getRSS(X0,Y);
    int k;
    if(false==findIn){
        k = p;                  
    }else{
        k = -p;      
    }
    Eigen::MatrixXd X(n,X0.cols()+k); 

    if(false==findIn){
        for(int i=0;i<Xf.cols();i++){
            if(0==varIn[i]){
                X<<X0,Xf.col(i);   // X: combine X0 and ith column of Xf                  
                nF = n-X.cols();     
                RSSf = getRSS(X,Y);
                FitStat = getFval(RSSr,RSSf,X.cols(),X0.cols(),n);
                //FitStat = getPvalue(F_value,nF,nR); 
                if(FitStat<FitStat1){
                    FitStat1=FitStat;
                    pointer=i;                    
                }                 
            }//varIn     
        }//for i                 
    }else{
        for(int i=1;i<X0.cols();i++){
            X =  removeColumn(X0,i,p);       
            RSSf = getRSS(X,Y);
            FitStat = getFval(RSSf,RSSr,X0.cols(),X.cols(),n);
            //FitStat = getPvalue(F_value,nR,nF); 
            if(FitStat<FitStat1){
                FitStat1=FitStat;
                pointer=i;                    
            }                 
        }//for i    
    }//findIn 
    return Rcpp::List::create(Rcpp::Named("keyV")=FitStat1,
                              Rcpp::Named("keyP")=pointer+1,
                              Rcpp::Named("keyR")=valid);
}

person JunhuiLi    schedule 09.11.2014    source источник
comment
Вы упоминаете все, кроме того, что потребуется, чтобы даже начать отвечать на ваш вопрос. А именно 1) Compiler used and version of the compiler и 2) Compilation settings to confirm whether you are compiling with optimizations turned on.   -  person PaulMcKenzie    schedule 09.11.2014
comment
Я использовал DEV-C++ для компиляции программы на C++. Я загрузил библиотеки R-3.1.1, Rtools и RcppEigen онлайн, я использовал RcppEigen.package.skeleton() для установки локальной библиотеки. Я запускаю эту программу в R.   -  person JunhuiLi    schedule 09.11.2014
comment
Нет, вы не используете DEV-C++ для компиляции программы на C++. Вы используете IDE под названием Dev-C++ для редактирования вашей программы. @PaulMcKenzie спросил о компиляторе, т.е. какую версию g++ или clang++ вы используете.   -  person Dirk Eddelbuettel    schedule 09.11.2014
comment
Спасибо, @Dirk Eddelbuettel, я использовал компилятор gcc versiong 4.6.3 20111208 <prerelease> <GCC>, и я также получил информацию о том, что CFLAGS='-O2 -mtune=core2 -fomit-frame-pointer'   -  person JunhuiLi    schedule 10.11.2014
comment
@JunhuiLi - хорошо. Это информация, которую мы должны знать. Причина, по которой важно иметь эту информацию, заключается в том, что много раз люди спрашивают, почему мой код работает медленно, и причина, почему он медленный, заключается в том, что они не создавали свое приложение с включенной оптимизацией. Неоптимизированный по времени код бесполезен, поэтому нужно убедиться, что вы не тратите свое время впустую.   -  person PaulMcKenzie    schedule 10.11.2014


Ответы (1)


Ваше выражение для матричной формулы RSS крайне неэффективно. Ты делаешь это:

Eigen::MatrixXd RSS = (
  (Y - X * 
    ( ( X.transpose() * X ).inverse() * X.transpose() * Y ) 
  ).transpose() ) * 
  ( Y - X * 
    ( ( X.transpose() * X ).inverse() * X.transpose() * Y ) 
  );

который явно очень повторяющийся и много раз повторно вычисляет одни и те же дорогостоящие операции. Транспонирование матрицы должно быть очень дешевым, если только для этого не потребуется копия. Но обращение матрицы (даже симметричной положительно определенной матрицы, как в данном случае, которую Эйген не может знать, если вы не скажете ему об этом) очень дорого. Черт... даже умножение матриц дорого.

Вы можете подумать, что Eigen проделывает какую-то скрытую магию, чтобы исключить избыточные операции и найти наиболее эффективную последовательность операций для получения результатов. Но Eigen остается довольно консервативным на этом фронте (полагаясь на консервативные шаблоны выражений, разрешенные во время компиляции, когда на самом деле следует использовать оптимизацию выражений во время выполнения). Так что здесь особо ничего не получится. Вы должны помочь ему удалить лишние операции, выполнив эту работу самостоятельно.

И, наконец, вы можете комбинировать инверсию и умножение, выполнив вместо этого решение линейной системы (вместо A = inv(X) * B вы выполняете solve(X * A = B)), что также позволяет указать наиболее подходящую декомпозицию (здесь это либо llt, либо ldlt, в зависимости от того, как вы ожидаете, что ваша матрица (Xt*X) будет хорошо обусловленной).

Вы получаете это:

auto Xt = X.transpose(); //<- deduce the type with 'auto' to avoid copy-evaluation of the transpose.
const Eigen::MatrixXd A = X * ( Xt * X ).ldlt().solve(Xt);
const Eigen::MatrixXd Y_AY = Y - A * Y;
Eigen::MatrixXd RSS = Y_AY.transpose() * Y_AY;

Но на самом деле вы можете еще больше оптимизировать это, поняв, что X * (Xt * X)^-1 * Xt * Y на самом деле эквивалентно X * B, где B — это решение методом наименьших квадратов для X*B = Y. Если вы используете метод QR (не используйте здесь SVD, это полный излишек и очень медленный, я не понимаю, почему он даже упоминается в документах Eigen как жизнеспособный метод линейного метода наименьших квадратов (вероятно, потому что люди Eigen любители!)), вы можете сделать это:

const Eigen::MatrixXd B = X.colPivHouseholderQr().solve( Y );
const Eigen::MatrixXd Y_XB = Y - X * B;
Eigen::MatrixXd RSS = Y_XB.transpose() * Y_XB;

что должно быть намного быстрее, чем то, что у вас было раньше (по крайней мере, с точки зрения временной сложности это должно быть на порядки быстрее).

Кроме того, если Y оказывается квадратной матрицей, то вам следует вычислить определитель Y_XB и возвести его в квадрат, а не вычислять определитель его произведения с его собственным транспонированием. Это удалит одно матричное умножение (и скопирует в RSS).

Наконец, я не слишком подробно рассматривал другие ваши функции (которые вызывают getRSS), но вы должны делать все возможное, чтобы избежать повторного вычисления (на каждой итерации) вещей, которые не меняются или меняются не слишком сильно, например QR-разложение X. Существуют способы, которыми вы можете поддерживать QR-разложение при изменении X, но это больше, чем я могу здесь подробно описать, и, вероятно, это то, что вы не можете сделать с Eigen.

person Mikael Persson    schedule 09.11.2014
comment
Спасибо, нужно просто 0.03s запустить for цикл, чтобы получить RSS. - person JunhuiLi; 09.11.2014
comment
Из моего теста разложение LDLT и разложение QR имеют вполне сопоставимую скорость. Иногда разложение LDLT происходит немного быстрее. - person zhanxw; 12.06.2017