Re: lookups and performance

[Hans Boldt <boldt@xxxxxxxxxx>]

Mail List wrote:
> Hi Rick,
>
> FWIW, %lookup has a 4th parm -- number of elements to search.  In other
> words, load 100 elements of a 1000-element array and do
>
>     x = %lookup(SearchFor: Array: StartElem: #ElemToSearch)
>
> With a binary search, I'm not sure there'd be a significant increase in
> performance.
> ...
>
> ----- Original Message -----
> From: "Richard B Baird"
>
> > is there an appreciable difference between that and back filling my array
> > with hivals and starting at the beginning?
> >
> > for example (on a much smaller scale - my array is set at 9999 with a
> > possibility of more than a 1000 valid iters, in otherwords, about 1/10th
> > full.

Peter is correct. The binary search is an O(log2(n)) algorithm, 
which roughly means that you have to search through a much bigger 
set of data to get an appreciable difference in search time. 
Roughly, it takes 10 iterations to search through an array of about 
1000 items. For an array of 1,000,000 items, the algorithm iterates 
20 times. So an array 1000 times bigger can be searched in only 
twice the time.

Yes, if you want significant performance improvements, do look 
elsewhere. Good profiling tools are essential in identifying the 
bottlenecks and in verifying that any change does indeed improve 
performance. The latter point is important since often changes made 
in the name of performance can be counter-intuitive.

Cheers! Hans