Fast way to compare elements of two different sized matrices?

2 次查看（过去 30 天）
John Hawthorn
John Hawthorn 2019-7-2
编辑： 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

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

采纳的回答

Kaustav Bhattacharya
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 中查找有关 Matrix Indexing 的更多信息

标签

产品


版本

R2018b

Community Treasure Hunt

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

Start Hunting!

Translated by