# What is the fastest way to find zeros and ones indices in a 3D binary array?

4 views (last 30 days)
AliHg on 17 Aug 2021
Commented: AliHg on 19 Aug 2021
Hello all,
I have a (binary) 3D array, and I need to find zeros and ones indices. My algorithm calls this find function more than 1e8 times, so I need a faster function to get the job done.
I used something like this:
% mat1 in the 3D array
ind0 = find(mat1 == 0);
ind1 = find(mat1 == 1);
The above code takes too much time, so I am looking for a more efficient way. I wonder whether you know a substitute for the find function to reduce the runtime.
Is ind2sub function the best choice to go? If the answer is positive,how can I convert the row/column indices to the 3D array total indices?
Any help would be appreciated.
AliHg on 17 Aug 2021
Thank you all for your suggestions.
Let me elaborate more on the problem that I am facing. Below is the function that I am trying to execute as fast as possible.
function [mat2, i1page, i2page] = Swap(mat1)
mat1 = logical(mat1);
ind0 = find(mat1);
ind1 = find(~mat1);
i1 = randsample(ind0, 1);
i2 = randsample(ind1, 1);
mat2 = mat1;
mat2([i1 i2]) = mat1([i2 i1]);
[~, ~, i1page] = ind2sub(size(mat1), i1);
[~, ~, i2page] = ind2sub(size(mat1), i2);
end
Here mat1 is a 3D binary array. Mat2 is equal to mat1 with a slight difference that is a voxel got interchanged (swapped). i1page and i2page are two matrices associated with those voxels. In other words, I am trying to input a 3D array, swap a "zero" voxel with a "one" voxel, and find their corresponding slices.
I attached an image that shows my algorithm spends 116 seconds of its total 136 seconds runtime, dealing with this function. I have to mention that these runtimes would be way larger when I use the actual iteration number.

Adam Danz on 17 Aug 2021
Edited: Adam Danz on 17 Aug 2021
Here are two versions of your code that are faster than the original but they only shave off a sliver of time. I've timed 10 repetitions of each method using tic/toc and usually the second method is faster but due to variability, occasionally the first method is faster. The test input was 100x100x500. Both methods are consistently faster than your original version. The first is more readable so you can make the decision which one works best for you (or perhaps a better method will appear).
Both methods make the following simplications:
• Neither use find(). The find function is known to be very slow.
• Since mat2 is a duplicate of mat1 until the end, you can convert mat1 to mat2 at the beginning of the function and just work with mat2. That eliminates 1 line of code.
• No need to call ind2sub twice.
Method 1
mat2 = logical(mat1);
n = 1; % number of random selections
idx = 1:numel(mat2);
i1 = randsample(idx(mat2), n);
i2 = randsample(idx(~mat2), n);
mat2([i1 i2]) = mat2([i2 i1]);
% in this context the line above is
% the same as mat2([i1 i2]) = ~ mat2([i1 i2]);
[~, ~, ipage] = ind2sub(size(mat2), [i1,i2]);
% if n>1 and you need to separate the page numbers,
% i1page = ipage(1:numel(i1));
% i2page = ipage(numel(i1)+1:end);
Method 2
Method 2 differs from method 1 by replacing randsample which is also a bit slow.
mat2 = logical(mat1);
n = 1; % number of random selections
idx = 1:numel(mat2);
idxTrue = idx(mat2);
idxFalse = idx(~mat2);
i1 = idxTrue(randi(numel(idxTrue), n));
i2 = idxFalse(randi(numel(idxFalse), n));
mat2([i1 i2]) = mat2([i2 i1]);
% in this context the line above is
% the same as mat2([i1 i2]) = ~ mat2([i1 i2]);
[~, ~, ipage] = ind2sub(size(mat2), [i1,i2]);
% if n>1 and you need to separate the page numbers,
% i1page = ipage(1:numel(i1));
% i2page = ipage(numel(i1)+1:end);
Lastly, your input matrix appears to be a numeric array (otherwise, why would you need to convert it to logical?). Your output array, however, is logical. If you want consistency, you'll need to add double(mat2) somewhere to convert it back to numeric (assuming you're working with double precision values).
AliHg on 19 Aug 2021
Both of the functions you suggested worked perfectly, but the second one was a bit faster.
I appreciate your time and energy.