c++ - 加速递归行列式算法

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. Skip Col Check -- 正如 Surt 所建议的那样，删除它可以使我们的速度提高 1%。
2. 添加 3x3 案例 -- 为 3x3 矩阵添加另一个显式检查让我们获得最多，55%
3. Change pow() -- 将 pow() 调用更改为 (r % 2 ? -1.0 : 1.0) 让我们得到一个多一点，57%
4. 更改为 switch -- 将顺序检查更改为 switch 让我们多一点，58%
5. 添加 4x4 案例 -- 为 4x4 矩阵添加另一个显式检查得到更多，85%

不工作的事情包括:

1. memcpy -- 正如 Surt 所建议的那样，这实际上会降低很多速度，-100%
2. Threads -- 创建 order 线程根本不起作用，-160%

我希望使用线程可以显着提高性能，但即使进行了所有优化，它也比原来慢。我认为复制所有内存使其不是很并行。

添加了 3x3 和 4x4 情况最有效，并且是超过 x6 速度增加的主要原因。从理论上讲，您可以添加更多明确的案例(可能通过创建一个程序来输出所需的代码)以进一步降低速度。当然，在某些时候，这种做法违背了使用递归算法的初衷。

要获得更高的性能，您可能必须考虑使用不同的算法。理论上，您可以通过管理自己的堆栈将递归函数更改为迭代函数，但这是一项相当大的工作，而且无论如何都不能保证性能会提高。