Ускорение алгоритма рекурсивного детерминанта

Question

Как ускорить эту рекурсивную функцию? Когда он достигает матрицы 10x10, для решения проблемы требуется около минуты или около того. Я включил функцию события так, чтобы вы могли видеть, когда произойдет расчет.

void determinantsFrame::OnCalculateClick(wxCommandEvent &event) 
{ 
    double elem[MAX][MAX]; double det; string test; bool doIt = true; 
    for (int i = 0; i < n; i++) 
    { 
     for (int j = 0; j < n; j++) 
     { 
      test = (numbers[i][j]->GetValue()).mb_str(); 
      if (test == "") 
      { 
       doIt = false; 
       break; 
      } 

      for (int k = 0; k < test.length(); k++) 
       if (isalpha(test[k]) || test[k] == ' ') 
       { 
        doIt = false; 
        break; 
       } 
       else if (ispunct(test[k])) 
       { 
        if (test[k] == '.' && test.length() == 1) 
         doIt = false; 
        else if (test[k] == '.' && test.length() != 1) 
         doIt = true; 
        else if (test[k] != '.') 
         doIt = false; 
       } 

      if (doIt == false) 
       break; 
     } 
     if (doIt == false) 
      break; 
    } 

    if (doIt) 
    { 
     for (int i = 0; i < n; i++) 
      for (int j = 0; j < n; j++) 
       elem[i][j] = static_cast<double>(wxAtof(numbers[i][j]->GetValue())); 

     det = determinant(elem, n); 
     wxMessageBox(wxString::Format(wxT("The determinant is: %.4lf"),det)); 
    } 
    else 
     wxMessageBox(wxT("You may have entered an invalid character. Please try again")); 
} 

double determinantsFrame::determinant(double matrix[MAX][MAX], int order) // Here's the recursive algorithm 
{ 
    double det = 0; double temp[MAX][MAX]; int row, col; 

    if (order == 1) 
     return matrix[0][0]; 
    else if (order == 2) 
     return ((matrix[0][0] * matrix[1][1]) - (matrix[0][1] * matrix[1][0])); 
    else 
    { 
     for (int r = 0; r < order; r++) 
     { 
      col = 0; row = 0; 
      for (int i = 1; i < order; i++) 
      { 
       for (int j = 0; j < order; j++) 
       { 
        if (j == r) 
         continue; 

        temp[row][col] = matrix[i][j]; 
        col++; 

        if (col == order - 1) 
         col = 0; 
       } 
       row++; 
      } 
      det = det + (matrix[0][r] * pow(-1, r) * determinant(temp, order - 1)); 
     } 
     return det; 
    } 
} 

Answer 1

Вы можете сделать немного лучше, сохранив тот же алгоритм, но он по крайней мере O(n!) (возможно, хуже), поэтому матрицы более высокого порядка будут медленными, независимо от того, насколько вы его оптимизируете. Примечание. Я делал тесты в MSVC 2010 и присутствовал только для приблизительных целей сравнения. Каждое изменение кумулятивно, когда вы идете по списку и сравнивается с исходным алгоритмом.

1. Пропустить Col Check - Как было предложено Surt, убрав это становится нам увеличение скорости на 1%.
2. Добавить 3х3 Case - Добавление другой явную проверки для матрицы 3х3 получает нас больше всего, 55%
3. Изменения пау() - Изменение pow() вызова (r % 2 ? -1.0 : 1.0) получает нас немного больше, 57 %
4. Изменить для переключения - Изменение порядка проверки на коммутатор получает нам немного больше, 58%
5. Добавить 4x4 Case - Добавление другой явную проверки для матрицы 4х4 получает больше, 85%

вещей, которые не работают, включают:

1. тетсру - Как Surt предположила, что это на самом деле теряет много скорости, -100%
2. Тема - Создание order темы вообще не работает, -160%

Я надеялся, что использование потоков может привести к значительному увеличению производительности, но даже при всей оптимизации он медленнее оригинала. Я думаю, что копирование всей памяти делает ее не очень параллельной.

Добавлены случаи 3x3 и 4x4, которые имеют наибольший эффект и являются основной причиной увеличения скорости x6. Теоретически вы можете добавить более явные случаи (возможно, создав программу для вывода требуемого кода), чтобы еще больше уменьшить скорость. Конечно, в какой-то момент этот вид побеждает цель использования рекурсивного алгоритма для начала.

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

Answer 2

Это может быть branch mispredict проблемы (see also). Тест

if (col == order - 1) 
    col = 0; 

Не нужно, насколько я могу судить.

Тест не прошел 1/order раз за цикл и доминирует для небольших order, поэтому не влияет на большее количество N. Время все еще большое O (N!^3) (afaik), поэтому не ожидайте чудес.

 col = 0; row = 0; 
     for (int i = 1; i < order; i++) { 
      for (int j = 0; j < order; j++) { 
       if (j == r) 
        continue; 

       temp[row][col] = matrix[i][j]; 
       col++; 

       //if (col == order - 1) 
       // col = 0; 
      } 
      col = 0; // no need to test 
      row++; 
     } 

Алгоритм получит дальнейшее замедление при попадании в кэш L2, самое позднее при N = 64.

Также копия матрицы может быть неэффективной, это может быть гораздо более эффективным для больших order за счет низкой эффективности при низких order.

for (int r = 0; r < order; r++) { 
     row = 0; 
     for (int i = 1; i < order; i++) { 
      memcpy(temp[row], matrix[i], r*sizeof(double)); // if r==0 will this work? 
      memcpy(&temp[row][r], &matrix[i][r+1], (order-r-1)*sizeof(double)); 
      // amount of copied elements r+(order-r-1)=order-1. 

      row++; 
     } 

Пройдите тест с исходным кодом, чтобы получить детерминанту, что я получил индексы правильно!