Check for equality in the contents of two arrays ignoring order

Question

Bill Tubbs 2021-10-17

0
链接

此问题的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/1565851-check-for-equality-in-the-contents-of-two-arrays-ignoring-order

评论： Bill Tubbs 2021-10-18

I want to check that the contents of two arrays are equal, ignoring ordering of the elements.

I couldn't find an existing answer on this for some reason. There are two parts to this question, depending on whether the arrays are sets or not.

1. Checking equality for two sets

Assuming there are no duplicates I could use set operaions but it doesn't look like Matlab has sets, only set operations, and I couldn't find a setisequal function. Also, there are so many possible ways to do it I'm not sure which is the best:

A = [1 3]; B = [3 1];
assert(isequal(intersect(A, B), union(A, B)))

or

assert(isempty(setdiff(A,B)) & isempty(setdiff(B,A)))

or

assert(all(ismember(B, A)) & all(ismember(A, B)))

or

assert(isequal(unique(A), unique(B)))

However, if there may be different numbers of duplicates in either of the two arrays, then the above set operations will ignore them.

2. Checking equality for non-sets

This is the best I could think of in this case but it involves two sort operations which is quite inefficient:

assert(isequal(sort(A), sort(B)))

No doubt there is something very simple that I am missing here...

0 个评论
显示 -2更早的评论隐藏 -2更早的评论

请先登录，再进行评论。

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

Answer 1

Walter Roberson 2021-10-17

1
链接

此回答的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/1565851-check-for-equality-in-the-contents-of-two-arrays-ignoring-order#answer_810486

在 MATLAB Online 中打开

%sets case
A = [1 3]; B = [3 1];
isequal(unique(A), unique(B))
ans = logical
   1

For the sets case, a different approach just might be faster:

numel(A) == numel(B) && all(ismember(A, B))
ans = logical
   1
%nonset case:
A = [1 3]; B = [3 1 3];
isequal(unique(A), unique(B))
ans = logical
   1

7 个评论
显示 5更早的评论隐藏 5更早的评论

Walter Roberson 2021-10-17

在 MATLAB Online 中打开

But is the ismember() version faster than the isequal() of unique?

And in the sets case, is unique() faster than sort()?

N = 100000;

T = 25;

A = randperm(N);

B = randperm(N);

C = randperm(N); C(randi(N,1,5)) = randi(N,1,5); %likely to produce duplicates

[eteu, etes, etnel, nteu, ntes, ntnel] = deal(zeros(1,T));

for K = 1 : T;

%case where they are in fact equal

eteu(K) = timeit(@() isequal(unique(A), unique(B)),0);

etes(K) = timeit(@() isequal(sort(A), sort(B)), 0);

etnel(K) = timeit(@() numel(A) == numel(B) && all(ismember(A,B)));

%case where they are not equal

nteu(K) = timeit(@() isequal(unique(A), unique(C)),0);

ntes(K) = timeit(@() isequal(sort(A), sort(C)), 0);

ntnel(K) = timeit(@() numel(A) == numel(C) && all(ismember(A,C)));

end

X = categorical({'eteu', 'etes', 'etnel', 'nteu', 'ntes', 'ntnel'});

Y = [mean(eteu), mean(etes), mean(etnel), mean(nteu), mean(ntes), mean(ntnel)];

bar(X, Y)

Analysis:

checking isequal() of sort() is slightly faster than checking isequal() of unique(), but checking isequal() of unique() is statistically the same as all(ismember) when the sets are the same size (if they are potentially different sizes then checking the size first could be a big advantage.)

The difference between checking isequal() of sort() compared to isequal() of unique() is small enough that it is probably not worth using two different code paths: might as well use the isequal() of unique() for both cases.

Walter Roberson 2021-10-18

在 MATLAB Online 中打开

%implementation #1
0.1 + 0.2 - 0.3
ans = 5.5511e-17
%implementation #2
0.1 - 0.3 + 0.2
ans = 2.7756e-17

Two implementation of the same algorithm involving floating point values will typically not return identical results.

Bill Tubbs 2021-10-18

在 MATLAB Online 中打开

You have a good point about tolerances. The only solution that works at the moment is therefore something like this:

assert(all(abs(sort(A) - sort(B)) < 1e-6))

