Как сделать этот код более быстрым

Question

Следующий фрагмент кода выполняет 20 миллионов раз каждый раз, когда программа вызывается, поэтому мне нужен способ сделать этот код максимально оптимизированным. Я не продвинутый программист на C++, поэтому я ищу эту помощь невероятного сообщества.

int WilcoxinRST::work(GeneSet originalGeneSet, vector<string> randomGenes) { 
vector<string> geneIDs; 
vector<bool> isOriginal; 
vector<int> rank; 
vector<double> value; 
vector<int> score; 
int genesPerSet = originalGeneSet.geneCount(); 
unsigned int totalGenes, tempScore; 
/** 
* Fill the first half of the vectors with original gene set data 
*/ 
totalGenes = genesPerSet * 2; 
for (int i = 0; i < genesPerSet; i++) { 
    geneIDs.push_back(originalGeneSet.getMemberGeneAt(i)); 
    isOriginal.push_back(true); 
    value.push_back(fabs(expressionLevels.getValue(geneIDs[i], statType))); 
} 
/** 
* Fill the second half with random data 
*/ 
for (unsigned int i = genesPerSet; i < totalGenes; i++) { 
    geneIDs.push_back(randomGenes.at(i - genesPerSet)); 
    isOriginal.push_back(false); 
    value.push_back(fabs(expressionLevels.getValue(geneIDs[i], statType))); 
} 
totalGenes = geneIDs.size(); 
/** 
* calculate the scores 
*/ 
if (statType == Fold_Change || statType == T_Statistic 
     || statType == Z_Statistic) { 
    //  Higher value is a winner 
    for (unsigned int i = 0; i < totalGenes; i++) { 
     tempScore = 0; 
     if (!isOriginal[i]) { 
      for (int j = 0; j < genesPerSet; j++) { 
       if (value.at(i) > value.at(j)) { 
        tempScore++; 
       } 
      } 

     } else { 
      for (unsigned int j = genesPerSet; j < totalGenes; j++) { 
       if (value.at(i) > value.at(j)) { 
        tempScore++; 
       } 
      } 

     } 

     score.push_back(tempScore); 
    } 

} else if (statType == FDR_PValue || statType == PValue) { 
    // Lower value is a winner 
    for (unsigned int i = 0; i < totalGenes; i++) { 
     tempScore = 0; 
     if (!isOriginal[i]) { 
      for (int j = 0; j < genesPerSet; j++) { 
       if (value.at(i) < value.at(j)) { 
        tempScore++; 
       } 
      } 

     } else { 
      for (unsigned int j = genesPerSet; j < totalGenes; j++) { 
       if (value.at(i) < value.at(j)) { 
        tempScore++; 
       } 
      } 

     } 

     score.push_back(tempScore); 
    } 

} else { 
    cout << endl << "ERROR. Statistic type not defined." << endl; 
} 

/** 
* calculate Ua, Ub and U 
*/ 
int U_Original = 0, U_Random = 0, U_Final; 
for (int j = 0; j < genesPerSet; j++) { 
    U_Original += score[j]; 
} 
for (unsigned int j = genesPerSet; j < totalGenes; j++) { 
    U_Random += score[j]; 
} 
U_Final = (U_Original < U_Random) ? U_Original : U_Random; 

/** 
* calculate z 
*/ 
double Zn, Zd, Z; 
Zn = U_Final - ((genesPerSet * genesPerSet)/2); 
Zd = sqrt(
     (double) (((genesPerSet * genesPerSet 
       * (genesPerSet + genesPerSet + 1))))/12.0); 
Z = Zn/Zd; 

/** 
* Return 0/1/2 
* 2: p value < 0.01 
* 1: 0.01 < p value < 0.05 
* 0: p value > 0.05 
*/ 
if (fabs(Z) > 2.303) 
    return 2; 
else if (fabs(Z) > 1.605) 
    return 1; 
else 
    return 0; 
} 

Answer 1

Ваш код имеет сложность O (N * N) [genesPerSet = N]. Но используя тот факт, что порядок значений для вас неактуальен, мы можем заказать его в O (N • log (N)) и вычислить «баллы» в O (N). (С потенциально может быть тысячи раз быстрее).

