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> -- http://mail.python.org/mailman/listinfo/python-list
