Как сравнить пары координат наиболее эффективно, не используя вложенные циклы в 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, в котором строка newPts существует в oldPts, а в противном случае обнуляется.

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

Если ваши исходные двадцать баллов не изменятся, вы получите лучшую эффективность, если вы отсортируете их O (n log n); тогда вы могли видеть, была ли каждая случайная точка в списке с помощью поиска O (log n).

Если ваш «оригинальный» список точек изменится (вставки / удаления), вы можете получить эквивалентную производительность с двоичным деревом.

НО: если количество точек, с которыми вы работаете, действительно так мало, как в вашем вопросе, ваш двойной цикл может быть просто самым быстрым методом! Алгоритмы с низкими кривыми Big-O будут быстрее, так как объем данных становится действительно большим, но часто за счет одноразового замедления (в вашем случае, сортировки) - и только с 15x20 точками данных ... Там не будет разницы воспринимаемой человеком; Вы могли бы видеть один, если вы синхронизируете это на своих системных часах. Или нет.

Надеюсь, это поможет!