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

7 次查看（过去 30 天）
Cem Gormezano
Cem Gormezano 2020-8-9
评论： John D'Errico 2020-8-9
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 个评论
Bruno Luong
Bruno Luong 2020-8-9
编辑：Bruno Luong 2020-8-9
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.

请先登录，再进行评论。

请先登录，再回答此问题。

采纳的回答

Bruno Luong
Bruno Luong 2020-8-9
编辑：Bruno Luong 2020-8-9
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.

更多回答（3 个）

Sulaymon Eshkabilov
Hi,
This one could be faster:
ismember(A, B)
Walter Roberson
Walter Roberson 2020-8-9
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 2020-8-9
编辑：John D'Errico 2020-8-9
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.

类别

在 Help Center 和 File Exchange 中查找有关 Resizing and Reshaping Matrices 的更多信息

标签

产品


版本

R2019b

Community Treasure Hunt

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

Start Hunting!

Translated by