優化代碼效率

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-d陣列，在那裏你保持新的1-d指數將如何映射認真記錄回二維指數。然後在1-D數組上調用排序函數，將其按升序排序。確保保存導致排序的索引的排列，然後讀取與排序排列中的1-D座標對應的2維數組座標。在這種方法中，你將會受到Matlab排序算法的支配，並且你需要仔細跟蹤重新定形的索引變化。

這也造成了不考慮移除點的問題。你必須爲已經選擇的點保留一個運行的索引列表，並且如果（當你遍歷一維排列）時，你遇到了與已經選擇的索引相對應的東西，那麼你只需跳過它（例如，你不要不會將它設置爲NaN，你只是從考慮中跳過它）。

這樣您就需要每次都計算在最低限度。在遍歷一維排序置換的for循環的每次迭代中唯一真正的檢查是邏輯檢查當前位置是否之前已被選擇（由於其中一個點在較小距離位置處）。在迭代i上，該檢查最多需要i-1比較，所以這將比O（n^2）略小。

這將比您當前的方法更快，它每次計算整個數組的最小值，但仍然不如下面鏈接中提到的O（n log n）方法那麼快。

更一般地說，您想要閱讀在答案to this question中鏈接的論文。這不是一個微不足道的問題，不太適合RAM密集型Matlab會話，並且可能需要你重寫你的整個方法。

另一個想法是，如果你播放所有的陣列A的一堆處理器，那麼這是在陣列B點尷尬的並行。您可以將B件件發送到不同的處理器，並獲取所有距離的列表。您必須在頭節點上進行一些處理，以選擇最小距離的索引並刪除這些點，但不要太多。可能你可以重寫那個部分，這樣你就不需要多次計算距離了。

因此，如果您使用Python或C++編寫該代碼，則可以快速使用MPI庫，然後在Amazon Web Services上的雲羣集上運行它，或者在有權訪問的情況下在本地羣集上運行它。