c++ - 计算 vector vector 子集的最佳方法

Question

好的，所以我正在实现一种算法，该算法计算由以下位置给出的 3x3 矩阵的行列式:

A = [0,0 0,1 0,2 
     1,0 1,1 1,2 
     2,0 2,1 2,2]

目前算法是这样的:

float a1 = A[0][0]; 
float calula1 = (A[1][1] * A[2][2]) - (A[2][1] * A[1][2]) 

然后我们转到下一栏，所以它是:

float a2 = A[0][1];
float calcula2 = (A[1][0] * A[2][2]) - (A[2][0] * A[1][2]); 

就这样，再跨一个。现在，就个人而言，这不是很有效，我已经实现了一个可以计算 2x2 矩阵的行列式的函数，这基本上就是我对这些计算中的每一个所做的。

因此，我的问题是，是否有最佳方法可以做到这一点？我考虑过拥有一个函数的想法，它调用一个模板 (X, Y)，它表示 3x3 矩阵的特定 block 的开始和结束位置:

template<typename X, Y> 
float det(std::vector<Vector> data)
{
   //....

}

但是，我不知道这是否是执行此操作的方法，我如何才能像提议的方法一样访问其中的不同元素？

Answer 1

您可以对 rule of Sarrus 进行硬编码如果您只处理 3 x 3 矩阵，就像这样。

float det_3_x_3(float** A) {
    return A[0][0]*A[1][1]*A[2][2] + A[0][1]*A[1][2]*A[2][0]
           + A[0][2]*A[1][0]*A[2][1] - A[2][0]*A[1][1]*A[0][2]
           - A[2][1]*A[1][2]*A[0][0] - A[2][2]*A[1][0]*A[0][1];
}

如果要省3次乘法，可以去

float det_3_x_3(float** A) {
    return A[0][0] * (A[1][1]*A[2][2] - A[2][1]*A[1][2])
           + A[0][1] * (A[1][2]*A[2][0] - A[2][2]*A[1][0])
           + A[0][2] * (A[1][0]*A[2][1] - A[2][0]*A[1][1]);
}

我希望这第二个功能与您已有的功能非常接近。

由于您需要所有这些数字来计算行列式，因此必须至少访问每个数字一次，我怀疑没有比这更快的了。行列式在计算上并不完全漂亮。 Faster algorithms比蛮力方法(Sarrus 的规则基本上是这样)要求您首先转换矩阵，对于 3 x 3 矩阵，这将比仅执行上述操作花费更多的时间。硬编码 Leibniz formula - 这就是 Sarrus 规则的全部内容 - 并不漂亮，但我希望如果您不必为 n > 3 做任何行列式，这是最快的方法。