我有两个二维点列表,分别作为M x 2-和nx2-矩阵给出,其中M和N可能非常大。
什么是最快的方法来确定他们中有多少人是平等的?

最佳答案

我不确定您是否想计算重复条目,但如果不想,您可以使用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

10-06 04:13
查看更多