我正在尝试分析我编写的 MATLAB 代码的复杂性。
我试图弄清楚多少(就要么) 给出函数,如find、矩阵*运算符、矩阵.*运算符等。
有没有办法计算这个?还是参考?
我正在尝试分析我编写的 MATLAB 代码的复杂性。
我试图弄清楚多少(就要么) 给出函数,如find、矩阵*运算符、矩阵.*运算符等。
有没有办法计算这个?还是参考?
查找和替换、maxtrix-matrix 乘法和元素矩阵-矩阵乘法等标准操作的成本是众所周知的:查看相应的 wiki 站点。
如果您真的想知道您的 MATLAB 安装做了什么,您可以随时继续测量时间,例如,
t = zeros(1,100);
for n = 1:100
A = rand(n,n);
B = rand(n,n);
tic;
C = A*B;
t(n) = toc;
end
plot(t)
这也可以让您对缓存行为等有所了解。
Matlab 6 曾经有一个 flop计算它们的函数,但在以后的版本中被删除了。主要原因是技术上的(他们改用 LAPACK 作为线性代数核心,但它没有返回失败计数)。
今天这个选项不再可用;没有简单的等价物,所以如果你想拥有一个,你必须使用定义和你对如何实现这些操作的最佳猜测自己计算它们。提出大 O 估计应该很容易;并不总是这样来确定确切的常数。在您要求的示例中,很容易猜测 Matlab 正在做什么并手动计算操作,但并非总是如此。
在某些情况下,例如用于计算特征值 ( eig) 的 QR/Francis 算法,这个“常数”将取决于特定的矩阵。Higham's Function of Matrices的附录 C包含一些稠密线性代数运算的良好参考值。然而,真正的答案取决于 Matlab 和 LAPACK 实现的细节,因为前者是闭源的,所以最终是未知的,而且它经常会随着版本的变化而变化。
另外,让我指出,答案取决于您如何定义/复杂性。大多数理论论文中的一个常见选择是“算术运算,例如求和和乘积计数为 1,其他一切都是免费的”(有时称为flop count)。然而,使用这个定义,find成本为零,因为它进行了一堆比较但没有真正的算术运算。要扮演魔鬼的拥护者,您甚至可以用一堆比较和赋值来代替浮点运算。所以有很多理由认为这不是一个好的选择。
对于一个不太人为的例子,考虑完全旋转的高斯消除:它与部分旋转具有相同的失败计数成本,但它涉及比较而不是,这些比较增加了它的实际成本。
此外,现代计算机上的执行时间不再(仅)取决于触发器。内存布局、缓存未命中、分支预测等细节影响很大。除了运行它并测量时间之外,没有简单的方法来判断一个操作需要多长时间。查看此线程以获取启发性示例。关于如何降低线性代数运算中的内存访问等“隐藏成本”,有一个完整的研究领域;例如,查看Jim Demmel 主页上的“避免通信的算法”部分。
Matlab 本身的性能是另一罐蠕虫。Matlab 是一种解释型语言,它在字里行间做了很多额外的工作和簿记。如果您使用 Matlab 分析器检查哪些指令花费的时间最多,您通常会发现罪魁祸首是令人惊讶的不寻常的行,例如内存分配、比较或对几乎什么都不做的函数的调用。仅仅将函数放在名称空间或类中就会对其执行时间产生巨大影响。JIT 编译器(Matlab 加速器)优化了一些紧凑的周期,但由于它本身是封闭源代码且不断发展,因此无法预测它是否以及何时启动。Mathworks 明确拒绝提供一个接口来判断一个函数是否有是否经过 JIT 编译。
要从整体上检查您的实现,您可以使用 MATLAB 的分析器。它是一种内置功能,可以根据执行时间分析您的代码。
它为所有类型的测量提供了一个接口,您可以深入研究结果,直至特定代码行的执行时间。