what is the fastest way to search a huge matrix

Question

Li Xue 2016-2-12

0
链接

此问题的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/267804-what-is-the-fastest-way-to-search-a-huge-matrix

评论： Guillaume 2016-2-12

I have 2 huge matrices, A and B, with the same size (9000 by 9000). I need to search two numbers x and y from A and B, respectively, and return the indices where x and y appears in A and B. I have 10,000+ pairs of x and y saved in a table of C, therefore need to do 10,000+ such searches.

I am currently using the following code, but it took me 4+ hours to finish the searching.

linearIdx=rowfun(@(x, y)find(A==x & B == y),C ) ;
[I,J]=ind2sub(size(A), linearIdx.Var1);

Is there faster way to do it? Maybe I should save A and B into hashtable? Thanks.

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

请先登录，再进行评论。

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

Answer 1

Guillaume 2016-2-12

0
链接

此回答的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/267804-what-is-the-fastest-way-to-search-a-huge-matrix#answer_209567

编辑：Guillaume 2016-2-12

在 MATLAB Online 中打开

I'm assuming that the (x, y) pair is always present and only present once in (A, B). Otherwise the code you've posted would fail at the rowfun point.

The best way to find the locations of all the elements of an array within another array is to use ismember. In your case, the best thing to do would be to reshape A and B into columns, concatenate them into a 2 column array, and perform the search with ismember plus the 'rows' option:

[isrowfound, linearidx] = ismember(C, table(A(:), B(:)), 'rows'); 
%note: I wouldn't bother with tables and instead just have C as a matrix, in which case:
%[isrowfound, linearidx] = ismember(C, [A(:), B(:)], 'rows'); 
assert(all(isrowfound), 'Some rows in C were not present in (A, B)')
[I, J] = ind2sub(size(A), linearidx);

If a pair (x, y) is not found then the call to sub2ind will fail (due to linearidx containing 0).

If a pair (x, y) is found several time, you'll only get the location of the first one. Unlike your code, it won't cause an error.

2 个评论
显示无隐藏无

Li Xue 2016-2-12

编辑：Li Xue 2016-2-12

Many thanks. The code is now only taking seconds to run! Thanks a lot! Yes, (x, y) pair is always present and only present once in (A, B). By the way, you had a typo in your code: sub2ind should be ind2sub.