Как сравнить два несортированных списка в Matlab?

Question

У меня есть два списка двумерных точек, заданных как M x 2 - и N x 2 - матрицы соответственно, причем M и N, возможно, очень большие.

Каков самый быстрый способ определить, сколько из них одинаково?

Answer 1

Я не уверен, хотите ли вы подсчитать повторяющиеся записи, но если бы вы не могли использовать intersect или какой-то довольно интуитивный алгоритм, основанный на сортировке (см. Ниже). Я бы не предпочесть версию вложенного цикла ...

function test_compareVecs() 
    %% create some random data 
    N = 31415; 
    M1 = 100000; 
    M2 = 200000; 
    vec = rand(N,2); 
    v1 = [rand(M1-N,2); vec]; 
    v2 = [rand(M2-N,2); vec]; 
    v1 = v1(randperm(M1),:); 
    v2 = v2(randperm(M2),:); 

    %% intersect 
    disp('intersect:'); 
    tic 
    s = size(intersect(v1,v2,'rows'),1); 
    toc; 
    s 

    %% alternative approach 
    disp('alternative approach:'); 
    tic; 
    s = compareVecs(v1,v2); 
    toc; 
    s  
end 

function s = compareVecs(v1,v2) 
    %% create help vector 
    help_vec = [[v1,zeros(size(v1,1),1)]; ... 
       [v2,ones(size(v2,1),1)]]; 

    %% sort by first column 
    % note: for some reason "sortrows(help_vec,1)" is slower 
    hash_vec = help_vec(:,1); % dummy hash 
    [~,sidx] = sort(hash_vec); 
    help_vec = help_vec(sidx,:); 

    %% diff + compare 
    help_vec = diff(help_vec);  
    s = sum(help_vec(:,1) == 0 & ... 
      help_vec(:,2) == 0 & ... 
      help_vec(:,3) ~= 0); 
end 

Результата

intersect: 
Elapsed time is 0.145717 seconds. 
s = 31415 

alternative approach: 
Elapsed time is 0.048084 seconds. 
s = 31415 

Answer 2

Compute всех парных расстояний с pdist2, а затем рассчитывать пары с нулевым расстоянием. Если координаты значения с плавающей точкой, вы можете использовать допуск вместо сравнения с нулем:

%// Data: 
M = 10; 
N = 8; 
listM = randi(10,M,2)-1; 
listN = randi(10,N,2)-1; 
tol = 1e-6; 
%// Distance matrix: 
d = pdist2(listM, listN); 
%// Count: 
count = sum(d(:)<tol); 

Answer 3

Это должно работать независимо от порядка точек в каждом списке, или их длины. Это решение хеш-таблицы/словаря, которое должно быть быстрым, но с потребностью в памяти, линейной по длине списков. Пожалуйста, обратите внимание, что приведенный ниже синтаксис может быть не идеальным, но краткая ссылка на упомянутые основные структуры данных должна сделать тривиальную корректировку.

(1) заполняет словарь-containers.Map таким образом, что ключ является уникальной функцией точек, например. num2str(M(i,1))'-'num2str(M(i,2)).

(2) Затем перейдите ко всем элементам второго списка, создайте ключ так же, как в (1), и проверьте, существует ли он. Если это так, установите map(key)=1 еще и установите 0. В конце все ключи, состоящие из общих точек, будут сохранены в 1, а остальные будут нулями.

(3) Доработка суммирования значений карты (что-то вроде sum(map.values())), который должен дать вам общее количество уникальных пересечений между двумя группами, независимо от того, этих точек появляются в каждом списке.

OBS: если вы не хотите, чтобы рассчитывать только уникальные перекрестки, но все повторяющиеся точки, в (2), а не делать map(key)=1, добавьте 1 к map(key). Остальное - то же самое.