I'm happy with this t.b.h.

请先登录，再进行评论。

Answer 2

Bill Tubbs 2021-10-17

0
链接

此回答的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/1565851-check-for-equality-in-the-contents-of-two-arrays-ignoring-order#answer_810466

在 MATLAB Online 中打开

I think this might be the answer for case 1 (A & B are sets):

A = [1 3]; B = [3 1];
assert(isempty(setxor(A, B)))
A = [1 3]; B = [3 1 2];
assert(~isempty(setxor(A, B)))

Note: Doesn't work in the case that A or B are not sets:

A = [1 3]; B = [3 1 3];
assert(~isempty(setxor(A, B)))

Assertion failed.

0 个评论
显示 -2更早的评论隐藏 -2更早的评论

请先登录，再进行评论。

Answer 3

Jan 2021-10-17

0
链接

此回答的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/1565851-check-for-equality-in-the-contents-of-two-arrays-ignoring-order#answer_810506

在 MATLAB Online 中打开

unique, setdiff, union and ismember call the function sort also internally. So

% assert(isequal(sort(A), sort(B)))

Is a very efficient solution.

A = randperm(1e6, 1e6);
B = randperm(1e6, 1e6);
tic
for k = 1:10
  isequal(sort(A), sort(B));
end
toc
Elapsed time is 1.138481 seconds.
tic
for k = 1:10
  all(ismembc(A, sort(B)));  % Internal helper of ISMEMBER
end
toc
Elapsed time is 1.453001 seconds.

If repeated elements are existing:

A = randi([0,1e3], 1, 1e6);
B = randi([0,1e3], 1, 1e6);
tic
for k = 1:10
  isequal(unique(A), unique(B));
end
toc
Elapsed time is 0.676562 seconds.
tic
for k = 1:10
   numel(A) == numel(B) && all(ismember(A, B));
end
toc
Elapsed time is 0.980030 seconds.
tic
for k = 1:10
   As = sort(A);
   Au = As([true, diff(As) ~= 0]);  % Remove repeated elements
   Bs = sort(B);
   Bu = Bs([true, diff(Bs) ~= 0]);  % Remove repeated elements
   isequal(Au, Bu);
end
toc
Elapsed time is 0.781304 seconds.

In R2018b the last method is faster than isequal(unique(A), unique(B)). Try this locally.

1 个评论
显示 -1更早的评论隐藏 -1更早的评论

Bill Tubbs 2021-10-18

编辑：Bill Tubbs 2021-10-18

在 MATLAB Online 中打开

Thanks for the timings. Only assert(isequal(sort(A), sort(B))) produces the desired result in the case of unordered lists (not sets) so I guess there is no other option.

Also, note that these solutions you proposed do not produce the correct result:

assert(~all(ismembc([1 2], sort([1 2 3]))))

Assertion failed.

A = [1 2 2]; B = [1 2 3];
assert(~(numel(A) == numel(B) && all(ismember(A, B))))

Assertion failed.

请先登录，再进行评论。

Check for equality in the contents of two arrays ignoring order

0 个评论
显示 -2更早的评论隐藏 -2更早的评论

采纳的回答

7 个评论
显示 5更早的评论隐藏 5更早的评论

更多回答（2 个）

0 个评论
显示 -2更早的评论隐藏 -2更早的评论

1 个评论
显示 -1更早的评论隐藏 -1更早的评论

另请参阅

类别

标签

产品

版本

Community Treasure Hunt

Check for equality in the contents of two arrays ignoring order

0 个评论 显示 -2更早的评论隐藏 -2更早的评论

采纳的回答

7 个评论 显示 5更早的评论隐藏 5更早的评论

更多回答（2 个）

0 个评论 显示 -2更早的评论隐藏 -2更早的评论

1 个评论 显示 -1更早的评论隐藏 -1更早的评论

另请参阅

类别

标签

产品

版本

Community Treasure Hunt

0 个评论
显示 -2更早的评论隐藏 -2更早的评论

7 个评论
显示 5更早的评论隐藏 5更早的评论

0 个评论
显示 -2更早的评论隐藏 -2更早的评论

1 个评论
显示 -1更早的评论隐藏 -1更早的评论