check condition if array A contain array B or not

82 views (last 30 days)
Example, I have:
A = [randperm(1e9,1e8)]';% array A contain 100,000,000 element
B = [randperm(1e5,1e4)]';% array B contain 1,000 element
How to determine if array A contain all element in array B or not? (I know the syntax: ismember(B,A). But the execution time is too long If the size of array A,B is large)
Example code(use ismember, and time consuming=43s) :
clear;clc;
A = [randperm(1e9,1e8)]';%generate 100,000,000 non-repeating random integers element with the value from 1-1,000,000,000
B = [randperm(1e5,1e4)]';%generate 1,000 non-repeating random integers element with the value from 1-10,000
if all(ismember(B,A,'rows')==1) %if A contain all element in B
disp('yes');%If condition is right, show "yes"
else
disp('no');%If condition is wrong, show "no"
end

Accepted Answer

ha ha
ha ha on 31 Mar 2018
Edited: ha ha on 9 Aug 2018
THE ANSWER IS(this below code(20s) is faster than use ismember(43s)):
clear;clc;
A = [randperm(1e9,1e8)]';%generate 100,000,000 non-repeating random integers element between value from 1-1,000,000,000
B = [randperm(1e5,1e4)]';%generate 10,000 non-repeating random integers element between value from 1-100,000
size_B=size(B,1);%define number of element in array B
C=intersect(A,B);%find intersection between A & B
size_C=size(C,1);%define number of element in array C
if size_C==size_B %if A contain all element in B
disp('yes');%If condition is right, show "yes"
else
disp('no');%If condition is wrong, show "no"
end
%the number of element in A will affect the time significantly

More Answers (2)

Image Analyst
Image Analyst on 31 Mar 2018
B will not be contained in A if you do it like that, with random numbers each being generated independently. However if B is in A you might try ismember(), strfind() or norxcorr2().
  14 Comments
Image Analyst
Image Analyst on 2 Apr 2018
No problem. I just interpreted it differently. I thought you wanted to know if B, as given, was in A, whereas you wanted to know if all the individual elements of B were anywhere in A at all regardless if the whole of B was in there or not. In other words, I was thinking that if you looked over A, could you see B embedded in there somewhere? While you didn't care if the elements of B were in there intact - next to each other in the original, given order - you just cared if the elements were there at all even if B were split apart into individual elements. Just a different interpretation of what "A contains B" means.

Sign in to comment.


Walter Roberson
Walter Roberson on 31 Mar 2018
ismember() first checks if the second parameter is sorted (a linear process), and if it is not sorted then it sorts it. Then ismember does binary searches for the first parameter within the sorted version of the second parameter.
In theory you can do a little better than this if you sort the first parameter as well, as you can use information about the search programs for one element to reduce the amount of searching that needs to be done for another element. However, the cost of doing the sort of the first parameter adds up as well; you would have to write the algorithm fairly carefully to be sure of coming out ahead.

Community Treasure Hunt

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

Start Hunting!