Yellow Pages Search

Question

I've written code in Free Pascal based on a contest problem (The contest insists that I have to write with Pascal). It works like charm, but I think it still need some improvements, from memory usage to runtime.

Input Format

First line is n (Number of people in the Yellow Pages) and q (Number of people to search) {1 <= n <= 10000} and {1 <= q <= 10000}

Next n lines are Yellow Pages entries, each line is the name and the phone number, space delimited. The name is uppercase letters with maximum length of 15, while the length of the phone number is exactly 7 digits.

Next q lines are the people to search, also in uppercase letters with maximum length 15.

Output Format

Output is q lines, where each line is the phone number of the people to search

Input Sample

10 5
AARON 8468431
BEN 1573457
GREGORY 1765743
JACK 3746843
JILL 1357891
MICHAEL 1375638
MONET 1357562
SHEILA 1378651
TERRY 8756345
YIN 1781945
GREGORY
YIN
AARON
MONET
JACK

Output Sample

1765743
1781945
8468431
1357562
3746843

My Code

program YellowPages;

type string7 = String[7];

var
  namearray : Array of shortstring;
  numberarray, searcharray : Array of string7;
  input, name, search : shortstring;
  number : string7;
  n, q, iter1, iter2 : word;

procedure SplitInput(input : shortstring; var name : shortstring; var number : string7);
var 
  iter_proc, hitspace : byte;
begin
  hitspace := pos(' ', input);
  name := '';
  number := '';
  for iter_proc := 1 to length(input) do
  begin
    if iter_proc < hitspace then name := name + input[iter_proc];
    if iter_proc > hitspace then number := number + input[iter_proc];
  end;
end;

begin
  readln(n, q);
  setlength(namearray, n);
  setlength(numberarray, n);
  setlength(searcharray, q);
  for iter1 := 0 to (n - 1) do
  begin
    readln(input);
    SplitInput(input, name, number);
    namearray[iter1] := name;
    numberarray[iter1] := numberarray;
  end;
  for iter1 := 0 to (q - 1) do
  begin
    readln(search);
    for iter2 := 0 to (n - 1) do
    begin
      if namearray[iter2] = search then break;
    end;
    searcharray[iter1] := numberarray[iter2];
  end;
  for iter1 := 0 to (q - 1) do
  begin
    writeln(searcharray[iter1]);
  end;
end.

Answer 1

The first thing I would do is switch from using parallel arrays to using a single array of records. Create a record that holds both the name and the phone number of each person in the phonebook, like this:

Type
    Contact = Record 
        name : shortstring;
        number : String7;
        end;

Once you've done that, you should sort the array based on each contact's name. The quicksort algorithm is fairly easy to implement and is usually quite fast in most cases.

Once you have the array sorted, instead of searching through the entire phonebook from the beginning, you can use a binary search to find each record you want and get the phone number from it. A binary search should never require more than log2(n) comparisons (where n is the size of the array you're searching). Whereas your search requires on average n/2 comparisons. So for 100 entries, you'd never perform more than ~8 comparisons with a binary search, whereas you'd usually do around 50 using a linear search.

I haven't used FreePascal or any other Pascal compiler in a long time. It's possible that they have some built-in sorting and searching procedures that you could use. But it's not hard to implement the ones mentioned above.

Also, in SplitInput() you're manually copying the data from one string to another. Usually there's a library with a procedure for copying a string or a part of a string. These will usually be faster than writing your own. (For example, in C you could use memcpy() or strncpy(). I'm not sure if there's an equivalent in Pascal.)