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

3 views (last 30 days)
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 ?
  2 Comments
Bruno Luong
Bruno Luong on 9 Aug 2020
Edited: Bruno Luong on 9 Aug 2020
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.

Sign in to comment.

Accepted Answer

Bruno Luong
Bruno Luong on 9 Aug 2020
Edited: Bruno Luong on 9 Aug 2020
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.

More Answers (3)

Sulaymon Eshkabilov
Sulaymon Eshkabilov on 9 Aug 2020
Hi,
This one could be faster:
ismember(A, B)

Walter Roberson
Walter Roberson on 9 Aug 2020
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.

John D'Errico
John D'Errico on 9 Aug 2020
Edited: John D'Errico on 9 Aug 2020
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.

Products


Release

R2019b

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!