Looking for an efficient Alternative for "intersect" function in matlab 2015

Question

i have a program in MATLAB 2015 that calls intersect function more than 5 million times. for example:

x=[2,4,6,3]
y=[3,5,7,9,1,6,4]
tic;for i=1:5*1e6;t=intersect(x,y);end;toc;
*Elapsed time is 365.038992 seconds in my computer

but because of the intersect function my program is too slow, is there any efficient alternative for intersect function? builtin or Mex or something like these. I also tried unique(x(ismember(x,y))):

tic;for i=1:5*1e6;t=unique(x(ismember(x,y)));end;toc;
*Elapsed time is 227.7381 seconds in my computer

although this cause some improvements but this is not enough! i have the same problem with unique() and ismember() too.

Answer 1

Here's a fast solution that works in all cases (elements can be non-unique and/or non-positive).

tmp = sort(x(ismembc(x,sort(y))));
t = tmp([~~diff(tmp),true]);

Basic idea behind it is the same as in your suggestion with unique(x(ismember(x,y))), however both ismember and unique are slow and can be improved. We can use built-in ismembc instead of ismember, but we need to ensure second argument is sorted. And instead of using unique, we use a combination of sort, diff and logical indexing.

That gives an improvement of ~15.5x over intersect on Matlab 2013b:

>> tic; for i=1:1e5, tmp=sort(x(ismembc(x,sort(y)))); t = tmp([~~diff(tmp),true]); end; toc;
Elapsed time is 0.998081 seconds.

>> tic; for i=1:1e5, t = intersect(x,y); end; toc;
Elapsed time is 15.538410 seconds.

For a more specific case, if you know that elements of x are unique, you can just use the result of ismembc straight away, resulting in ~33x speedup:

>> tic; for i=1:1e5, t = x(ismembc(x,sort(y))); end; toc;
Elapsed time is 0.465070 seconds.

Benchmark results could obviously differ on another Matlab release and/or PC, but I believe the outcome would be the same regardless.