Efficient searching to find the first element of an array meeting a condition

Question

Mohammad Shojaei Arani 2023-8-24

0
链接

此问题的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/2012317-efficient-searching-to-find-the-first-element-of-an-array-meeting-a-condition

回答： C. Rithiya 2023-9-6

采纳的回答： Florian Bidaud

Hello,

If a vector is given and the task is to find the first element fulfilling a condition then we use the

command 'finb(...,1)'. However, imagine that checking whether any member of my vector meets

the condition is going to be computationally expensive. In such a case the linear search is not a good idea.

An example:

f = @(x) rand(x);

find(f(1:10)>0.5);

Note that in this example it does not take so much time to check the 'condition' (i.e., wether it is bigger than 0.5) but in my actuall problem it is really expensive. So, my question is this: is there an efficient way to find the first element of an array fulfilling a condition?

Thanks in advance!

Babak

0 个评论
显示 -2更早的评论隐藏 -2更早的评论

请先登录，再进行评论。

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

Answer 1

Florian Bidaud 2023-8-24

1
链接

此回答的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/2012317-efficient-searching-to-find-the-first-element-of-an-array-meeting-a-condition#answer_1293112

编辑：Florian Bidaud 2023-8-24

在 MATLAB Online 中打开

EDIT: See @Bruno Luong answer, a simple for loop will actually be faster.

Depending on your data, you can split the search into pieces.

Let's say there the probability of your condition being met is 1/10.

Then there is a rather big probability that it is met in the first 10 values of your dataset, therefore you can split the search into vectors of 10 elements.

With your exemple, we could split the search into vectors of 2 because there is one chance out of two that the condition is met.

Provided that the matrix is already stored (Which I guess is the case for you ?), this could give something like the following code.

How to smartly split the data is the tricky part, it is supposing you already have a feeling about the probability of your condition being met.

a = f(1:12);
tic
find(a>0.5,1)
toc
ans =
     1
Elapsed time is 0.425812 seconds.
tic
p = 2; % 1/Probability
i = 0;
while true 
    b = a(i*p+1:(i+1)*p);
    I = find(b>0.5,1);
    if ~isempty(I)>0
        break
    end
    i = i+1;
end
value = i*p+I
toc
value =
     1
Elapsed time is 0.027613 seconds.

Now if we reduce the probability :

tic
find(a>0.999,1)
toc
ans =
        1550
Elapsed time is 0.396268 seconds.
tic
p = 1000; % 1/Probability
i = 0;
while true 
    b = a(i*p+1:(i+1)*p);
    I = find(b>0.999,1);
    if ~isempty(I)>0
        break
    end
    i = i+1;
end
value = i*p+I
toc
value =
        1550
Elapsed time is 0.026435 seconds.

Or even more:

tic
find(a>0.99999,1)
toc
ans =
      232137
Elapsed time is 0.387584 seconds.
tic
p = 100000; % 1/Probability
i = 0;
while true 
    b = a(i*p+1:(i+1)*p);
    I = find(b>0.99999,1);
    if ~isempty(I)>0
        break
    end
    i = i+1;
end
value = i*p+I
toc
value =
      232137
Elapsed time is 0.026697 seconds.

1 个评论
显示 -1更早的评论隐藏 -1更早的评论

Mohammad Shojaei Arani 2023-8-24

Hello Florian,

Thanks for your kind response. Well, in my problem I do not know the probability of meeting the

condition, unfortunately. But you answer is helpful for me and hoefully I find a way. First, I thought to do it using a sort of binary search but unfortunately it is not possible.

If I simplify my problem, then I have a vector of 0's and 1's where it is computationally expensive to say which element is 1 or 0. So, the question is to find the first '1' (when the condition is met) in this array. Aparently the find command follows a linear searching strategy which is expensive for my problem.

Thanks again!

请先登录，再进行评论。

Answer 2

Bruno Luong 2023-8-24

2
链接

此回答的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/2012317-efficient-searching-to-find-the-first-element-of-an-array-meeting-a-condition#answer_1293152

编辑：Bruno Luong 2023-8-24

在 MATLAB Online 中打开

just fo the obvious for loop

for i = 1:length(x)
    if expensive_check_for_meet_condition(x(i))
        ifind = i;
        break
    end
end

for-loop the most fundamental statement in any programming language often neglected by MATLAB users

6 个评论
显示 4更早的评论隐藏 4更早的评论

Bruno Luong 2023-8-24

编辑：Bruno Luong 2023-8-24

If you know how to sort the array so that the condition meet becomes stronger from start to the end, meaning the expensive_check_for_meet_condition(x) always returns 0s followed by the 1s, a dichotomy (binary) strategy search can be adopted. You cut in half the array check the middle, depending on the test value, you skip the left or right side until your interval reduces to 1 element.

Mohammad Shojaei Arani 2023-8-25

Unfortunately, it is not often the case that my set comes with 0's first and then 1's apear. So, unfortunately, I am not able to perform a binary serch.

请先登录，再进行评论。

Answer 3

Torsten 2023-8-24

0
链接

此回答的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/2012317-efficient-searching-to-find-the-first-element-of-an-array-meeting-a-condition#answer_1293077

编辑：Torsten 2023-8-24

"find" will use the "first" option by default which means that the command will return the first occurence of the event and will not search further.

4 个评论
显示 2更早的评论隐藏 2更早的评论

Florian Bidaud 2023-8-24

Whislt it's true, the find function will still have to deal with the whole array, consuming unnecessary time if the condition is met early.

Mohammad Shojaei Arani 2023-8-24

Yes Florian,

This is what I was guessing as well. The 'find' command 'NEEDS' to know the set it wants to search within first, unfortunately.

请先登录，再进行评论。

Answer 4

C. Rithiya 2023-9-6

0
链接

此回答的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/2012317-efficient-searching-to-find-the-first-element-of-an-array-meeting-a-condition#answer_1303401

a = f(1:12); tic find(a>0.5,1) toc ans = 1 Elapsed time is 0.425812 seconds. tic p = 2; % 1/Probability i = 0; while true b = a(i*p+1:(i+1)*p); I = find(b>0.5,1); if ~isempty(I)>0 break end i = i+1; end value = i*p+I toc value = 1 Elapsed time is 0.027613 seconds.