#Help
6 messages in this thread
Hello Jim,
Ok, I've got to ask. Are you _the_ Jim Butterfield of the C64 days?
If so I have to thank you for all your help back when I didn't know a peek from
a poke. Because of people like you, understanding these wonderful little
machines became a lot easier.
> The traditional way to find an item in an ordered list is by a binary split
>search. In other words, you go to the middle of the list, and depending on
>whether your search value is higher or lower, move up or down 1/4 of the
length >of the list .. then 1/8, and so on.
Yes, I am familiar with this. I am opting to try something different, something
new. With each new program I try to improve my technique, and not rely on the
same old methods.
> If your material is purely alphabetic, that is, you can depend on the first
>character being A through Z, you can save time over the above method by
>building a list: where A starts, where B starts, etc. You don't have to
>search THIS index list; just go straight to the letter you want to find a
>starting point for your search.
I have been rolling this idea around, but I'm not sure it will be faster than
the binary split method. Deciding where to start looking will be quick, but
from there I still must locate the word in question.
> A variation on the above is the "linked list"; all the As are linked
>together, then all the Bs, and so on. Nice thing about links is that you can
>set them up to search on more than one key value.
This I haven't done before, I'll have to see what information I can dig up on
this.
> You'll undoubtedly get a number of suggestions about putting your data into
>a "tree" structure, where each above/below test points you to the next set of
>tests to do. There are many variations on this one.
I've heard of this type, and I'm trying to find some examples on this. Would
this not be similar to the binary split method, only reshaped into a tree?
I like the idea of having only two test to perform as with the binary split
(simplicity is best), would the same be possible with a tree method?
> If your objective is to find "hits" in the table – you don't care about
>values that will not turn out to find a match – you can go to a "hashing"
>technique. This is a little wasteful of memory, but it's real fast: by
>crunching together the alphabetic characters in mathematical fashion, you can
>generate an index number that will take you straight to the match, if it
>exists.
This sounds interesting, do you know of anyplace on-line I might look to find
an example or an in-depth description?
> Searching (and its cousin, sorting) is a major area of computer science
>study. Most of us cobble together something that works nicely for the
>application we have on hand.
As I'm beginning to see 🙂
Thanks for all your input regarding my question Jim. Programing is somewhat of
a passion of mine, and these types of hints from the experts helps a lot.
I'm currently taking a course in C and VB in the hopes of someday being able to
make a living programing. As of now I try to keep active by helping out where
I can, mostly with the ACE basic compiler by David Benn. I do the amigaguide
docs for him and try to answer a few questions for other users of ACE.
It's been a pleasure talking to you, brought back a lot of old memories 🙂
Best Regards -John
> Are you the Jim Butterfield of the C64 days?
Yup, and before the C64 days, too…
>> .. building a list (based on first character)..
> .. I'm not sure it will be faster..
For the sake of argument, let's say that your data is evenly distributed
between the 26 letters (VERY unlikely). You would have to do about FIVE
comparisons to get to the area of the first letter; and comparisons are usually
costly in processing time.
Now, let's try the initial letter thing, in quasi-Basic:
Index = ASC(UPPER$(string)) – 64
(This should bring index into the range 1 to 26)
Startpointer = List(Index)
Endpointer = List(Index+1)
No comparisons yet, but your list is down to (optimally) 1/26 of its
original search size. In practice, you might get 1/10. If you're doing names
in Scotland, where a large proportion start with "Mc..", you might need to vary
the approach and make a separate list for these.
>> .. tree structure
> .. I'm trying to find some examples of this ..
Tree structure coding is a whole state of mind. These are most useful, I
think, when the data is undergoing continuous update; you can slip extra stuff
into a tree with much less pain than the regular ordered list.
When you start reading up on it, check out a method called "B-trees". This
isn't a binary split; each branch on the tree can be a multi-way branch. Quite
popular these days.
>> .. a "hashing" technique ..
> .. anyplace I might look to find an example? ..
Looks for books on computer science, or algorithms. Here's a VERY crude
example…
< continued in next message >
>> a "hashing" technique
> .. an example or in-depth description?
Here's a brief and very sloppy example. Please try to find a better hashing
algorithm than the one I will suggest.
ASSUME: You expect ot have 200 records or so. Good; I'll has into a table of
512 bytes (notice the planned waste space?)
Before starting, I'll set all hash table entries to zero. Then I will go
through each key string of each record (call it Key$) and calculate:
Hash = 0
FOR J=1 TO LEN(Key$) : Hash = Hash * 7 + ASC(MID$(Key$,J,1))
Hash = Hash MOD 512 (however your Basic does a MOD remainder)
NEXT J
At this point, you have a value for variable Hash that is a muddied up
result of the original string. We need to put it into the hash table, at entry
number (Hash). But suppose that entry has already been used by some other
string that hashed to the same number? In that case, we just move along and
pop the index into the next free spot. (Heaven help you if you didn't allow
waste space). Call our has table HT(), and the number of our current record is
N, so:
WHILE HT(Hash)<>0
Hash = (Hash + 1) MOD 512
WEND
HT(Hash)=N
After we've done this calculation with all our records (and we could save the
hash values on the file or recalculate them each time, we can now look up an
input value in a similar way. Hash to key in exactly the same way as before.
Look up the hash table entry for that value; if it's zero, you have no match.
If it's not zero, compare with the actual record. If it matches, you're there.
If it doesn't match, repeat that Hash=(Hash+1)MOD512 bump and try again until
you get a zero or a match.
A little thought will show you that, in some cases, hashing can be very fast
indeed; your first hit finds the record. And that a near-full table (say, 500
out of 512) can be mighty slow. More, you need to consider that if you have a
few dozen guys called Smith, you might do well to has both first and last
names.
–Jim
It's scary thinking I might have missed this valuable exchange because John
called it "Help" (Hmm… *Might* be interesting) instead of "Searching" (Just
what I'm looking for). How about more descriptive subject lines!
Fortunately I did see it and Jim's responses are duly printed out for study.
By the way, I have long wondered: When ARexx does compound variables, is that
by hashing? (I seem to recall that is how SNOBOL handles arrays…)
Bart
Believe you're right. I have been told that the original ARexx did not store
its variables using a hashing technique, but the first upgrade switched over.
I don't know this from personal experience, but I heard that the speed
improvement was noticeable.
–Jim
A somewhat late afterthought to the search-methodology question:
I've just uploaded an ARexx program plus data file in library 7 of the
AmigaUser forum. It uses the built-in "hashing" system of ARexx to find
indexed stuff fast.
And/or: if you have access to a Commodore 64, I've uploaded the same data to
CBMAPP using Basic and a whole different search technique. This one is in
Basic, and uses an index of the first numeric of the requested area code to
point to a small search area. Might be good alternative code-reading.
–Jim