Finding the first element that meets a condition

classic Classic list List threaded Threaded
5 messages Options
Reply | Threaded
Open this post in threaded view
|

Finding the first element that meets a condition

BGreen
Hello all,

I have a sorted list of values and would like to find the index of the first element greater than some cutoff size. For example

min_val = 0.3;
arr = [.4, .8, .23, .19, .37];
arr_sorted = sort(arr);
index = find_first(arr_sorted,min_val);

Is there a better way to do this than a for loop? "find" would pull out every value that meets this condition and that would waste effort. On the other hand, I could use a while loop, but I would like to avoid looping if better methods exist.

first_index = 1;
while(arr_sorted(first_index)<min_val)
first_index += 1;
endwhile

- Brett Green


Reply | Threaded
Open this post in threaded view
|

Re: Finding the first element that meets a condition

nrjank
On Tue, Mar 10, 2020 at 2:00 PM Brett Green <[hidden email]> wrote:

If you're avoiding a loop, then by default you're going to be applying some operation to the entire array.  Find generally works pretty well.  
 
>> first_element = find(arr_sorted>min_val)(1)
ans = 3


Reply | Threaded
Open this post in threaded view
|

Re: Finding the first element that meets a condition

mmuetzel
Am 10. März 2020 um 19:05 Uhr schrieb "Nicholas Jankowski":
> On Tue, Mar 10, 2020 at 2:00 PM Brett Green <[hidden email]> wrote:
>
> If you're avoiding a loop, then by default you're going to be applying some
> operation to the entire array.  Find generally works pretty well.
>
> >> first_element = find(arr_sorted>min_val)(1)
> ans = 3

Or similarly:
first_element = find(arr_sorted>min_val, 1, 'first')

Markus


Reply | Threaded
Open this post in threaded view
|

RE: Finding the first element that meets a condition

Windhorn, Allen E [ACIM/LSA/MKT]
In reply to this post by BGreen
Brett,

From: Help-octave <[hidden email]> On Behalf Of Brett Green

> I have a sorted list of values and would like to find the index of the first
> element greater than some cutoff size. For example

> min_val = 0.3;
> arr = [.4, .8, .23, .19, .37];
> arr_sorted = sort(arr);
> index = find_first(arr_sorted,min_val);

> Is there a better way to do this than a for loop? ...

This looks like a root-finding problem, where the function whose root you
are finding is your list of sorted values, less min_val.  If the values are
distributed fairly uniformly, you could actually use a root finding routine.
Otherwise, a binary chop method would find the right value in a million
records with only 20 comparisons, much better than a linear search.

min_val =  0.30000
arr = sort(log(rand(1000000,1)+1));

function [ind, val, iter] = vsearch(arr,min_val)
  iter = 0;
  v1 = arr(1);
  v2 = arr(end);
  % Check for pathological values
  if (min_val<v1)
    ind = 1; % The first value is already greater than min_val
    return
  endif
  if (min_val>v2)
    ind = 0; % Error: no value in arr is greater than min_val
    return
  endif
  arl = length(arr);
  if (arl<1)
    ind = 0; % Error: no values in arr
    return
  elsif (arl<2)
    ind = 1; % Only one element, so that must be it
    return
  endif
  ind = fix((min_val-v1)/(v2-v1)*arl); % Guess where in the pack to find the value
  i1 = 1;
  i2 = arl;
  while (i2>i1+1)
    cv = arr(ind);
    if (cv<=min_val)
      i1 = ind;
    else
      i2 = ind;
    endif
    ind = fix((i1+i2)/2);
    iter++
  endwhile
  val = arr(ind);
endfunction

>> [ind, val, iter] = vsearch(arr,min_val)
ind =  349220
val =  0.30000
iter = 20

OK, this doesn't quite work -- it finds a value equal to min_val if there is one.
But you get the idea.  If you only have a few hundred items, "find" will be
better.

Regards,
Allen

Reply | Threaded
Open this post in threaded view
|

Re: Finding the first element that meets a condition

BGreen

On Tue, Mar 10, 2020 at 3:34 PM Windhorn, Allen E [ACIM/LSA/MKT] <[hidden email]> wrote:
Brett,

From: Help-octave <[hidden email]> On Behalf Of Brett Green

> I have a sorted list of values and would like to find the index of the first
> element greater than some cutoff size. For example

> min_val = 0.3;
> arr = [.4, .8, .23, .19, .37];
> arr_sorted = sort(arr);
> index = find_first(arr_sorted,min_val);

> Is there a better way to do this than a for loop? ...

This looks like a root-finding problem, where the function whose root you
are finding is your list of sorted values, less min_val.  If the values are
distributed fairly uniformly, you could actually use a root finding routine.
Otherwise, a binary chop method would find the right value in a million
records with only 20 comparisons, much better than a linear search.

min_val =  0.30000
arr = sort(log(rand(1000000,1)+1));

function [ind, val, iter] = vsearch(arr,min_val)
  iter = 0;
  v1 = arr(1);
  v2 = arr(end);
  % Check for pathological values
  if (min_val<v1)
    ind = 1; % The first value is already greater than min_val
    return
  endif
  if (min_val>v2)
    ind = 0; % Error: no value in arr is greater than min_val
    return
  endif
  arl = length(arr);
  if (arl<1)
    ind = 0; % Error: no values in arr
    return
  elsif (arl<2)
    ind = 1; % Only one element, so that must be it
    return
  endif
  ind = fix((min_val-v1)/(v2-v1)*arl); % Guess where in the pack to find the value
  i1 = 1;
  i2 = arl;
  while (i2>i1+1)
    cv = arr(ind);
    if (cv<=min_val)
      i1 = ind;
    else
      i2 = ind;
    endif
    ind = fix((i1+i2)/2);
    iter++
  endwhile
  val = arr(ind);
endfunction

>> [ind, val, iter] = vsearch(arr,min_val)
ind =  349220
val =  0.30000
iter = 20

OK, this doesn't quite work -- it finds a value equal to min_val if there is one.
But you get the idea.  If you only have a few hundred items, "find" will be
better.

Regards,
Allen

Thank you to all for the suggestions! I think I will just use "find" in the end.

- Brett Green