Schlemiel the Painter's algorithm: Difference between revisions

Revision as of 05:38, 11 May 2008

Revision as of 05:40, 11 May 2008

Line 13:

== The Problem ==

Repeated calls to [[ANSI_C|ANSI-C]]'s [[strcat]] function is a classic example of Schlemiel's algorithm.

An implementation of strcat might look something like this:

<source lang="c">

char *strcat(char *dest, const char *src) {

Line 35 ⟶ 37:

The ''strcat'' function looks innocious enough, and it is, as long as you don't call it '''repeatedly''' to build a large string.

So lets examine an example of how __not__'''not''' to use strcat:

<source lang="c">

// builds a 1Meg string of "word, word, word, ....";

Line 49 ⟶ 51:

</source>

The totalestimated cost of testPerformanceOfStrcat is:

* NOTE: I am ignoring "ancillary expenses" like the cost of making a function call.

* The number of times through the loop is int(1024*1024/6) = 174,762 // strlen("word, ")==6