#Help
11 messages in this thread
Hello all,
Could anyone give me a suggestion or two in regards to a small program I am
writing? The question is as follows;
Given a large list of words (alphabetically sorted) what would be the
best/fastest way to locate one particular word?
Obviously a comparison loop running from the beginning of the list to the end
of the list would not be the way to go. I've thought of using an index type of
approach but I feel there must be a better method.
Any suggestion/comments would be greatly appreciated.
-John
Hi John,
The search method I use is known as "halving" (has a technical name but can't
for the life of me remember what its called) and is documented in a number of
programming texts. The idea is simple, but quite effective. It is an old
method, however, so there are probably faster algorithms out there.
The procedure is as follows. Check the word half way down the list. If it is
the required word, exit. If its bigger than the required word, check the word
half way between the last checked word and the start. If its smaller, check
the word halfway between it and the end. You just keep repeating this
procedure of halving the remaining list until you arrive at the required word.
Here is an example BASIC algorithm:
pnt=numw/2
high=numw+1
low=1
for lp=1tonumw
if upper$(word$(pnt))=upper$(kword$)
goto found
else if upper$(word$(pnt))<upper$(kword$)
low=pnt
pnt=pnt+((high-pnt)/2)
else
high=pnt
pnt=(pnt-low)/2
endif
next lp
goto nofound
where word$() is the array of words, numw is the number of words in the array,
and kword$ is the word your are looking for. This assumes the list is sorted
in ascending order. If not, reverse the IF statements.
Using this algorithm to search a list of 31 words, it located the required word
after an average of only 6 loops. The largest number of loops performed was
14, while the lowest was 1.
Hope this helps,
Terry Cooper,
Sailing the fjords on AutoPilot.
>The search method I use is known as "halving" (has a technical name but can't
>for the life of me remember what its called)
Binary search.
> and is documented in a number of
>programming texts. The idea is simple, but quite effective. It is an old
>method, however, so there are probably faster algorithms out there.
It is like looking up a word in the dictionary.
Which algorithm is best depends upon many things and goals.
This one still has its place. There are of course tangents and
optimizations possible too.
Hi Greg,
Yep, thats the one! It sure does still have its place – at least 6 of the
worlds airlines use it.
Ciao,
Terry Cooper,
Sailing the fjords on Autopilot.
>Yep, thats the one! It sure does still have its place – at least 6 of the
>worlds airlines use it.
Everybody uses it. It's just one of those fundamental
"data structures/algorithms".
>>Everybody uses it. It's just one of those fundamental "data
structures/algorithms".<<
Exactly, I used it 15 years ago in my first commercial program and I still use
it. At the time I didn't even know it was called that way.
Bart Van Bockstaele at 100574.2352@compuserve.com
… On AutoPilot and Amiga all the way from Belgium NOT from Mars!…
Hi Greg,
<<Everybody uses it. It's just one of those fundamental "data
structures/algorithms".>>
Well yeah, but not everybody's running real-time systems!
Ciao,
Terry Cooper,
Sailing the fjords on Autopilot.
>>Everybody uses it. It's just one of those fundamental
>>"data structures/algorithms".
>
>Well yeah, but not everybody's running real-time systems!
That in and of itself would not necessarily stop me from using it.
What other "look-up" would you choose? (I can think of many things,
but would depend upon many things to decide.)
Hi Greg,
Yep, your right! I sat down and thought about it for a while and couldn't come
up with any other solution. The database is large and very dynamic – 3 days
from now it will be 100% different – conditions which hamper other algorithms.
Ciao,
Terry Cooper,
Sailing the fjords on Autopilot.
>The database is large and very dynamic – 3 days
>from now it will be 100% different – conditions which hamper other algorithms.
No doubt. Just recall that the algorithm works on a data structure,
and hence, alternate structures may be conducive to something else though
in this case changing the algorithm might not be.
"alphabetically sorted" may be something of a red herring.. but..
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.
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.
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.
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.
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.
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.
–Jim