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

조회 수: 14 (최근 30일)
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.
  댓글 수: 6
Adam Danz
Adam Danz 2021년 8월 17일
As others have mentioned above, logical indexing is faster than subscript indexing. What is the reason you need to find the 1s (true) and 0s (false)? Sometimes it is necessary to do so but most of the time it can be avoided.
AliHg
AliHg 2021년 8월 17일
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
Adam Danz 2021년 8월 17일
편집: Adam Danz 2021년 8월 17일
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).
  댓글 수: 1
AliHg
AliHg 2021년 8월 19일
Thanks, Adam, for your detailed response.
Both of the functions you suggested worked perfectly, but the second one was a bit faster.
I appreciate your time and energy.

댓글을 달려면 로그인하십시오.

추가 답변 (0개)

카테고리

Help CenterFile Exchange에서 Logical에 대해 자세히 알아보기

Community Treasure Hunt

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

Start Hunting!

Translated by