优化代码效率

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上的云群集上运行它，或者在有权访问的情况下在本地群集上运行它。