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

[Joel Fritz <JFritz@xxxxxxxxxxxxxxxx>]

Sorry, I probably didn't make it clear that I was talking about a binary
search in RPG vs. the C function.  I think you're right about lokup.  I know
a hand coded linear search performs about the same.  For the first six
months I wrote RPG I was too lazy to learn the indicator positions for lokup
and wrote little three or four line routines for array lookup. 

> -----Original Message-----
> From: Jim Langston [mailto:jimlangston@conexfreight.com]
> Sent: Thursday, December 21, 2000 8:52 AM
> To: RPG400-L@midrange.com
> Subject: Re: lokup substitute--RE: Externalising opcodes (was:
> Converting to u pper case)
> 
> 
> 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
+---