Fastest selection of a coordinate in 3d array that fulfills a condition?

1 次查看（过去 30 天）
Carson Purnell
Carson Purnell 2022-12-22
回答： Jan 2022-12-23
I have a relatively simple problem: I need to generate random coordinates of an array, but they must fulfill a condition. I thought find+ind2sub would make this easy to sample from condition-positive sets - and it does - but i was surprised to find that these are relatively slow, and on the arrays i'm using (>1e7 elements) it can take up to seconds. Needing to run this thousands of times makes that prohibitive.
Turns out that a loop is ~10-100 times faster merely generating completely random coordinates/indices and testing them for the condition. It's even more disparately faster with ever larger arrays, and approaches similarity only under extreme conditions (<<.001% fulfilling condition) in smaller arrays.
I'm guessing that this is the overhead of find+ind2sub exhaustively searching and indexing the entire array. Is there possibly a vectorized solution that avoids the overhead, or at least overcomes the loop through internal optimizations?
  3 个评论
显示 1更早的评论
Jan
Jan 2022-12-22
@Carson Purnell: I agree to Matt J. Please provide a small data set for the input and the wanted output. Then mention the typical dimensions of the problem. Afterwards we can serach an efficient method.
Carson Purnell
Carson Purnell 2022-12-22
A sufficient test case is using randi(10,500,500,200) to generate the array. The only output is a single randomly selected voxel within the array (as coordinates or a linear index) that satisfies a basic comparison, for this test case ==1 works.
Again, to make it clear: I do not need many random points from this single array. ind2sub would be fast at that. I need exactly one point, but quickly because i'm doing this for thousands of non-identical arrays.

请先登录，再进行评论。

请先登录，再回答此问题。

采纳的回答

Jan
Jan 2022-12-23
Ran in:
If the condition is not rare in the array, a gun-shot method can be very fast:
T = randi(10, 500,500,200);
tic
doSearch = true;
n = numel(T);
index = randi([1, n]);
while T(index) ~= 1
index = randi([1, n]);
end
toc
Elapsed time is 0.009403 seconds.
A comparison with an exhaustive search:
tic; % Matt J's suggestion:
logIndex=(T(:)==1); %logical index
n=sum(logIndex);
k=randi(n,1);
z=find(logIndex,k,'first');
result=z(end); %linear index
toc
Elapsed time is 0.159166 seconds.
If the data have a small range, this is working, but of course the less frequent the condition is true, the more likely is a huge run-time.

更多回答（1 个）

Matt J
Matt J 2022-12-22
编辑：Matt J 2022-12-23
Ran in:
Why not as follows? I don't know if it's as fast as you were hoping, but it definitely doesn't take seconds per iteration.
T=randi(10, 500,500,200); %hypothetical input
tic;
logIndex=(T(:)==1); %logical index
n=sum(logIndex);
k=randi(n,1);
z=find(logIndex,k,'first');
result=z(end); %linear index
toc
Elapsed time is 0.055249 seconds.
  1 个评论
Matt J
Matt J 2022-12-22
编辑：Matt J 2022-12-23
If you have the Parallel Computing Toolbox, there is substantial speed-up to be had from working on the GPU. This comparison used the GTX 1080 Ti:
T=randi(10, 500,500,200);
Tgpu=gpuArray(T);
timeit(@()doIt(T)) %on CPU
ans =
0.0828
gputimeit(@()doIt(Tgpu)) %on GPU
ans =
0.0126
function result=doIt(T)
logIndex=(T(:)==1);
n=sum(logIndex);
k=randi(n,1);
z=find(logIndex,k,'first');
result=z(end);
end

请先登录，再进行评论。

类别

在 Help Center 和 File Exchange 中查找有关 Multidimensional Arrays 的更多信息

标签

产品

Community Treasure Hunt

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

Start Hunting!

Translated by