Fast way to compare elements of two different sized matrices?
조회 수: 2 (최근 30일)
이전 댓글 표시
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
채택된 답변
Kaustav Bhattacharya
2019년 7월 2일
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))
추가 답변 (0개)
참고 항목
카테고리
Help Center 및 File Exchange에서 Resizing and Reshaping Matrices에 대해 자세히 알아보기
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!