Path: utzoo!mnetor!uunet!mcvax!unido!tub!net
From: net@tub.UUCP (Oliver Laumann)
Newsgroups: comp.lang.misc
Subject: Re: Poor Algorithms
Message-ID: <404@tub.UUCP>
Date: 7 Mar 88 10:34:04 GMT
References: <3821@ihlpf.ATT.COM> <2791@enea.se>
Reply-To: net@tub.UUCP (Oliver Laumann)
Organization: Technical University of Berlin, Germany
Lines: 31

All the anecdotes about poor algorithms remind me of an amusing tale
I have read in the (highly recommendable, by the way) paper "Hints for
Computer System Design" by Butler W. Lampson of Xerox Palo Alto.

In a paragraph titled "Get it right" he mentions that neither
abstraction nor simplicity can be a substitute for getting an algorithm
or a computer system right; in fact, abstraction, if overdone or used
unwisely, can lead to severe difficulties.  He illustrates this by the
following anecdote:

A major commercial word processing system used a "FindNamedField"
procedure which, for a given "name", searched the document being edited
for a "field" of the form "{name: contents}" embedded in the text.
The "name" was passed to the procedure as an argument.  The remarkable
point is that this procedure ran in time O(n^2), where n is the length
of the document!

This result was achieved by first writing a procedure "FindIthField"
which finds the i-th field in the document.  This, of course, takes
time O(n).  The procedure "FindNamedField(name)" was then implemented
in the following "natural" way [quoted directly from the article]:

   FOR i = 0 to NumberOfFields DO
      FindIthField; IF its name is "name" THEN EXIT
   ENDLOOP


--
Regards,
    Oliver Laumann, Technical University of Berlin, Germany.
    ...!pyramid!tub!net   or   net@TUB.BITNET