Computer Science & Perl Programming

Chapter 20. Memoization

Mark Jason Dominus

Caching is a useful general technique that sometimes makes programs run faster. It does this by exchanging space for time: caching tries to save previously computed results in an attempt to reuse them later rather than recomputing them.

Caching is useful in all kinds of situations, including almost any kind of searching (cache the results of the search so that we can skip it next time), HTML generation (cache the results of the generation process so that you never have to regenerate the page), and numeric computation (cache the results of the computation). As a specific example, consider a function for preparing graphic images to be printed on an industrial offset printer. Four-color printing processes, commonly used in magazines and color printers, use four colors of ink: cyan, magenta, yellow, and black, collectively referred to as CMYK. Graphics files, however, usually record colors by indicating the desired intensities of red, green, and blue light (RGB). The RGB format has to be converted to CMYK values prior to printing.

Each pixel needs to have its color converted; this typically requires a fairly expensive calculation. But in many graphics formats, such as GIF, there are few colors relative to the number of pixels. A naïve approach would compute the CMYK values for each color repeatedly.

To speed up the caculation of CMYK values, we save each CMYK set in a data structure, called a cache. Later, if we use the function to compute the ...