Schlemiel the Painter's algorithm: Difference between revisions

Revision as of 05:54, 11 May 2008

Revision as of 05:59, 11 May 2008

Line 64:

== The Solution ==

Yep, Schlemiel would be well advised to "take your paint with you"... So how can we apply that principle to ''strcat''? Easy, we just have to remember the end of the string, to avoid thethat costexpensive of finding the end of the stringseek every time we append to it. First lets write another version of ''strcat'' called ''szcat'' which returns the-new-end-of-the-destination-string (nbnote: the mnemonic ''sz'' denotes a null terminated string).

<source lang="c">

Line 83:

</source>

Our new ''szcat'' function is basically the same, it just returns the-new-end-of-the-destination-string instead of the-start-of-the-destination-string... So what? Well so the '''next time''' we call ''szcat'' we can pass it the-end-of-the-destination-string, so ''szcat'' doesn't have to waste time looping through the destination string in order to findfinding it. Pretty clever huh!

NoewNow lets write anothera test harness to examine ''szcat'''s (hopefully improved) performance characteristics.

<source lang="c">

Line 101:

</source>

The totalestimated cost of testPerformanceOfStrcat is:

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

* We've eliminated the overhead of finding the-end-of-the-destination-string in the ''while'' condition...., so we're down to one operation per loop = 174,762 clock ticks.

* We've eliminated the overhead of finding the-end-of-the-destination-string in ''strcat(endOfBuffer, word)'', which leaves is with just the cost of copying the string, which is 6 cycles per loop = 174,762 * 6 = 1,048,572

* about 1.2 billionmillion (with an m) cycles at 2 billion cycles per second (my CPU speed is 2.01GHz) is about a tenth of a second.

* MuchThat's bettermore like it!

== Conclusion ==