Кроме того, мы имеем общее количество сравнений N * N. Затем U_Original + U_Random = N * N, что означает, что нам не нужно вычислять U_Random. Также ваша статистика Zn = Umin-N * N/2; [Umix=min(U_Original,U_Random)],, когда вы только abs (Zn/Zd) симметричны вокруг N * N/2. Нам нужен только один алгоритм.

1.- Первая вещь может быть принимать аргументы (сопзЬ) Справочно:

int WilcoxinRST::work(const GeneSet &originalGeneSet, const vector<string> &randomGenes) 

2.- Вы заполняете в вектор geneIDs; но не использовать его? Зачем?

3.- Вы можете повторять только 2 раза.

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

5.- Вам не нужен вектор оценки, только сумма.

6.- Почему 20 миллионов раз? Я хочу, чтобы вы вычислили некоторую «статистическую» стабильность или BStrap. Возможно, вы используете один и тот же оригинальныйGeneSet много раз. Я думаю, вы можете в другом вопросе поставить код, который вызывает эту функцию, чтобы сэкономить время при создании вектора значений и сортировки.

Здесь представлен новый код O (N • log (N)).

Далее следует очистка вашего кода, но все же O (N * N), быстрая, но только постоянным фактором.

Тогда тот же код, но смешанный с вашим исходным кодом и с дополнительными комментариями.

Пожалуйста, отлаживайте это и расскажите, как это было.

#include<vector> 
#include<algorithm> 

int WilcoxinRST::work(const GeneSet &originalGeneSet , const vector<string>& randomGenes) 
{ 
    size_t genesPerSet = originalGeneSet.geneCount(); 
    std::vector<double> valueOri(genesPerSet), valueRnd(genesPerSet); 
    /** 
    * Fill the valueOri vector with original gene set data, and valueRnd with random data 
    */ 
    for (size_t i = 0; i < genesPerSet; i++) 
    { 
     valueOri[i] = std::fabs(expressionLevels.getValue(originalGeneSet.getMemberGeneAt(i) , statType)); 
     valueRnd[i] = std::fabs(expressionLevels.getValue(randomGenes.at(i)     , statType)); 
    } 
    std::sort(valueOri.begin(),valueOri.end()); 
    std::sort(valueRnd.begin(),valueRnd.end()); 

    /** 
    * calculate the scores Ua, Ub and U 
    */ 
    long U_Original ; 

    if (statType == Fold_Change || statType == T_Statistic || statType == Z_Statistic 
     statType == FDR_PValue || statType == PValue) 
    { 
     //  Higher value is a winner 
     size_t j=0; 
     for (size_t i = 0; i < genesPerSet /*totalGenes*/; i++)  // i - 2x 
     { 
      while(valueOri[i] > valueRnd[j]) ++j ; 
      U_Original += j; 
     } 
    } else { cout << endl << "ERROR. Statistic type not defined." << endl; } 

    /** 
    * calculate z 
    */ 
    double Zn, Zd, Z; 
    Zn = U_Original - ((genesPerSet * genesPerSet)/2); 
    Zd = std::sqrt((double) (((genesPerSet * genesPerSet* (genesPerSet + genesPerSet + 1))))/12.0); 
    Z = Zn/Zd; 

    /** 
    * Return 0/1/2 
    * 2: p value < 0.01 
    * 1: 0.01 < p value < 0.05 
    * 0: p value > 0.05 
    */ 
     if (std::fabs(Z) > 2.303) return 2; 
    else if (std::fabs(Z) > 1.605) return 1; 
    else       return 0; 
} 

Далее следует очистка вашего кода, но все же O (N * N), быстрая, но только постоянным фактором.

#include<vector> 
using namespace std; 
class GeneSet ; 
class WilcoxinRST; 

