2

我开发了一种图像特征提取算法。为了评估算法提取时间，我使用一组图像作为输入运行了开发的方法及其竞争对手。所有提取算法均在 Matlab 中实现。

然而，有人向我指出，使用 Matlab 实现的时间比较是有问题的。这种说法有依据吗？

4

2 回答 2

4

该论点有两个可能的原因：时序测量可能存在可变性，并且 Matlab 被认为很慢，因此时序毫无意义。

出于第一个原因，获得准确的时间确实是一个挑战，特别是如果程序之间的运行时间非常相似。因此，简单tic，toc应该由timeit函数代替。

第二个原因是假的。当然，在 Matlab 中某些操作可能需要更长的时间，但是 TheMathWorks 在过去几年中花了很多精力使 Matlab 更快，因此在 C/C++ 中重新实现算法实际上可以使其更慢。如果其中一种算法更适合语言的优势，算法的相对速度确实可以在语言之间改变。但是用相同的语言实现这两种算法并诚实地努力以有效的方式实现算法肯定会导致公平的比较。

于 2012-07-02T14:26:44.000 回答
3

时间的有效性取决于您如何实现算法以及如何在“现实世界”中使用它们。如果您有一个算法应用程序，并且将使用 Matlab 实现，那么您的时间安排没有任何问题，因为您正在安排算法的使用方式。但是，如果您打算用较低级别的语言（例如 C++）重新编码算法，您可能会得到明显不同的结果。

Mathworks 花了很多时间优化 Matlab 中的工具箱和基本操作，因此矩阵乘法、矩阵求逆、FFT、SVD 等通常与良好的 C++ 实现一样快。您不一定知道优化了哪些工具箱例程。如果您的算法仅依赖于高度优化的例程，而竞争算法依赖于优化程度较低的例程，那么您的算法可能看起来更好，因为底层实现更好。

可能存在差异的另一个原因是 Matlab 是一种解释性语言。当你的程序有循环时，解释器必须弄清楚每次循环中代码在做什么。相比之下，矩阵运算已提前编译为机器代码，并且没有解释器开销。例如，如果我运行：

start = time; 
x = zeros(1000,1000); 
x = x+1; 
stop = time;
stop - start

在我的电脑上，我得到 0.02297 秒。如果我使用循环运行等效版本：

start = time; 
x=zeros(1000,1000); 
for i = 1:1000
    for j = 1:1000; 
        x(i,j) = x(i,j) + 1; 
    end; 
end; 
stop = time;
stop - start

我得到 18.175 秒。（上面@Jonas 提到的方法在您需要高精度时提供了更好的时机，但在这种情况下，有足够的数量级差异，这种简单的方法可以很好地工作。）

如果竞争算法在循环中做了很多工作，而您的算法更多地依赖内置函数，那么您的算法可能会因为解释器开销较少而击败竞争对手。

如果您计划仅在 Matlab 内部使用这些算法，并且无法从竞争对手中消除解释器开销，那么声称您的算法更好是有效的——至少对于 Matlab 实现而言。如果你想声明一个更一般的结果，至少你必须证明解释器不是性能差异的原因。用像 C++ 这样的语言实现所有算法消除了解释器的开销。为了进行公平的比较，您必须确保您已经完成了所有底层算法（例如，FFT、SVD、矩阵乘法）的快速实现。幸运的是，优化的库可用于多种不同语言的许多常用算法。

当然，如果你能证明你的算法的渐近复杂度更好（O() 表示法），这表明它在更广泛的实现中可能会更好，尽管常量在实际实现中很重要。

于 2012-07-02T15:10:39.337 回答