Как мога да ускоря функцията си с помощта на библиотеката Eigen в C++?

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

Ето програмата на C++:

#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