In order for this site to work correctly, and for us to improve the site, we need to store a small file (called a cookie) on your computer.
By continuing to use this website, you agree to our cookies and privacy policy.
  
Home page Home page Home page Home page
Pixel
Pixel Header R1 C1 Pixel
Pixel Header R2 C1 Pixel
Pixel Header R3 C1 Pixel
Pixel

RTP Series - RTP33

The LOCATE processor. Used for both LOCATE and LOCATE BY. The AREV version of LOCATE BY works using a binary chop algorithm unlike the G2.B version which uses a sequential search. The binary chop is many times more efficient for finding a sorted place within an array. (for those of you who have not encountered a binary chop before - the algorithm (assuming a sorted array) bisects the array and sees if the middle value is above or below the value being sought. It then takes the half that the value being sought is found in and bisects this. This new middle value is compared to the value being sought and the same process is repeated. This continues until a match is found and a value is returned. If there are 64K values to be checked, after one chop there will be 32K, after two chops 16K, after 3 8K, after 4 4K, after 5 2K, after 6 1K after 7 512, after 8 256, after 9 126, after 10 64, after 11 32, after 12 16, after 13 8, after 14 4, after 15 2 and the sixteenth comparison would yield the result. This is the worst case scenario! Sixteen comparisons in place of 64K comparisons - A significant improvement!) If any readers still use G2.B, we have a copy of $RTP33 which incorporates the new binary chop logic but for G2.B. This speeds up all manner of things, but especially the filing of records with large associated XREF records. Send us a disk and we'd be glad to send you the code.

One point however - if you know that the array is sorted and you want to check for the existence or non-existence of a value within the array (without setting a pos correctly for insertion), the LOCATE command is always faster than the LOCATE BY. Whilst this seems peculiar, it has to do with the algorithm design. Also remember that as pointed out in issue 1 of REVMEDIA, a LOCATE BY "AR" will return the same position for 1 as for 01.

(Volume 1, Issue 4, Pages 5,6)
Pixel
Pixel Footer R1 C1 Pixel
Pixel
Pixel
Pixel