Re: Access Key for a Sub File ?

[email@xxxxxxxxxxxxxxxxxxx (James W Kilgore)]

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 the 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
+---