Re: lokup substitute--RE: Externalising opcodes (was: Converting to u pper case)

[Jim Langston <jimlangston@xxxxxxxxxxxxxxxx>]

Not that I have used the C call, but I have some familiarity with sorts and
search routines.

There are many many ways to do a sort or a search.  Although they do different
things, a sort and a search generally have the same type of logic.  I have found
tremendous speed differences in different algorithms.  I have always felt that
the LOKUP did a simple array traversal lookup.  Start in element one and keep
going down the array until you find the match.  This is the slowest type.  There
are many other types, but the lookup that C uses is probably similar to the 
bubble
sort (or is that the quick sort?  Can't remember which is which on those).  
Jump to
the middle of the array.  Is the number smaller?  If yes, jump to the middle of 
the
lower half, if not, jump to the middle of the upper half.

Calculations and experimentation shows us that with 100 elements and array 
traversal
search will take an average of 50 calculations to find a match which can take 
from one
to 100 calculations.  The bubble search, however, can take a maximum of 7 
calculations to
find a match!  The average is probably somewhere around 6 or so.  That is, for 
any number
from one to 100, you will always find the match within 7 calculations using 
this type of
lookup.

There are other types of sorts/lookups such as a binary/trinary tree but those 
are
generally used for index building.

Regards,

Jim Langston

Joel Fritz wrote:
> 
> Yes, same array, same data, same loop.  I suspect it has to do with pointer
> arithmetic in the C implementation vs array access by index in the RPG, but
> I can't claim to be an expert.  Then again, it may be that there's a better
> algorithm for the RPG version than the ones I've tried.  That wouldn't
> surprise me at all.
> 
> I'm curious what others' experience has been.
+---
| This is the RPG/400 Mailing List!
| To submit a new message, send your mail to RPG400-L@midrange.com.
| To subscribe to this list send email to RPG400-L-SUB@midrange.com.
| To unsubscribe from this list send email to RPG400-L-UNSUB@midrange.com.
| Questions should be directed to the list owner/operator: david@midrange.com
+---