[Tutor] Efficiency and speed

[Steven D'Aprano]

On Sat, 20 Mar 2010 05:47:45 am James Reynolds wrote:

> This is a monte-carlo simulation.
>
> The simulation measures the expiration of something and those
> somethings fall into bins that are not evenly dispersed. These bins
> are stored in the nx list mentioned previously.
>
> So let's say you have the bins, a, b,c,d,e,f and you have the value z
> from the sample list where z >b and <= a. In this case, it should
> return the index value at position (a).

I'm not sure I understand completely. An example might help. I *think* 
you have a list like this:

nx = [10.0, 9.0, 7.0, 3.0, 2.0, 1.0]

and if you have a value like z = 9.8 you want to return the index 0. 
Correct?

That seems a bit funny. In my experience it is normal to have the bins 
in the opposite direction. I suppose it probably doesn't matter that 
much, but it does seem a bit unusual.

If nx is fairly short (say, less than 40 or 50 items), then the fastest 
way is probably a linear search, something like this:

def search_bins(nx, z):
    """Search bins nx for item z.

    >>> bins = [5.0, 4.0, 2.0, 1.0]
    >>> search_bins(bins, 1.2)
    2

    If z is not in the bins, returns -1:

    >>> search_bins(bins, 5.1)
    -1

    """
    for i, value in enumerate(nx):
        if z > value:
            return i-1
    return -1




-- 
Steven D'Aprano