Если у меня есть 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 парами координат, указанными выше, как я могу сделать это наиболее эффективно без вложенных циклов?
Если вы пытаетесь увидеть, равна ли какая-либо из ваших 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, и нулями в противном случае.
Если ваши координаты 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))
Если ваши исходные двадцать точек не изменятся, вы повысите эффективность, если отсортируете их O(n log n); тогда вы могли бы увидеть, была ли каждая случайная точка в списке с поиском O (log n).
Если ваш «исходный» список точек изменится (вставки/удаления), вы можете получить эквивалентную производительность с двоичным деревом.
НО: если количество точек, с которыми вы работаете, действительно так мало, как в вашем вопросе, ваш двойной цикл может быть просто самым быстрым методом! Алгоритмы с низкими кривыми Big-O будут быстрее, когда объем данных станет действительно большим, но часто это происходит за счет единовременного замедления (в вашем случае сортировки) - и только с 15x20 точками данных... Там не будет заметной для человека разницы; вы можете увидеть его, если вы измеряете его по системным часам. А может и нет.
Надеюсь это поможет!
