From: "Michael D. Kersey" 
Subject: Re: DESPERATE: Indexed files in QBasic ??
 
Seamus BROWNE wrote:
>
> Hi,
> I have written a few progs with Qbasic.
> Some of them need to lookup data and find an equivalence:
> say , in a table with two fields Refno and Title,
> lookup the Refno "12345" and retrieve Title  "War and Peace".
>
> I do this using DATA and READ to build a DIM table then
> run along down the DIM table till I find the Refno an dthen grab the Title.
>
> This may be a slow way of doing things but I can find any other way.
> So ...
> Q1. Is there no way to have an Indexed file in Qbasic ?
> Q2. Is there any other Basic that woul do the job OK without me having to
> re-write my progs?
>
> Thanks.
> Pls reply by e-mail.
> Seamus BROWNE at Partage
 
How many rows do you have in the table? Unless it is large, your method
is pretty good. Reason is that searching a DIM table in memory is very
fast compared with reading a disk file.
 
You could sort the rows in the table in "refno" order and do a binary
search for a match: that would speed up the program.
 
Or you could use a "hash" table:
1) DIM the table so it is the next prime number, say aprime, larger than
the amount of data that you have,
2) READ the inputs and store each of them into the row numbered MOD(
refno,  aprime). This will sometimes cause 2 or more refno's to go to
the same row. This is called a "collision". To handle collisions, if a
row is already occuppied, then search forward until an empty row is
found and put the record there.
 
To search the hash table:
1) compute row = Mod(refno1, aprime)
2) go to that row and get it's refno,
3) if refno=refno1 then you've found the correct row,
4) otherwise search forward looking for a match to refno.
 
BTW if, when you search forward, you get to the end of the table, you
"wrap around" to the start of the table.
 
A hash table can be very quick. If "aprime" is large, then the table is
sparsely populated and you usually get a "hit" on the first attempt.
 
HTH,
Mike Kersey
 
*** QwkNews (tm) v2.1
 * [TN71] Internet Newsgroup: alt.lang.powerbasic
--- GEcho 1.20/Pro
---------------