A faster way to achieve what crosses me ()?

Question

I find that a lot of time spent in my matlab function is in this code:

intersect(freq_bins, our_bins); 

Both can be quite large vectors and consist only of integers. I just need to know which integers are in both. This is really a primitive intersect () target, so I suspect the answer is this: it is not improving. But maybe someone has some suggestions.

Answer 1

intersect calls ismember . In your case, you do not need all the complex checks that intersect performs, so you can save some overhead and call ismember directly (note: I definitely called both functions before synchronizing them):

 a = randi(1000,100,1); b = randi(1000,100,1); >> tic,intersect(a,b),toc ans = 76 338 490 548 550 801 914 930 Elapsed time is 0.027104 seconds. >> tic,a(ismember(a,b)),toc ans = 914 801 490 548 930 550 76 338 Elapsed time is 0.000613 seconds. 

You can do this even faster by calling ismembc , a function that does the actual testing, directly. Note that ismembc requires sorted arrays (so you can remove sorting if your input is already sorted!)

 tic,a=sort(a);b=sort(b);a(ismembc(a,b)),toc ans = 76 338 490 548 550 801 914 930 Elapsed time is 0.000473 seconds. 

Answer 2

If you can assume that your inputs contain sorted lists of unique integers, you can do this in linear time using a very simple algorithm:

 function c = intersect_sorted(a,b) ia = 1; na = length(a); ib = 1; nb = length(b); ic = 0; cn = min(na,nb); c = zeros(1,cn); while (ia <= na && ib <= nb) if (a(ia) > b(ib)) ib = ib + 1; elseif a(ia) < b(ib) ia = ia + 1; else % a(ia) == b(ib) ic = ic + 1; c(ic) = a(ia); ib = ib + 1; ia = ia + 1; end end c = c(1:ic); end 

The maximum runtime for lists of length n and m will be O (n + m).

 >>a = unique(randi(1000,100,1)); >>b = unique(randi(1000,100,1)); >>tic;for i = 1:10000, intersect(a,b); end,toc Elapsed time is 1.224514 seconds. >> tic;for i = 1:10000, intersect_sorted(a,b); end,toc Elapsed time is 0.289075 seconds.