1

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.

Wolfie
  • 27,562
  • 7
  • 28
  • 55
Da Beast
  • 13
  • 3
  • Did you try flattening the multipaged array `M` and then expanding `A` to match? Then you can do a direct comparison and find where they match. – Matt Mar 30 '22 at 15:22
  • 2
    When talking about improving performance, it would be good if you could [edit] your question to include a [mcve] against which we can test various approaches. Even your looping approach may be almost performance-optimal already. A sense of the size of the true size of `M` would also be helpful in case memory is a constraint – Wolfie Mar 30 '22 at 15:29

2 Answers2

3

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.

Ander Biguri
  • 35,140
  • 11
  • 74
  • 120
3

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
Edric
  • 23,676
  • 2
  • 38
  • 40
  • `find` can give you variable size output and linguistically using `any` instead of `find` would give you a quick logical check here for the presence of `A` in `M`, otherwise this looks like a good approach. It would be good to clarify which release "relatively recent" actually refers to in case someone wants to use this. – Wolfie Mar 30 '22 at 15:57
  • 1
    Hm, I must have been at MathWorks too long when features introduced in R2018b feel new to me. – Edric Mar 31 '22 at 11:57
  • Haha I still think of implicit expansion as "new" since my org was version locked to 15b for far too long :D Cheers Edric – Wolfie Mar 31 '22 at 12:48