C = union( A,B ) is too slow. Is there any faster way given that A and B are ordered.

I have two sorted arrays A and B. I want to find the elements that are both in A and B. I am using union function, yet this seems to be quite slow. Is there a faster way of doing this ?

[Bruno Luong]

Well

C = [A(:); B(:)]

contains "the elements that are both in A and B".

However it's not sorted or uniquely represented. But you doesn't seem to mention those characteristics are required.

[John D'Errico]

Bruno does make a good point here.

Answer 1

[Bruno Luong]

If you have a decend C-compiler you might use my MEX MERGE SORTED ARRAY

c = mergesa(a,b); % or mergemex(a,b);
c = c([true; diff(c1)>0]);

According to my benchmark, it runs 2.5 time faster than UNION.

Answer 2

[Sulaymon Eshkabilov]

Hi,

This one could be faster:

ismember(A, B)

[John D'Errico]

Except ismember does not do the same thing as union. You might check to see what ismember does return.

Answer 3

[Walter Roberson]

The faster way would involve writing some mex code. There is an undocumented internal binary search routine, but calling it repeatedly would have too much overhead. The algorithm is easy enough to write in MATLAB but the performance would not be better than the current algorithm, which calls upon compiled routines.

Answer 4

[John D'Errico]

You could use unique. It would produce the same result, except that it will not be faster.

A = sort(randi(1e7,1,1e6));
B = sort(randi(1e7,1,1e6));
timeit(@() union(A,B))
ans =
            0.097985031132
            
timeit(@() unique([A,B]))
ans =
            0.097896961132

In fact, both codes would be faster if the arrays were not sorted.

A = randi(1e7,1,1e6);
B = randi(1e7,1,1e6);
timeit(@() unique([A,B]))
ans =
            0.044566429132
timeit(@() union(A,B))
ans =
            0.044880346132

Of course, randomizing the data will not help, as then the cost of randomization will enter into the problem.

If you truly need more speed than that, then you need to write compiled code. That is not to say you should compile MATLAB code. Since these tools will already have been compiled for speed, compiling them will not help.

However, IF you could write EFFICIENT code that is based on the assumption that the arrays are already pre-sorted, then you could gain speed.