効率のためにコードを最適化する

Question

ユークリッド距離に基づいて、あるベクトルから別のベクトルへの点のマッピングを実行するコードを作成し、それが正しく動作することを確認しました。

ただし、時間がかかりすぎます。基本的には、AとBのベクトルのユークリッド距離の行列を作成し、その最小値を求めました。これらの点の写像を表すと、ユークリッド行列から行と列が削除され、次の写像が発生するためのNaNとしてマークされます。

それは今とても遅いので、このコードは、より効率的にすることができます...

Euclid = distance(A,B); % calculates euclid distance column v/s column wise. 
for var = 1 : value 
    %# finds the min of Euclid and its position, when Euclid is viewed as a 1D array 
    [~, position] = min(Euclid(:)); 

    %#transform the index in the 1D view to 2 indices 
    [i,j] = ind2sub(size(Euclid),position); 

    %display(strcat(num2str(i),32, num2str(j))); 

    mapping = [A(1,i) A(2,i) B(1,j) B(2,j)]; 
    fprintf(FID,'%d %d %d %d\n', mapping); 

    Euclid(i , :) = NaN; 
    Euclid(: , j) = NaN; 
    %counter = counter + 1; 
end  

問題は、コードだけで長時間ハング5000 X 5000行列のためにということです...

誰かが私を助けることができます...

Answer 1

距離の配列を1次元配列に再形成して、新しい1次元インデックスをどのようにマップするかを慎重に記録することをお勧めします。 2-Dインデックス次に、1次元配列のソート関数を呼び出し、昇順にソートします。ソートの原因となるインデックスの順列を保存してから、ソート順列の1次元座標に対応する2次元配列座標を必ず読み出してください。この方法では、Matlabのソートアルゴリズムが役に立つので、索引の変更を細かく見直しておく必要があります。

これはまた、ポイントを考慮から除外するための問題を提起します。すでに選択されているポイントのインデックスの実行リストを保持しなければならないでしょう。もし、（1次元置換を通過すると）既に選択されているインデックスに対応するものがあれば、スキップしますそれをNaNに設定しないで、あなたはただそれをスキップするだけです）。

これにより、毎回最小値を計算する必要がなくなります。 1-Dソート順列を横断するforループの各反復での唯一の実際のチェックは、現在の位置が以前に選択されたかどうか（その点のうちの1つがより小さい距離の場所に含まれているため）を論理的にチェックすることです。反復iでは、このチェックは最大でi-1の比較を要するので、これはO（n^2）よりわずかに少なくなります。

これは、毎回アレイ全体の最小値を計算する現在の方法よりも速くなりますが、下のリンクで説明されているO（n log n）メソッドほど速くはありません。

もっと一般的には、回答to this questionにリンクされている論文を読んでみたいです。これは簡単な問題ではなく、RAM集約型のMatlabセッションにはあまり適していません。おそらく、これに全アプローチを書き直す必要があります。

もう1つの考え方は、配列Aをすべて一連のプロセッサにブロードキャストすると、配列Bの点に恥ずかしく並行しているということです。 Bの部分を別のプロセッサに発送して、すべての距離のリストを返すことができます。ヘッドノードでいくつかの処理をやり直して、min-distanceのインデックスを選択し、それらのポイントを削除する必要があります。たぶん、その部分を書き換えて、距離を何度も計算する必要がないようにすることができます。

これをPythonやC++などに書き込むと、すぐにMPIライブラリを使用し、Amazon Web Servicesのクラウ​​ドクラスタ、またはアクセス可能であればローカルクラスタ上でMPIライブラリを実行できます。