The final version is now ready, and I confirm bplus's observation that the file falcon.h needs to be in the QB64 folder, but no other part of InForm needs to be present.
The bplus search method gives a much improved search time, now about 0.1s. This compares to 0.05s which the full bplus method gives. My sort method for the found words slows it down a little and Inform increases the time by a tiny fraction. Even on a slow machine of mine it's pretty instantaneous. We are there!
I thought that I might try to understand the binary search method in detail, and so I went to Wikipedia's expert where the following is given:
Procedure
Given an array A of n elements with values or records A0, A1, ..., An-1, sorted such that A0 = A1 = ... = An-1, and target value T, the following subroutine uses binary search to find the index of T in A.
1. Set L to 0 and R to n - 1.
2. If L > R, the search terminates as unsuccessful.
3. Set m (the position of the middle element) to the floor, [the greatest integer less than or equal to], (L + R)?/?2.
4. If Am < T, set L to m + 1 and go to step 2.
5. If Am > T, set R to m - 1 and go to step 2.
6. Now Am = T, the search is done; return m.
This iterative procedure keeps track of the search boundaries with the two variables. The procedure may be expressed in pseudocode as follows, where the variable names and types remain the same as above, floor is the floor function, and unsuccessful refers to a specific variable that conveys the failure of the search.
Our dictionary array has elements from 1 to 155237 (rather than from "0 to n-1"), so just add 1 to everything.
Then, the following routine (which I have always used in the past) follows this procedure exactly:
Located` = False: P0& = 1: P100& = Entries&
P50&
= INT((P0&
+ P100&
) / 2) Located` = True
P0& = P50& + 1
P100& = P50& - 1
You can see that it works by thinking through an array with 1 to 4 elements and then with 1 to 5 elements. So, I have used this method in the search function instead of bplus's. In the actual Trackword program, the BIT variable Located` is replaced by a BYTE variable Located%% as BIT variables are not successfully transferred to/from Functions or Subroutines.
I constructed a program which created an ordered dictionary file with elements 1 to 150,000 and then checked that every element is correctly found and that any word between every element is not found and that a word before and a word after the dictionary elements is not found.
The Wikipedia instruction is that rounding down must be used (as does this function), but I think that because of the P0& = P50& + 1 and P100& = P50& - 1 statements, rounding up also probably works. Anyway, I'm confident that we've done it correctly.
The simplest procedure for me will be to replace the User Manual in the first section of this post with my updated version, but there is no "Modify" procedure on this website. Is there a way to modify what's already there? If I've missed the obvious in usage of the site, I apologise.
Richard
