Faster INTERSECT with strings - MATLAB

Question

I have code written in Matlab that uses “intersect” to find vectors (and their indices) that intersect in two large matrices. I found that "intersect" is the slowest line (big difference) in my code. Unfortunately, so far I have not been able to find a faster alternative.

As an example, running the code below takes about 5 seconds on my computer:

profile on
for i = 1 : 500
    a = rand(10000,5);
    b = rand(10000,5);
    [intersectVectors, ind_a, ind_b] = intersect(a,b,'rows');
end
profile viewer

I was wondering if there is a faster way. Note that matrices (a) and (b) have 5 columns. The number of rows does not have to be the same for the two matrices.

Any help would be great. Thanks

Answer 1

, fast matrix multiplication in MATLAB, 5 , "" . , , intersect ismember 'rows', !

-

intersectrows_fast_v1.m:

function [intersectVectors, ind_a, ind_b] = intersectrows_fast_v1(a,b)

%// Calculate equivalent one-column versions of input arrays
mult = [10^ceil(log10( 1+max( [a(:);b(:)] ))).^(size(a,2)-1:-1:0)]'; %//'
acol1 = a*mult;
bcol1 = b*mult;

%// Use intersect without 'rows' option for a good speedup
[~, ind_a, ind_b] = intersect(acol1,bcol1);
intersectVectors = a(ind_a,:);

return;

intersectrows_fast_v2.m:

function [intersectVectors, ind_a, ind_b] = intersectrows_fast_v2(a,b)

%// Calculate equivalent one-column versions of input arrays
mult = [10^ceil(log10( 1+max( [a(:);b(:)] ))).^(size(a,2)-1:-1:0)]'; %//'
acol1 = a*mult;
bcol1 = b*mult;

%// Use ismember to get indices of the common elements
[match_a,idx_b] = ismember(acol1,bcol1);

%// Now, with ismember, duplicate items are not taken care of automatically as
%// are done with intersect. So, we need to find the duplicate items and
%// remove those from the outputs of ismember
[~,a_sorted_ind] = sort(acol1);
a_rm_ind =a_sorted_ind([false;diff(sort(acol1))==0]); %//indices to be removed
match_a(a_rm_ind)=0;

intersectVectors = a(match_a,:);
ind_a = find(match_a);
ind_b = idx_b(match_a);

return;

, , -

-------------------------- With original approach
Elapsed time is 3.885792 seconds.
-------------------------- With Proposed approach - Version - I
Elapsed time is 0.581123 seconds.
-------------------------- With Proposed approach - Version - II
Elapsed time is 0.963409 seconds.

, , version - I 6.7x !!

, - intersect , , !