如何在Matlab中最有效地比较坐标对而不使用嵌套循环

Question

如果我有20对坐标，它们的x和y值是:

x   y
27  182
180 81
154 52
183 24
124 168
146 11
16  90
184 153
138 133
122 79
192 183
39  25
194 63
129 107
115 161
33  14
47  65
65  2
1   124
93  79

现在，如果我随机生成15对坐标(x,y)，并想与上面给出的这20对坐标进行比较，我如何在没有嵌套循环的情况下最有效地做到这一点?

Answer 1

如果您试图查看15个随机生成的坐标对中的任何一个是否等于20个原始坐标对中的任何一个，一个简单的解决方案是使用函数ISMEMBER，如下所示:

oldPts = [...];  %# A 20-by-2 matrix with x values in column 1
                 %#   and y values in column 2
newPts = randi(200,[15 2]);  %# Create a 15-by-2 matrix of random
                             %#   values from 1 to 200
isRepeated = ismember(newPts,oldPts,'rows');

isRepeated将是一个15 × 1的逻辑数组，如果oldPts中存在一行newPts，则为1，否则为0。

Answer 2

如果您的坐标是1)实际上是整数并且2)它们的跨度是合理的(否则使用稀疏矩阵)，那么我将使用一个简单的真值表。像

x_0= [27 180 ...
y_0= [182 81 ...
s= [200 200]; %# span of coordinates
T= false(s);
T(sub2ind(s, x_0, y_0))= true;
%# now obtain some other coordinates
x_1= [...
y_1= [...
%# and common coordinates of (x_0, y_0) and (x_1, y_1) are just
T(sub2ind(s, x_1, y_1))

Answer 3

如果你原来的20个点不会改变，你可以把它们排序为O(n log n)，这样效率会更高;然后你就可以看到每个随机点是否在一个O(log n)搜索的列表中。

如果您的"原始"点列表发生了变化(插入/删除)，您可以使用二叉树获得相同的性能。

BUT:如果你正在处理的点数真的和你的问题一样低，你的双循环可能只是最快的方法!当数据量变得非常大时，使用低big - o曲线的算法会更快，但这通常是以一次性减速为代价的(在你的情况下，排序)——而且只有15x20个数据点……不会有人类感觉得到的区别;如果你在你的系统时钟上计时，你可能会看到一个。也可能不会。

希望这对你有帮助!