# Fast way to compare elements of two different sized matrices?

2 views (last 30 days)
John Hawthorn on 2 Jul 2019
Edited: John Hawthorn on 2 Jul 2019
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

Kaustav Bhattacharya on 2 Jul 2019
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))
John Hawthorn on 2 Jul 2019
Edited: John Hawthorn on 2 Jul 2019
Oh thats good. Thanks a bunch

### Categories

Find more on Matrix Indexing in Help Center and File Exchange

R2018b

### Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!