使用Matlab實現的算法進行時間比較是否有問題？

我開發了一個feature extraction算法的圖像。爲了評估算法提取時間，我運行了開發的方法及其競爭對手，使用一組圖像作爲輸入。所有提取算法都在Matlab中實現。然而，有人指出，使用Matlab實現的時間比較值得懷疑。這種說法有沒有基礎？使用Matlab實現的算法進行時間比較是否有問題？

來源

2012-07-02 Alceu Costa

您的時間安排的有效性取決於您如何實施算法，以及他們如何在「真實世界」中使用。如果你有一個算法的應用程序，它將用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-02 15:10:39 wrdieter

有兩種可能的理由：在時間測量中可能存在可變性，並且Matlab被認爲很慢，因此時序沒有意義。

由於第一個原因，getting exact timings can indeed be a challenge，特別是如果運行時間在程序之間非常相似。因此，簡單的tic和toc應該被替換爲timeit函數。

第二個原因是假的。當然，在Matlab中某些操作可能需要更長的時間，但TheMathWorks在過去幾年中花費了大量的精力來使Matlab更快，因此在C/C++中重新實現一個算法實際上可能會讓它變慢。確實，算法的相對速度可以在語言之間變化，如果其中一種算法更適合語言的優勢。但是，用相同的語言來實現這兩種算法並且盡力以高效的方式實現算法肯定會導致公平的比較。

來源

2012-07-02 14:26:44 Jonas

使用Matlab實現的算法進行時間比較是否有問題？

回答

相關問題