CODEWITHSUNDEEP
arraysmatlab
Da Beast
Da Beast

Reputation: 13

What is the fastest way to check if a matrix is an element of an 3d array?

I have an 3d binary array M(x,y,z) consisting of only 0s and 1s, then at each timestep I am given an binary matrix A(x,y), then I need to check if A(x,y)=M(x,y,z) for some z, and if not then I add it at the end of M with M(x,y,end+1)=A(x,y). Is there a way to do this which is faster then checking every z until an equality is found?

I tried looping over every z, but then I thought it should be possible to precompute something aout M that allows us to check multiple z with 1 comparison.

Upvotes: 1

Views: 276

Answers (2)

Edric
Edric

Reputation: 25140

Premature optimisation being the root of all evil, instead of trying to do anything fancy, I would simply try and use MATLAB's array notation and vectorisation and then later worry about optimisations. I haven't tested, but there's a decent chance that just vectorising things will be pretty reasonable since it makes the memory accesses required uniform. Here's how I'd do it:

>> M = rand(3,4,7) > 0.5;  % Example data
>> A1 = rand(3,4) > 0.5;   % (Probably) not a page of M
>> A2 = M(:,:,3);          % Page 3 of M
>> find(all(A1==M, [1 2])) % Use implicit expansion to compare
ans =
  0x1 empty double column vector
>> find(all(A2==M, [1 2]))
ans =
     3

This uses implicit expansion (introduced R2016b) in the Ax == M piece, and then uses the relatively recent (introduced in R2018b) vectorised dimension specifier to all for the "reduction" piece.

As per @Wolfie's comment, if you only need to know whether (and not where) a page is present, you can use any instead of find

if any(all(A2==M, [1 2]))
    % Page was present
else
    % Page not already present
end

Upvotes: 3

Ander Biguri
Ander Biguri

Reputation: 35525

Obviously there is no way of doing it without checking all of them.

However if you are trying to find a faster way, we can borrow from the image processing literature where they use "image integrals". Simply compute sum(M,[1,2]) for each z slice and store it in an array. When a new A comes, compute sum(A(:)) and compare to the list. Then only fully compare such indices of z that match in integral with the new matrix.

Depending on the nature of the matrices, you may need to find a different metric that is not the integral, as your application may produce normalized matrices or something like that. Just find a metric that is different enough and easy to compute. Image integrals are really good for natural images.

Upvotes: 3

Related Questions