2

画像の特徴抽出アルゴリズムを開発しました。アルゴリズムの抽出時間を評価するために、一連の画像を入力として使用して、開発した方法とその競合他社を実行しました。すべての抽出アルゴリズムは Matlab で実装されました。

しかし、Matlab の実装を使用した時間比較には疑問があると指摘されました。この主張に根拠はありますか？

4

2 に答える 2

4

議論には2つの理由が考えられます。タイミング測定にはばらつきがある可能性があり、Matlabはおそらく遅いため、タイミングは無意味です。

最初の理由から、特に実行時間がプログラム間で非常に類似している場合、正確なタイミングを取得することは確かに困難な場合があります。したがって、単純ticであり、 timeit関数tocに置き換える必要があります。

2番目の理由は偽物です。確かに、Matlabでは一部の操作に時間がかかる場合がありますが、TheMathWorksは過去数年間でMatlabを高速化するために多大な労力を費やしてきたため、C /C++でアルゴリズムを再実装すると実際に速度が低下する可能性があります。アルゴリズムの1つが言語の長所により適している場合、アルゴリズムの相対速度が言語間で変わる可能性があるのは事実です。しかし、両方のアルゴリズムを同じ言語で実装し、効率的な方法でアルゴリズムを実装するために正直な努力をすることは、確かに公正な比較につながります。

于 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 に答える