Article View: comp.lang.misc
Article #5232Re: Poor Algorithms
From: gvlv2!kleonard Ken Leonard
Date: Tue, 08 Mar 1988 13:44
Date: Tue, 08 Mar 1988 13:44
25 lines
1586 bytes
1586 bytes
In article <404@tub.UUCP> net@tub.UUCP (Oliver Laumann) writes: * ... * I have read in the (highly recommendable, by the way) paper "Hints for * Computer System Design" by Butler W. Lampson of Xerox Palo Alto. * ... * A major commercial word processing system used a "FindNamedField" * ... * 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 In the best tradition of K&R. Regardz, Engineering--The Art of Science Ken Leonard --- --- This represents neither my employer's opinion nor my own--It's just something I overheard in a low-class bar down by the docks.
Technical Details
Message-ID:
<5713@burdvax.PRC.Unisys.COM>Path:
arc1-ca.pugleaf.net!utzoo!utgpu!water!watmath!clyde!att-cb!att-ih!pacbell!ames!ll-xn!mit-eddie!bbn!rochester!udel!burdvax!kleonardReferences:
<3821@ihlpf.ATT.COM> <2791@enea.se> <404@tub.UUCP>Show Full Headers
Complete Article Headers
Path: arc1-ca.pugleaf.net!utzoo!utgpu!water!watmath!clyde!att-cb!att-ih!pacbell!ames!ll-xn!mit-eddie!bbn!rochester!udel!burdvax!kleonard From: kleonard@PRC.Unisys.COM (gvlv2!kleonard@prc.unisys.com, Ken Leonard) Newsgroups: comp.lang.misc Subject: Re: Poor Algorithms Message-ID: <5713@burdvax.PRC.Unisys.COM> Date: 8 Mar 88 13:44:31 GMT References: <3821@ihlpf.ATT.COM> <2791@enea.se> <404@tub.UUCP> Organization: Unisys Great Valley Laboratory, Paoli, Pa. Lines: 25