Find equal rows between two Matlab matrices

4
votes

I have a matrix index in Matlab with size GxN and a matrix A with size MxN.

Let me provide an example before presenting my question.

clear
N=3;
G=2;
M=5;

index=[1  2  3;
       13 14 15]; %GxN

A=[1  2  3; 
   5  6  7; 
   21 22 23; 
   1  2  3;
   13 14 15]; %MxN

I would like your help to construct a matrix Response with size GxM with Response(g,m)=1 if the row A(m,:) is equal to index(g,:) and zero otherwise.

Continuing the example above 

Response= [1 0 0 1 0; 
           0 0 0 0 1]; %GxM

This code does what I want (taken from a previous question of mine - just to clarify: the current question is different)

Response=permute(any(all(bsxfun(@eq, reshape(index.', N, [], G), permute(A, [2 3 4 1])), 1), 2), [3 4 1 2]);

However, the command is extremely slow for my real matrix sizes (N=19, M=500, G=524288). I understand that I will not be able to get huge speed but anything that can improve on this is welcome.

3
matlabperformancematrixrowsset-intersection
I highly doubt this is much more improveable. You may be able to do it by instead of using 1-liners, break the code into pieces and time it - Ander Biguri

3 Answers

7
votes

MATLAB has a multitude of functions for working with sets, including setdiff, intersect, union etc. In this case, you can use the ismember function:

[~, Loc] = ismember(A,index,'rows');

Which gives:

Loc =
     1
     0
     0
     1
     2

And Response would be constructed as follows:

Response = (1:size(index,1) == Loc).';


Response =
  2×5 logical array
   1   0   0   1   0
   0   0   0   0   1
7
votes

Aproach 1: computing distances

If you have the Statistics Toolbox:

Response = ~(pdist2(index, A));

or:

Response = ~(pdist2(index, A, 'hamming'));

This works because pdist2 computes the distance between each pair of rows. Equal rows have distance 0. The logical negation ~ gives 1 for those pairs of rows, and 0 otherwise.

Approach 2: reducing rows to unique integer labels

This approach is faster on my machine:

[~,~,u] = unique([index; A], 'rows');
Response = bsxfun(@eq, u(1:G), u(G+1:end).');

It works by reducing rows to unique integer labels (using the third output of unique), and comparing the latter instead of the former.

For your size values this takes approximately 1 second on my computer:

clear
N = 19; M = 500; G = 524288;
index = randi(5,G,N); A = randi(5,M,N);
tic
[~,~,u] = unique([index; A], 'rows');
Response = bsxfun(@eq, u(1:G), u(G+1:end).');
toc

gives

Elapsed time is 1.081043 seconds.
3
votes

You could reshape the matrices so that each row instead lies along the 3rd dimension. Then we can use implicit expansion (see bsxfun for R2016b or earlier) for equality of all elements, and all to aggregate on the rows (i.e. false if not all equal for a given row).

Response = all( reshape( index, [], 1, size(index,2) ) == reshape( A, 1, [], size(A,2) ), 3 );

You might even be able to avoid some reshaping by using all in another dimension, but it's easier for me to visualise it this way.