Comparing lists

[Fredrik Lundh]

Christian Stapfer wrote:

> As to the value of complexity theory for creativity
> in programming (even though you seem to believe that
> a theoretical bent of mind can only serve to stifle
> creativity), the story of the discovery of an efficient
> string searching algorithm by D.E.Knuth provides an
> interesting case in point. Knuth based himself on
> seemingly quite "uncreatively theoretical work" (from
> *your* point of view) that gave a *better* value for
> the computuational complexity of string searching
> than any of the then known algorithms could provide.

are you talking about KMP?  I'm not sure that's really a good example of
how useful "theoretical work" really is in practice:

- Morris had already implemented the algorithm (in 1968) when Knuth "dis-
  covered" it (1971 or later), so the "then known" part of your argument is
  obviously bogus.  "then known by theoretical computer scientists" might
  be correct, though.

- (iirc, Knuth's first version wasn't practical to use; this was fixed by Pratt)

- (and iirc, Boyer-Moore had already been invented when Knuth published the
  first paper on KMP (in 1977))

- for use cases where the setup overhead is irrelevant, Boyer-Moore is almost
  always faster than KMP.  for many such cases, BM is a lot faster.

- for use cases such as Python's "find" method where the setup overhead cannot
  be ignored, a brute-force search is almost always faster than KMP.

- for use cases such as Python's "find" method, a hybrid approach is almost
  always faster than a brute-force search.

in other words, the "better" computational complexity of KMP has turned out
to be mostly useless, in practice.

</F>