Re: I'd be interested in a discussion on the topic of LOOKUP vs. %LOOKUP

[Simon Coulter <shc@xxxxxxxxxxxxxxxxx>]

On 13/01/2005, at 10:18 AM, Booth Martin wrote:

> I have a program that must compile to target release V4R2.  It has a 
> process
> that needs to be called repeatedly and it is a pig for time.  I can
> substantially reduce the number of times it is called by saving the 
> result
> to an array and checking the array first.
>
> There are two ways to check the array that I am aware of.  LOOKUP and
> %LOOKUP.   The difference in performance appears to be a factor of 10. 
>  Is
> that to be expected in your opinion?  Can LOOKUP take 25 minutes to 
> run, and
> %LOOKUP take 4 minutes?

LOOKUP is a linear search therefore the elapsed time is a function of 
the array size and on average will take N/2 lookups to find the search 
value.

%LOOKUP is a binary search (if the array is sorted) therefore will be 
much faster over non-trivial data sets and on average will take lg N 
lookups.

Given a 100 element array LOOKUP will, on average, perform 50 
comparisons before finding the search value presuming the search value 
is in the array. It will perform 100 searches (if the array is not 
sorted) if the search value is not in the array. %LOOKUP does the same 
if the array is not sorted but if it is sorted then it will stop after 
at most 5 comparisons.

> Of course, %LOOKUP won't compile to V4R2 anyway.

True, but you could prototype the C bsearch() function and use that all 
the way back to v3r2 and v3r6.

> So, what say you?  How to solve this pig of a performer?

Use bsearch() or build the array from the end and control the starting 
position so you search only populated elements.

Regards,
Simon Coulter.
--------------------------------------------------------------------
   FlyByNight Software         AS/400 Technical Specialists

   http://www.flybynight.com.au/
   Phone: +61 3 9419 0175   Mobile: +61 0411 091 400        /"\
   Fax:   +61 3 9419 0175                                   \ /
                                                             X
                 ASCII Ribbon campaign against HTML E-Mail  / \
--------------------------------------------------------------------