2

I'm writing a bigger program and getting the determinants of 3x3 matrices as fast as possible is pretty important for it to work well. I've read that I could use numPy to do it, but I thought that maybe writing my own code would be more educational as I'm in my 3rd semester of CompSci.

So I wrote two functions and I'm using time.clock() (I'm on a win7 machine) to time how long it takes for each function to return a value.

This is the first function:

def dete(a):
   x = (a[0][0] * a[1][1] * a[2][2]) + (a[1][0] * a[2][1] * a[3][2]) + (a[2][0] * a[3][1] * a[4][2])
   y = (a[0][2] * a[1][1] * a[2][0]) + (a[1][2] * a[2][1] * a[3][0]) + (a[2][2] * a[3][1] * a[4][0])
   return x - y

And this is the second function:

def det(a):
    a.append(a[0]); a.append(a[1]);
    x = 0
    for i in range(0, len(a)-2):
        y=1;        
        for j in range(0, len(a)-2):    
            y *= a[i+j][j]      
        x += y

    p = 0
    for i in range(0, len(a)-2):
        y=1;
        z = 0;
        for j in range(2, -1, -1):  
            y *= a[i+z][j]  
            z+=1        
        z += 1
        p += y  
    return x - p

They both give the correct answers, however the first one seems to be slightly faster, which makes me think that since for-loops are more elegant to use and usually faster, I'm doing something wrong - I made the loops too slow and fat. I tried trimming it down, but it seems that the *= and += operations are taking too much time, there's too many of them. I haven't checked how fast numPy takes care of this problem yet, but I wanna get better at writing efficient code. Any ideas on how to make those loops faster?

4

5 回答 5

3

首先让我注意，微尺度速度优化应该用另一种语言进行。因此，您最好使用使用 c 编写功能的库。

关于你的 for 循环：展开（小）循环以加快速度是一种常用技术，因此让循环完成这项工作并不总是更快。通常它只是更通用（大多数通用算法实际上比专用算法慢）。

正如评论中所述，它不会提高 python 的速度，-但*如果涉及的算术运算较少，它可能会提高速度。因此，我将在此处发布已分解的术语：

def dete(a):
    return (a[0][0] * (a[1][1] * a[2][2] - a[2][1] * a[1][2])
           -a[1][0] * (a[0][1] * a[2][2] - a[2][1] * a[0][2])
           +a[2][0] * (a[0][1] * a[1][2] - a[1][1] * a[0][2]))

如您所见，有 5+/-和 9 *，而在原始版本中有 5+/-和 12 *。另请注意，此版本a仅访问 15 次，而原始版本访问了 18 次。

总结起来，这产生了 3 个算术运算和 3 个变量访问，比完全相乘的版本少。

于 2012-02-26T17:29:13.867 回答
3

循环更优雅，更通用，但它们并不比单个表达式中的几个内联乘法“通常更快”。

一方面，forpython中的循环必须组装你将交互的对象（调用range），然后为循环中的每个项目调用该迭代器上的方法。

所以，根据你在做什么，如果内联表单足够快，你可以保留它 - 如果它仍然太慢（通常是我们在 Python 中进行数值计算时的情况），你应该使用数值库（例如 NumpY），它可以在本机代码中计算行列式。在像这样的数字操作代码的情况下，您可以使用本机代码将其运行速度提高数百倍。

如果 yo9u 需要一些已经制作的库无法执行的数值计算，如果您寻求速度（例如，图像处理中的像素操作），您可能更愿意编写在本机代码中运行的扩展（使用 C ，Cython 或其他一些东西），以便快速获得它。

另一方面，如果速度不是关键，甚至注意到内联表达式只是“稍微快一点”，那么只需使用完整循环——你会获得更具可读性和可维护性的代码——这毕竟是使用 Python 的主要原因。

在您给出的具体示例中，您可以通过硬编码对元组的“范围”调用来提高循环代码的速度 - 例如，更改： for i in range(0, len(a)-2):到for i in (0, 1, 2)- 请注意，与内联情况一样，您失去了使用矩阵的能力不同大小的。

于 2012-02-26T17:35:56.270 回答
1

如上所述，当您展开它时，您还可以将两个块合并为一个，因为快速浏览发现两个块之间没有依赖关系（如果我错了，请纠正我）

于 2012-02-26T17:31:30.063 回答
1

循环几乎不可能比显式的长表达式更快，所以难怪第一个变体更快。我怀疑您能否比第一个功能更快地提出 smt。

于 2012-02-26T17:32:06.513 回答
0

you can unroll the loops and take advantage of the fact that you handle 3x3 matrices and not nxn matrices.

With this optimization you get rid of the determination of the size of the matrix. You trade flexibility with a little speed up. You can simply write down the concrete formulas for each cell of the result matrix. BTW: (c++) Compilers do such optimization stuff.

I would only suggest to do so, if you are really sure that such a small optimization is worth the specialized code. To make sure, that you optimize the right part of your code use e.g. the profiling tools see http://docs.python.org/library/profile.html or timeit.

于 2012-02-26T17:28:33.600 回答