int WilcoxinRST::work(const GeneSet &originalGeneSet , const vector<string>& randomGenes) 
{ 
    size_t genesPerSet = originalGeneSet.geneCount(); 
    vector<double> valueOri(genesPerSet), valueRnd(genesPerSet); 
    /** 
    * Fill the valueOri vector with original gene set data, and valueRnd with random data 
    */ 
    for (size_t i = 0; i < genesPerSet; i++) 
    { 
     valueOri[i] = fabs(expressionLevels.getValue(originalGeneSet.getMemberGeneAt(i) , statType)); 
     valueRnd[i] = fabs(expressionLevels.getValue(randomGenes.at(i)     , statType)); 
    } 
    /** 
    * calculate the scores Ua, Ub and U 
    */ 
    long U_Original = 0, U_Random = 0, U_Final; 

    if (statType == Fold_Change || statType == T_Statistic || statType == Z_Statistic) 
    { 
     //  Higher value is a winner 
     for (size_t i = 0; i < genesPerSet /*totalGenes*/; i++)  // i - 2x 
     { for (size_t j = 0; j < genesPerSet; j++) 
      { U_Random += (valueRnd[i] > valueOri[j]);// i en 2 set=Rnd, j in 1 set=Ori. count how many Ori are less than this Rnd 
       U_Original+= (valueOri[i] > valueRnd[j]);// i in 1 set=Ori, j in 2 set=Rnd, count how many Rnd are less than this Ori 
      } 
     } 
    } else 
    if (statType == FDR_PValue || statType == PValue) 
    { 
     // Lower value is a winner 
     for (size_t i = 0; i < genesPerSet; i++) 
     { 
      for (size_t j = 0; j < genesPerSet; j++) 
      { U_Random += (valueRnd[i] < valueOri[j]);// i en 2 set=Rnd, j in 1 set=Ori. count how many Ori are > than this Rnd 
       U_Original+= (valueOri[i] < valueRnd[j]);// i in 1 set=Ori, j in 2 set=Rnd, count how many Rnd are > than this Ori 
      } 
     } 
    } else { cout << endl << "ERROR. Statistic type not defined." << endl; } 


    U_Final = (U_Original < U_Random) ? U_Original : U_Random; 

    /** 
    * calculate z 
    */ 
    double Zn, Zd, Z; 
    Zn = U_Final - ((genesPerSet * genesPerSet)/2); 
    Zd = sqrt(
      (double) (((genesPerSet * genesPerSet 
        * (genesPerSet + genesPerSet + 1))))/12.0); 
    Z = Zn/Zd; 

    /** 
    * Return 0/1/2 
    * 2: p value < 0.01 
    * 1: 0.01 < p value < 0.05 
    * 0: p value > 0.05 
    */ 
     if (fabs(Z) > 2.303)  return 2; 
    else if (fabs(Z) > 1.605)  return 1; 
    else       return 0; 
} 

тот же код, но в сочетании с вашим исходным кодом и с дополнительными комментариями.

