Schlemiel the Painter's algorithm: Difference between revisions

Revision as of 16:46, 22 September 2008

Revision as of 23:31, 20 December 2008

Line 23:

# <code>strcat( buffer, "George" ); </code>/* ... and the string "George" is appended to ''that'' */

# <code>strcat( buffer, "Ringo" ); &nbsp;</code>/* ... and the string "Ringo" is appended to ''that'' */

By the end of the first invocation of <code>strcat()</code> the length of <code>buffer</code> will be known but not preserved upon return to the point just after step 1 and just before step 2. Subsequent calls to <code>strcat()</code> have to compute that length again before they concatenating another name to the <code>buffer</code>.

As such, and analogous to Schmiel's not carrying the paint-bucket with him, all the subsequent <code>strcat()</code>s have to again "walk" the length of the string to determine where the second string should be copied. As more data is added to it, the string in <code>buffer</code> also gets longer with each call to <code>strcat()</code>, and with increasing length, the determination of that length takes longer, which means that subsequent calls are increasingly slower. Just as "Schlemiel's" path to his bucket keeps getting longer.