Re: locate a value in an array

On 28 jan, 09:48, Klemens <jokulhl...@xxxxxx> wrote:
Hello together,

I have computed a bootstrap analysis spending most of the time in this
part where the bootstrap pdf is resampled.
Some random numbers are generated (n = 1000000) and these numbers pick
the bin from the cdf.
These picking is done in a loop starting at the lowest bin and stoping
when the respective bin has been found.
Because its the cdf, bins are not equidistant. The number of bins of
the cdf is 1000.
There is a great number of repetitions (n), so some precalculations
could be worth to do if the overall time of this part of the code
could be reduced. Are there any advanced techniques to  locate the
value's position in the cdf like subdividing the cdf, etc ... ?

Thanks for your help in advance !

Cheers,

Klemens

As the bounds of the bins are ordered, you can apply
a binary search to find the correct one. There are
plenty of code examples to be found on that (the corner
cases are a trifle tricky).

Binary search is O(ln N) instead of O(N), so that should
make a performance difference that could be significant.

Regards,

Arjen
.

Relevant Pages

  • locate a value in an array
    ... I have computed a bootstrap analysis spending most of the time in this ... part where the bootstrap pdf is resampled. ... These picking is done in a loop starting at the lowest bin and stoping ... Because its the cdf, bins are not equidistant. ...
    (comp.lang.fortran)
  • Re: locate a value in an array
    ... I have computed a bootstrap analysis spending most of the time in this ... These picking is done in a loop starting at the lowest bin and stoping ... Because its the cdf, bins are not equidistant. ... See other methods such as "Walker's Alias Method" for sampling from ...
    (comp.lang.fortran)
  • Re: rank deficient warning on nlinfit
    ... This function produces the bins, as well as the CDF ... I then try to see if I can fit a Gaussian CDF function to ... I'm going to assume that mu_bins is a vector of bin ...
    (comp.soft-sys.matlab)
  • Re: rank deficient warning on nlinfit
    ... This function produces the bins, as well as the CDF ... I then try to see if I can fit a Gaussian CDF function to ... I'm going to assume that mu_bins is a vector of bin ...
    (comp.soft-sys.matlab)