A faster way of finding historical highs/lows

[Humpdydum]

"Peter Hansen" <peter at engcorp.com> wrote in message
news:SN2dnT9ob92aPFTdRVn-gQ at powergate.ca...
> Eamonn Sullivan wrote:
>
> > 1. Find the most recent date when there was an equal or higher (or
> > lower) value than X.
>
> The fastest algorithm might depend on how you use the data, as well.
> For example, do you update the data often, and search it rarely,
> or update it rarely and do the search very often?  If searching
> many times between updates, some preprocessing will likely make things
> go much faster.
>
> Both of your examples sound to me like they would benefit by
> using sort(), then a binary search.  Sort is very fast relative
> to things like the Python loops you are doing, so using it to
> prepare the data before the search can be a good step.

One thing to keep in mind there is that it depends what is the "average"
number of iterations you expect to have to make before finding a value. If
you only have to go back about 50 data points on average to find a peak,
sorting 100000 items might be overkill. Yet, if you sort once and do a large
number of searches, may well be worth it. If new values can be added into a
sorted container, and get put in the right spot, you only need to sort once
too. Etc.

Oliver