matlab - 如何在 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