优化代码以提高效率

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索引将如何映射回2-D索引.然后只需在1-D数组上调用排序函数,将其按升序排序.确保保存导致排序的索引的排列,然后读取与排序排列中的1-D坐标对应的2-D数组坐标.在这种方法中,你将受到Matlab排序算法的支配,你需要仔细跟踪重塑的索引变化.

这也带来了从考虑中去除点的问题.您必须为已经选择的点保留一个正在运行的索引列表,如果(当您遍历1-D排列时)遇到与已经选择的索引相对应的内容,那么您只需跳过它(例如,您不要不要把它设置为NaN,你只需要考虑它.

这使您无需每次都计算最小值.在遍历1-D排序排列的for循环的每次迭代中唯一真实的检查是逻辑检查之前是否已经选择了当前位置(由于其中一个点涉及较小的距离位置).在迭代时i,此检查最多i-1进行比较,因此这将略小于O(n ^ 2).

这将比您当前的方法更快,该方法每次计算整个数组的最小值,但仍然不如下面链接中提到的O(n log n)方法快.

更一般地说,您希望阅读此问题答案中链接的论文.这不是一个微不足道的问题,不适合RAM密集型Matlab会话,可能需要您重写整个方法.

另一个想法是,如果你将所有数组广播A到一堆处理器,那么这在数组中的点上是令人尴尬的并行B.您可以B将不同的处理器发送出去,然后返回所有距离的列表.您必须在头节点上进行一些处理以选择最小距离的索引并删除这些点,但不要太多.也许你可以重新编写那个部分,这样你就不需要多次计算距离了.

因此,如果您使用Python或C++编写此代码,则可以快速使用MPI库,然后在Amazon Web Services上的云群集上运行它,或者如果您有权访问,则在本地群集上运行它.