int WilcoxinRST::work(const GeneSet &originalGeneSet , const vector<string>& randomGenes) 
{ 
    size_t genesPerSet = originalGeneSet.geneCount(); 
    unsigned int totalGenes, tempScore; 
    totalGenes = genesPerSet * 2; 

    //vector<string> geneIDs; 
    //vector<bool> isOriginal; 
    //vector<int> rank; 
    vector<double> valueOri(genesPerSet), valueRnd(genesPerSet); 
    //vector<int> score; 
    /** 
    * Fill the first half of the vectors with original gene set data 
    */ 

    for (size_t i = 0; i < genesPerSet; i++) 
    { 
     //geneIDs.push_back(originalGeneSet.getMemberGeneAt(i) ); 
     //isOriginal.push_back(true); 

     valueOri[i] = fabs(expressionLevels.getValue(originalGeneSet.getMemberGeneAt(i) , statType)); 
     valueRnd[i] = fabs(expressionLevels.getValue(randomGenes.at(i)     , statType)); 
    } 
    /** 
    * Fill the second half with random data 
    */ 
    //for (unsigned int i = genesPerSet; i < totalGenes; i++) { 
    // geneIDs.push_back(randomGenes.at(i - genesPerSet)); 
    // isOriginal.push_back(false); 
    // value.push_back(fabs(expressionLevels.getValue(geneIDs[i], statType))); 
    //} 
    //totalGenes = geneIDs.size(); 
    /** 
    * calculate the scores 
    */ 
     /** 
    * calculate Ua, Ub and U 
    */ 
    long U_Original = 0, U_Random = 0, U_Final; 
    //for (int j = 0; j < genesPerSet; j++) // j in 1 set=Ori. count how many Ori are less than this Rnd 
    //{ 
    // U_Original += score[j]; 
    //} 
    //for (unsigned int j = genesPerSet; j < totalGenes; j++) // j in 2 set=Rnd, count how many Rnd are less than this Ori 
    //{ 
    // U_Random += score[j]; 
    //} 

    if (statType == Fold_Change || statType == T_Statistic || statType == Z_Statistic) 
    { 
     //  Higher value is a winner 
     for (size_t i = 0; i < genesPerSet /*totalGenes*/; i++)  // i - 2x 
     { //tempScore = 0; 
      //if (!isOriginal[i]) // i en 2 set=Rnd, j in 1 set=Ori. count how many Ori are less than this Rnd 
      for (size_t j = 0; j < genesPerSet; j++) 
      { U_Random += (valueRnd[i] > valueOri[j]);// i en 2 set=Rnd, j in 1 set=Ori. count how many Ori are less than this Rnd 
       U_Original+= (valueOri[i] > valueRnd[j]);// i in 1 set=Ori, j in 2 set=Rnd, count how many Rnd are less than this Ori 
      } 
      //} else 
      //{ 
      // for (unsigned int j = genesPerSet; j < totalGenes; j++) // i in 1 set=Ori, j in 2 set=Rnd, count how many Rnd are less than this Ori 
      // { if (value.at(i) > value.at(j)) { tempScore++;  } 
      // } 

      //} 
      //score.push_back(tempScore); 
     } 

    } else 
    if (statType == FDR_PValue || statType == PValue) 
    { 
     // Lower value is a winner 
     for (size_t i = 0; i < genesPerSet; i++) 
     { 
      for (size_t j = 0; j < genesPerSet; j++) 
      { U_Random += (valueRnd[i] < valueOri[j]);// i en 2 set=Rnd, j in 1 set=Ori. count how many Ori are > than this Rnd 
       U_Original+= (valueOri[i] < valueRnd[j]);// i in 1 set=Ori, j in 2 set=Rnd, count how many Rnd are > than this Ori 
      } 
      //} else 
      //{ 
      // for (unsigned int j = genesPerSet; j < totalGenes; j++) // i in 1 set=Ori, j in 2 set=Rnd, count how many Rnd are less than this Ori 
      // { if (value.at(i) > value.at(j)) { tempScore++;  } 
      // } 

      //} 
      //score.push_back(tempScore); 
     } 

     //for (unsigned int i = 0; i < totalGenes; i++) 
     //{ tempScore = 0; 
     // if (!isOriginal[i]) 
     // { for (int j = 0; j < genesPerSet; j++) { 
     //   if (value.at(i) < value.at(j)) { // Rnd i < Ori j increm U_Random 
     //    tempScore++; 
     //   } 
     //  } 

     // } else { 
     //  for (unsigned int j = genesPerSet; j < totalGenes; j++) { // Ori i < Rnd j. Increm U_Original 
     //   if (value.at(i) < value.at(j)) { 
     //    tempScore++; 
     //   } 
     //  } 

     // } 

     // score.push_back(tempScore); 
     //} 

    } else { cout << endl << "ERROR. Statistic type not defined." << endl; } 


    U_Final = (U_Original < U_Random) ? U_Original : U_Random; 

    /** 
    * calculate z 
    */ 
    double Zn, Zd, Z; 
    Zn = U_Final - ((genesPerSet * genesPerSet)/2); 
    Zd = sqrt(
      (double) (((genesPerSet * genesPerSet 
        * (genesPerSet + genesPerSet + 1))))/12.0); 
    Z = Zn/Zd; 

    /** 
    * Return 0/1/2 
    * 2: p value < 0.01 
    * 1: 0.01 < p value < 0.05 
    * 0: p value > 0.05 
    */ 
    if (fabs(Z) > 2.303) 
     return 2; 
    else if (fabs(Z) > 1.605) 
     return 1; 
    else 
     return 0; 
}