shilling for my feature request [1926]

[Alex Tweedly]

At 15:46 22/08/2004 -0700, Mark Brownell wrote:


>So let's say that you have hundreds of points either in an array or comma 
>delimited. What would be the fastest way to get the value of the item just 
>less than 100 in this following example?
>
>1, 34, 67, 99, 109, 121, 133, 144, 155, (answer = item 4) -- 99
>
>Would I have to loop through each one checking each during a repeat for 
>the last item less-than 100 or is there a faster way to get the value in 
>item 4. Every time I can drop a repeat loop seems to be a way to optimize 
>the result based on speed issues.

If you have only have hundreds of points, then a loop may not be too bad.

However, since you know that data is ordered, you have other options.

If you have many hundreds, or thousands, then I would try out a binary 
search and compare its times to the simple repeat loop.

If you are enthusiastic, I'd try out a linear interpolation search as well 
- given the nature of the data, this might be noticeably better on average 
than binary search (but of course would be much worse in the worst case).

If you have many thousands, and you will be searching in the same data 
repeatedly, then you might build a balanced binary index tree or something 
more complicated - but you'd need to be very dependent on speed to consider 
this (and so you'd probably be better building an external to do it).

But a more fundamental question - why would you want to know that ? :-)

I'd guess it's because you have something like ....

    put the offsets of "<a>" of theText into tOff1
    put the offsets of "</a>" of theText into tOff2

and then your working through tOff2, find a value of 100 and want to find 
the matching (i.e. preceding) occurrence in tOff1.

You might consider doing something like ....
     repeat for each line L of tOff1
         put L & comma & "<a>" after tAllOff
     end repeat
     repeat for each line L of tOff2
        put L & comma & "</a>" after tAllOff
    end repeat
    sort tAllOff by item 1
and then working on the combined offset list.

Hmmmm - so maybe it would be worth asking for a single function to take a 
list of strings and put their offsets into a single list :
     put the offsets of "<a>,</a>" of myText into tAllOff
which would put
    1, <a>
    4, </a>
    9, <a>
   11, <a>
   25, </a>
   ... etc.
  into the list.   i.e. somewhat like  the earlier "split by string1 and 
string2" idea.

-- Alex.