Linear Searches

[gids.rs@sasktel.net]

Linear Searches

Linear, of anything, is great if you only have to process, search or sort that list of items just once.  It is very easy to implement, easy to understand and easy to explain.  You search every item from start to finish until your criteria is met.  Then you act upon that criteria, and then continue the search from that point until the criteria is met again.

But, and I say But, is there anything being overlooked to make linear searching even easier or faster.  I say there is.  What if you still went in a forward direction, but only looked at, say, every second item or third item.  Or even better.  Look at the last item in a group.

Whether we know it or not, lists always have groups.  Most groups are recognized by the alphabetical listing of titles.  But did you know that even consecutive numbers have groups.  Say for example, the numbers from 1 to 99.  All the numbers put together can be a group and each individual number can be considered a group.  Even each digit of a number can be grouped into something.  (tens, hundres, thousands)

It is these groups or grouping of something out of nothing, that can make searching, organizing and implementing, a lot less work and the processing much faster.

One example, I would like to talk about, is searching in an applesoft program.  And more direct, is a program called REM remover.  Of the few different REM remover programs I have looked over, they all do the same thing.  They start at the beginning, look at each byte of code, one at a time until a certain search criteria is met.  In this case, looking for the byte $B2, which is the reserved byte for REM.

While re-programming REM remover to work with my Command Line Environment program, an idea hit me to make removing REM's even faster.  In a standard applesoft program, there usually are way more program lines than there are lines with REMs in them.  Yet each program line still has to be searched from the beginning of its line, until its end.  If there are no REMs, then the search of the whole line was a total waste.  There is a lot of processing that did not need to take place.

So, I deduced, just like Sherlock Holmes, that since no program instructions can follow a REM, and reserved words have their high bit set and ascii characters do not, then only the last byte of each program line need be checked for a high bit condition.  If true, then the whole line can be skipped for searching for a REM.  That is a huge savings of processing time.  It helps that there are program pointers to the next line and all that is needed is to subtract 2 from the next line pointer.  2 is needed due to the zero that indicates the end of the line.

There are only two other conditions where the last byte of a line may be a low ascii alphabet character but still be a program instruction.  One is if a print statement with a line of text within quotes was on the line, but the trailing quotation mark was eliminated so the line ended with a low ascii character but after a print statement and not after a REM.

The second way is if the program line ends with a FP variable.  These are also low ascii but it is fairly rare to end a line with.  More often than not, a program ends with a reserved word like, RETURN and NEXT, or a closed bracket or even a number.  In these last two instances of a low ascii condition is met, then a whole line search will be triggered but both are very rare.

So, now we have our groups which are separated by the line numbers, we have our search criteria and we have our delimiters.  We can now put it all together and save time removing REMs and hopefully, learn to recognize groups to be organized where there are none.

Happy REMoving

Rob

Allowing Applesoft to play with the big boys