check ismember for each element individually

Hello all,

I wonder if there is any smart way checking the indices of every individual elements in an array, in another array.

For example,given an input

a=[ 1 2 3 3 5 6 6];
b=[1 2 3 5 6];

I want to check where is each element of b is located in a

for example: for b(1), the location in a) would be:

[1 0 0 0 0 0 0] 
%or 
a(1)

for b(3), it then would be:

[0 0 1 1 0 0 0] 
%or
a(3,4)

of course I can do it using For loop, for speed reason I need to avoid it.

Answer 1

[Jan]

You want to get a logical vector for each element, which is TRUE for the matching elements. Then this is efficient:

a = [1 2 3 3 5 6 6];
b = [1 2 3 5 6];
match = (b.' == a)

match = 5×7 logical array
   1   0   0   0   0   0   0
   0   1   0   0   0   0   0
   0   0   1   1   0   0   0
   0   0   0   0   1   0   0
   0   0   0   0   0   1   1

This works with auto-expanding since R2016b. For older Matlab versions:

match = bsxfun(@eq, b.', a)

If you want the indices instead, a loop is nice and efficient (I assume, you have this already, but maybe another user might be interested):

indices = cell(size(b));  % Pre-allocate
for k = 1:numel(b)
   indices{k} = find(b(k) == a);
   
   % This would waste time to create a temporary cell:
   %   indices(k) = {find(b(k) == a)};
end

[Xingda Chen]

Jan you the boss, exactly what I am looking for.

Answer 2

[Chunru]

Doc ismember to see if it meets your requirement:

a=[ 1 2 3 3 5 6 6];
b=[1 2 3 5 6];
[Lib, Loca] = ismember(b, a)

Lib = 1×5 logical array
   1   1   1   1   1

Loca = 1×5

1 2 3 5 6

a(Loca)  % Loca is the the location of the first appearance of b in a

ans = 1×5

1 2 3 5 6

[Xingda Chen]

I tried that as well. Problem is I need the location of all apreances, not the first.

[Chunru]

%% arrayfun
a=[ 1 2 3 3 5 6 6];
b=[1 2 3 5 6];
a = randi(100, 1e6, 1);
b = randi(100, 1e3, 1);
tic
cac = arrayfun( @(ii) find(a==ii), b, 'uni',false );
toc

Elapsed time is 2.493500 seconds.

% Elapsed time is 1.798082 seconds.

%% for loop
tic
cac1 = cell(length(b), 1);
for i=1:length(b)
    cac1{i} = find(a==b(i));
end
toc

Elapsed time is 2.050463 seconds.

% Elapsed time is 1.571855 seconds.

%% ismember
% This is fastest.
% it use sort (faster) and stop when 1st appearance is found
tic
[Lib, Loca] = ismember(b, a);
toc

Elapsed time is 0.108364 seconds.

%% array expansion, Jan's answer below
tic
match = (b.' == a)';
toc

Elapsed time is 1.722124 seconds.

[Jan]

Thanks for the useful speed comparison. arrayfun is 10% slower than a loop. That ismember is much faster with its binary search is interesting, but it replies a different result.

In your code for the array expansion method, 60% are spent in the final transposition, which can be omitted:

a = randi(100, 1e6, 1);
b = randi(100, 1e3, 1);

tic
match = (b.' == a).';
toc
% Elapsed time is 1.836326 seconds.  (i7, Matlab R2018b)

tic
match = (b.' == a);
toc
% Elapsed time is 0.642080 seconds.

tic
match = (b == a.');
toc
% Elapsed time is 0.553570 seconds.

And if you store the rows of the output in a cell:

tic
cac1 = cell(length(b), 1);
for i=1:length(b)
    cac1{i} = (a==b(i));  % Without FIND
end
toc
% Elapsed time is 0.528209 seconds.

By the way: Matlab R2009a:

% Elapsed time is 3.368870 seconds.
% Elapsed time is 1.358478 seconds.
% Elapsed time is 1.219993 seconds.

Answer 3

[per isakson]

The function arrayfun() does the trick (i.e. hides the foor-loop)

a=[ 1 2 3 3 5 6 6];
b=[1 2 3 5 6];
cac = arrayfun( @(ii) find(a==ii), b, 'uni',false )

cac = 1×5 cell array
    {[1]}    {[2]}    {[3 4]}    {[5]}    {[6 7]}

cac{3}

ans = 1×2

3 4

[Xingda Chen]

I never used arrayfun() before, but the doc looks like it runs at the same level of speed as a loop, the reason I was avoiding the loop in the first place is for speed reason.

[Image Analyst]

For loops are fast - almost as fast as vectorized (depending on the operations) and sometimes faster. Run the attached demo to see:

Vectorized won 26 times out of 1000 = 2.6%.

For loop won 974 times out of 1000 = 97.40%.

The average time for the vectorized method = 4.5891e-06.

The average time for the for loop method = 4.1571e-06.

I did a million comparisons and the difference was less than a microsecond. Just how much speed do you need? How big are your arrays?

[Chunru]

Loop in newer matlab is no longer the enemy of speed. Try to use it! See the test above.

[Xingda Chen]

i guess i will for loop then.

My process is quite large. at big picture i am dealing with ~500M iterations averaging 100 times, most of the temp data are not stored so memeory isn't an issue but i am trying the avoid for loop as much as i can

[Jan]

@Chunru: "Loop in newer matlab is no longer the enemy of speed." I can confirm this. In addition for loops tend to be easier to write, read and maintain. By the way, "newer" means the Matlab version, which has introduced the JIT acceleration for loops, and this was Matlab R6.5, so the rumor of slow loops is outdated for over 20 years now.