提高代码效率的优化

Question

提高代码效率的优化

performancealgorithmmatlabprocessing-efficiency

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的矩阵，代码仅仅是长时间地卡在那里...

能有人帮我解决一下吗...

- anon

“value” 是从哪里来的？ - PearsonArtPhoto

它相当于5000...取决于空间中的点数。 - anon

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- ely · Accepted Answer

我建议尝试的方法是将距离数组重新塑造为一维数组，同时仔细记录新一维索引将如何映射回二维索引。然后只需对一维数组调用排序函数，将其按升序排序。确保保存导致排序的索引排列，并读取与排序排列中的一维坐标相对应的二维数组坐标。在此方法中，您将取决于Matlab的排序算法，并且需要仔细跟踪从重塑时的索引更改。

这也会带来一个问题，即如何从考虑范围中删除点。您必须保持已选择点的索引列表，并且如果（当您遍历一维排列时）遇到与已选择索引相对应的内容，则只需跳过它（例如，您不将其设置为NaN，而是跳过不考虑）。

这样可以避免每次计算最小值的需要。在遍历 1-D 排序置换的 for 循环的每次迭代中，唯一真正的检查是当前位置是否已被选择过（由于其某个点涉及到一个较小距离位置）。在第 i 次迭代中，此检查最多需要 i-1 次比较，因此这将略微少于 O(n^2)。

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

更一般地说，您希望阅读答案中链接的论文to this question。这不是一个琐碎的问题，不适合于内存密集型 Matlab 会话，并且可能需要您重新编写整个解决方案。

另一个想法是，如果您将数组A的所有内容广播到一组处理器，那么在数组B中的点上进行尴尬并行处理。您可以将B的各个部分发送到不同的处理器，并返回所有距离的列表。您需要在头节点上进行一些处理，以选择出最小距离的索引并删除那些点，但不需要太多处理。可能您可以重新编写该部分，以便无需多次计算距离。

因此，如果您使用Python或C ++等语言编写此代码，可以快速使用MPI库，在亚马逊Web服务上运行它的云集群，或者在本地集群上运行（如果有访问权限）。