# search for elements of a vector in a matrix (without using ismember)

23 views (last 30 days)
Ashwin Renganathan on 18 Oct 2017
Edited: Ashwin Renganathan on 20 Oct 2017
I have a matrix A of size Nx2, N is large. I have another vector b of size nx1 and n<<N. I want to filter out those row indices of A, where both columns could contain any 2 elements of b.
For instance, let
A = [1 2;3 4; 5 6]
b = [1,2,5,6]'
Then output of method(A,b) should be
[1,3]'
(i.e. the first and 3rd rows of A contain 2 elements from b, but not the 2nd row.
I am currently using a combination of ismember and find but seems like ismember is not very efficient because my A, as I said, is very large.
Thanks in advance!
EDIT: (some more background on the problem)
The code has about couple dozen functions of which couple of them call ismember within a loop. The overall code takes several hours to execute when N is in O(1e5) and profiling it showed most of the time is consumed by ismember. The whole point of the question is to verify if (i) ismember is specifically inefficient for large scale code and (ii) are there alternatives that could take only a fraction of ismember 's cputime
EDIT 2: Tried alternative suggestion using 'any'. The cpu time was almost identical.
EDIT 3: Solved. Based on my personal experience, it does seem like ismember is inefficient when used repeatedly used within a large loop. So I replaced it with cellfun (since my 'b' is actually a cell array) & bsxfun and saw 25x speedup. Thanks to everyone that chimed in. I learned a lot!
##### 0 CommentsShowHide -1 older comments

Sign in to comment.

### Answers (4)

Cedric Wannaz on 19 Oct 2017
Edited: Cedric Wannaz on 19 Oct 2017
EDIT: I took 3 more minutes and I profiled a small test case (N=1e7, n=1e2). ISMEMBER is more efficient!
Here is an alternative for MATLAB 2016b and above:
>> all( any( A == permute( b, [3,2,1] ), 3 ), 2 )
ans =
3×1 logical array
1
0
1
Then FIND if you need indices.
And here the version for below 2016b:
all( any( bsxfun( @eq, A, permute( b, [3,2,1] )), 3 ), 2 )
If speed maters much, it may be faster to avoid pages:
>> any( A(:,1) == b.', 2 ) & any( A(:,2) == b.', 2 )
ans =
3×1 logical array
1
0
1
but you'll have to profile all solutions and also ISMEMBER, because our guesses about performance are often wrong.
##### 2 CommentsShowHide 1 older comment
Cedric Wannaz on 19 Oct 2017
Moved here:
There may be ways to pre-process a few things, to eliminate the loop, to parallelize, etc. I built a quick test (with n~10) and you can see that working with an expansion/ANY/etc may be as efficient as Andrei's solution for small values of N, but that as soon as N gets larger ISMEMBER becomes more efficient:

Sign in to comment.

Jan on 19 Oct 2017
Edited: Jan on 19 Oct 2017
[EDITED Wrong approach:]
You can save some time with calling the internally used C-Mex function:
bs = sort(b); % Omit if b is sorted already!
find(ismembc(A(:,1), bs) & ismembc(A(:,2), bs))
Then b is sorted once only.
Unfortunately ismembc is not documented. It existed at least from Matlab 5.3 to 2016b, but it might be removed from the toolbox in the future.
[EDITED] No, this is slower that ismember. Obviously Matlab uses faster methods now internally.
##### 3 CommentsShowHide 2 older comments
Walter Roberson on 19 Oct 2017
I was about to refer to _ismemberhelper, which is what is used by ismember() for some special cases of sorted data. In R2017b look near line 333 of ismember() for a description of _ismemberhelper

Sign in to comment.

Andrei Bobrov on 19 Oct 2017
Edited: Andrei Bobrov on 19 Oct 2017
all(ismember(A,b),2)
or
diff(A(all(ismember(A,b),2),:),1,2)~=0
##### 0 CommentsShowHide -1 older comments

Sign in to comment.

Matt J on 18 Oct 2017
find( ismember(A(:,1),b) & ismember(A(:,2),b) )
##### 15 CommentsShowHide 14 older comments
Ashwin Renganathan on 19 Oct 2017
Cedric - I really appreciate it. Thanks! I am re-thinking my algorithm to see scope for improvement. I will try to include the actual loops sometime today if it is still necessary.

Sign in to comment.

### Community Treasure Hunt

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

Start Hunting!

Translated by