Re: Access Key for a Sub File ?

["Simon Coulter" <shc@xxxxxxxxxxxxxxxxx>]

Hello James, Booth, et al:

Another interesting topic!  Just a couple of comments:

The LOKUP (and LOOKUP) operation is a linear searche therefore an average of 
(N+1)/2 comparisons.  A sorted 
array allows the search to stop when the search value has been exceeded (in 
either direction).

I don't think it is appropriate for the compiler to automatically perform a 
binary search because the array 
MUST be sorted for a binary search to work.  A linear search doesn't require 
the programmer to sort the array 
first although there are advantages to doing so.  Perhaps what we need is a 
LOOKUP(B) operation code?

Using a linear search is useful when the programmer has knowledge of the data 
being searched, for instance if 
the most common data is at the front or end of the array the actual number of 
operations required by a linear 
search may be significantly less then the average.

James, your maths is wrong at the fifth iteration.  The correct answer is 1093 
(1093.5 actually) but it 
doesn't change the outcome.  Also the calculation to determine getindex seems 
overly complex.  The usual form 
is simply (lowvalue + highvalue)/2.  (The perfect algorithm also increments 
lowindex and decrements highindex 
depending on which half of the remaining elements the search value is expected 
-- since you have already 
checked that element it can be discarded -- but this only marginally improves 
the chance of finding the 
desired value as N gets very large).

A binary search operates at worst as log base 2 (N) therefore for sorted data a 
binary search will require 
less comparisons when the number of elements exceeds 6 -- although Booth's 
point about whether the user would 
notice is valid and for practical purposes 100 elements is a good number 
(linear search averages 50 
comparisons, binary search at most 7 comparisons).

Further reading can be found in Knuth Vol. 3.

Regards,
Simon Coulter.

«»«»«»«»«»«»«»«»«»«»«»«»«»«»«»«»«»«»«»«»«»«»«»«»«»«»«»«»«»«»«»«»«»«»
«» FlyByNight Software         AS/400 Technical Specialists       «»
«» Eclipse the competition - run your business on an IBM AS/400.  «»
«»                                                                «»
«» Phone: +61 3 9419 0175      Mobile: +61 0411 091 400           «»
«» Fax:   +61 3 9419 0175      mailto: shc@flybynight.com.au      «»
«»                                                                «»
«» Windoze should not be open at Warp speed.                      «»
«»«»«»«»«»«»«»«»«»«»«»«»«»«»«»«»«»«»«»«»«»«»«»«»«»«»«»«»«»«»«»«»«»«»
//--- forwarded letter -------------------------------------------------------
> X-Mailer: Mozilla 4.5 [en] (WinNT; I)
> MIME-Version: 1.0
> Date: Fri, 19 Feb 99 10:59:29 -0800
> From: email@james-w-kilgore.com
> To: MIDRANGE-L@midrange.com
> Reply-To: MIDRANGE-L@midrange.com
> Subject: Re: Access Key for a Sub File ?

> 
> Joel,
> 
> I don't have access to a machine to do a dedicated test of lokup vs
> chain.
> 
> Just doing some figuring off the top of my head, let's say you have an
> array and subfile which each contain 5000 entries.  Doing a lokup or
> looping chain one could expect 2500 compares or get operations per
> "position to" on an average.
> 
> Let's say the entry you want is at 1234, halving would read:
> 
> getindex=(((high index-lowindex)+1)/2)+(lowindex-1)
> 
> low index     high index      getindex
> 1             5000            2500    
> 1             2500            1250
> 1             1250            625
> 625           1250            937
> 937           1250            1033
> 1033          1250            1136
> 1136          1250            1193
> 1193          1250            1221
> 1221          1250            1235
> 1221          1235            1228
> 1228          1235            1231
> 1231          1235            1233
> 1233          1235            1234 done
> 
> 13 gets/compares would just *have* to be quicker.  Also, doubling the
> size of the array only adds one more get/compare instead of doubling the
> search time. Actually, we stop halving when highindex-lowindex is <=
> page size so we would have set the subfile top at 1231 and displayed the
> page.  (3 less gets)
> 
> IMO, arrays or other techniques are all viable, but we don't have the
> processor space to store thH additional information an array would
> require.  Budgets and all that.
> 
> James-W-Kilgore
> email@James-W-Kilgore.com
> 
> 
> Joel Fritz wrote:
> 
> > 
> > My real question is:  OK, you've got a lot of records in your subfile,
> > enough to warrent a binary search (a cool idea, I hadn't thought of doing it
> > in a subfile).  Is there a significant performance difference between doing
> > this in an array and a subfile?
> +---
> | This is the Midrange System Mailing List!
> | To submit a new message, send your mail to MIDRANGE-L@midrange.com.
> | To subscribe to this list send email to MIDRANGE-L-SUB@midrange.com.
> | To unsubscribe from this list send email to MIDRANGE-L-UNSUB@midrange.com.
> | Questions should be directed to the list owner/operator: david@midrange.com
> +---
> 

+---
| This is the Midrange System Mailing List!
| To submit a new message, send your mail to MIDRANGE-L@midrange.com.
| To subscribe to this list send email to MIDRANGE-L-SUB@midrange.com.
| To unsubscribe from this list send email to MIDRANGE-L-UNSUB@midrange.com.
| Questions should be directed to the list owner/operator: david@midrange.com
+---