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

我想尝试将距离数组重塑为一维数组，在其中仔细记录新的一维索引如何映射回二维索引。然后只需调用一维数组上的排序函数，将其排序为升序。确保保存导致排序的索引的排列，然后读取与排序排列中的一维坐标相对应的二维数组坐标。在这种方法中，您将受制于 Matlab 的排序算法，并且您需要仔细跟踪索引因整形而发生的变化。

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

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

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

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

另一个想法是，如果您将所有数组广播A到一堆处理器，那么这在数组中的点上是令人尴尬的并行B。您可以将零件运送B到不同的处理器，并返回所有距离的列表。您必须在头节点上进行一些处理以选择最小距离的索引并删除这些点，但不要太多。可能无论如何您都可以重新编写该部分，这样您就不需要多次计算距离。

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

于 2012-04-14T02:39:10.207 回答