Fast way to compare elements of two different sized matrices?

Question

John Hawthorn 2019-7-2

0
链接

此问题的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/469935-fast-way-to-compare-elements-of-two-different-sized-matrices

编辑： John Hawthorn 2019-7-2

I need to do something like the following and am wondering if there's a faster way. mat1 is likely to be fixed size ~2000x2 or so but mat2 might get really big ~1e6?x2. So the thing only runs code if there is a pair (x,y) match between mat1 and mat2. Thoughts?

n1 = 50; n2 = 500;
mat1 = rand([n1, 2]);
mat2 = rand([n2, 2]);
for ii = 1:size(mat1, 1)
    if ismember(mat1(ii, :), mat2, 'rows')
        do my stuff
    end
end

0 个评论
显示 -2更早的评论隐藏 -2更早的评论

请先登录，再进行评论。

请先登录，再回答此问题。

Answer 1

Kaustav Bhattacharya 2019-7-2

0
链接

此回答的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/469935-fast-way-to-compare-elements-of-two-different-sized-matrices#answer_381692

Assuming ismember performs linear search has worst case O(n^2) complexity. The complexity of your code would be 2(n1)*(2n2)^2 = O(n1*n2^2).

You can reshape both the matrices to 1-D arrays and sort. That would take O(n1log(n1) + n2log(n2)).

Now performing binary search in m2 for each element in m1 would take O(n1log(2n2)) and linear search on sorted arrays will take O(n1+n2). So its better to go with binary search. Total complexity O(n1log(n1) + n2log(n2) + n1log(n2))