Finding A Word Faster

Introduction

BEACON knows 55 words; Zork I knows 697. A straight search down a table compares the typed word with every entry until it finds it, and a word near the end of a long table costs a comparison with every word before it. If the table is in alphabetical order there is a far quicker way, and Zork's dictionary, read off its disc, is in exactly that order.

The Vocabulary On The Disc

VOCAB.TXT holds 121 words, one to a line, in alphabetical order: the kind of vocabulary a game of BEACON's size might grow to. The program reads it into an array with S21's text-file reading:

while not Eof(F) do
begin
  Count := Count + 1;
  Readln(F, Vocab[Count]);
end;

The Straight Search

Start at the first word and go on until you find it or run out: Straight. Finding ABOUT, the first word, takes one comparison. Finding YELL, the last, takes 121.

The Binary Search

In an ordered list, look at the middle word first. If it is the one you want, you are done. If it comes before the word you want, the word must be in the second half, so throw the first half away; if after, throw the second half away. Then look at the middle of what is left, and so on:

Mid := (Lo + Hi) div 2;
if Vocab[Mid] = W then
  Found := Mid
else if Vocab[Mid] < W then
  Lo := Mid + 1
else
  Hi := Mid - 1;

Lo and Hi are the ends of the part still to search. Each comparison halves it: 121, 60, 30, 15, 7, 3, 1. Any word in the list is found in at most seven comparisons, and a word that is not there is known to be missing just as quickly.

< on strings compares them character by character, by code, exactly the order of VOCAB.TXT. That is the catch: the table must be in order, and in the same order < uses. All capitals, sorted alphabetically, is.

How Much Faster

The program looks up YELL, the worst case for the straight search, 300 times each way:

For ABOUT, the straight search wins easily, since it finds it at once. On average, over the whole table, a straight search compares about half of it: 60 or so against seven.

The Code

program Faster;
const
  Max = 150;
type
  Str10 = string[10];
var
  Vocab: array[1..Max] of Str10;
  Count, K, N: Integer;
  F: Text;

function Straight(W: Str10): Integer;
var
  I, Found: Integer;
begin
  Found := 0;
  I := 1;
  while (Found = 0) and (I <= Count) do
  begin
    if Vocab[I] = W then
      Found := I;
    I := I + 1;
  end;
  Straight := Found;
end;

function Binary(W: Str10): Integer;
var
  Lo, Hi, Mid, Found: Integer;
begin
  Found := 0;
  Lo := 1;
  Hi := Count;
  while (Found = 0) and (Lo <= Hi) do
  begin
    Mid := (Lo + Hi) div 2;
    if Vocab[Mid] = W then
      Found := Mid
    else if Vocab[Mid] < W then
      Lo := Mid + 1
    else
      Hi := Mid - 1;
  end;
  Binary := Found;
end;

begin
  Assign(F, 'VOCAB.TXT');
  Reset(F);
  Count := 0;
  while not Eof(F) do
  begin
    Count := Count + 1;
    Readln(F, Vocab[Count]);
  end;
  Close(F);
  Writeln(Count, ' words');
  for K := 1 to 300 do
    N := Straight('YELL');
  Writeln('Straight: ', N);
  for K := 1 to 300 do
    N := Binary('YELL');
  Writeln('Binary: ', N);
end.

Starting from

A new work file FASTER, on the primer's disc (which has VOCAB.TXT).

What you should see

121 words
Straight: 121
Binary: 121

with about twelve seconds before Straight: and two before Binary:.

Change One Thing

• Change Straight('YELL') to Straight('ABOUT'). How long does the straight search take now, and what does it print?
• Change Binary('YELL') to Binary('yell'). What does it print, and why?
• In Binary, change Vocab[Mid] < W to Vocab[Mid] > W. What happens?

Exercises

9.1 Count the comparisons each search makes for YELL, with a global counter, and print the two counts.

9.2 A binary search on a table that is out of order fails without saying so. Write a program that checks VOCAB.TXT is in order, printing any word that is not after the one before it, and how many there were.

9.3 Turn the program into a word finder: read words typed at the keyboard until an empty line, and say for each whether it is in the vocabulary, and where.

Worked solutions are in Appendix II.

When It Goes Wrong

Summary

A straight search compares the word with every entry before it: 121 comparisons for the last of 121 words. A binary search of an ordered table halves what is left each time: seven at most. For 300 look-ups of the last word, about twelve seconds against two. The price is keeping the table in order. BEACON's table is in order, and Zork's dictionary is too.

Next

S10, Understanding The Sentence: putting words together into a command the game can act on.