3

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

ただし、時間がかかりすぎます。基本的に、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 の行列の場合、コードが長時間ハングすることです...

誰か助けてくれませんか...

4

1 に答える 1

5

距離の配列を1-D配列に再形成することを試してみてください。ここでは、新しい1-Dインデックスがどのように2-Dインデックスにマップされるかを注意深く記録します。次に、1-D配列で並べ替え関数を呼び出して、昇順で並べ替えます。ソートの原因となるインデックスの順列を必ず保存してから、ソート順列の1次元座標に対応する2次元配列座標を読み取ります。この方法では、Matlabの並べ替えアルゴリズムに翻弄されるため、インデックスの変更が再形成されないように注意深く追跡する必要があります。

これは、考慮からポイントを削除する場合にも問題を引き起こします。すでに選択されているポイントのインデックスの実行リストを保持する必要があります。（1-D順列をトラバースするときに）すでに選択されているインデックスに対応するものに遭遇した場合は、それをスキップします（たとえば、 NaNに設定しないでください。検討からスキップするだけです）。

これにより、毎回最小値を計算する必要がなくなります。1次元ソート順列をトラバースするforループの各反復での唯一の実際のチェックは、現在の場所が以前に選択されているかどうかの論理チェックです（そのポイントの1つがより短い距離の場所に含まれているため）。反復iでは、このチェックは多くのi-1場合比較を行うため、これはO（n ^ 2）よりわずかに少なくなります。

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

より一般的には、この質問への回答にリンクされている論文を読みたいと思います。これは些細な問題ではなく、RAMを集中的に使用するMatlabセッションには適していません。おそらく、これに対するアプローチ全体を書き直す必要があります。

もう1つのアイデアは、すべての配列Aを多数のプロセッサにブロードキャストする場合、これは配列内のポイントで驚異的並列になるということBです。ピースをさまざまなプロセッサに発送してB、すべての距離のリストを取得できます。最小距離のインデックスを選択してそれらのポイントを削除するには、ヘッドノードで何らかの処理を行う必要がありますが、あまり多くはありません。おそらく、距離を何度も計算する必要がないように、とにかくその部分を書き直すことができます。

したがって、これをPythonやC ++などで記述した場合、MPIライブラリをすばやく使用して、Amazon Web Servicesのクラウ​​ドクラスターで実行するか、アクセスできる場合はローカルクラスターで実行できます。

于 2012-04-14T02:39:10.207 に答える