Program optimization using indexed and recursive data structures
Yanhong A. Liu and Scott D. Stoller
This paper describes a systematic method for optimizing recursive
functions using both indexed and recursive data structures. The method is
based on two critical ideas: first, determining a minimal input increment
operation so as to compute a function on repeatedly incremented input;
second, determining appropriate values to maintain in appropriate data
structures, based on what values are needed in computation on an
incremented input and how these values can be established and
accessed. Once these two are determined, the method extends the original
program to return the appropriate values in appropriate data structures,
derives an incremental version of the extended program, and forms an
optimized program that repeatedly calls the incremental program. The
method can derive all dynamic programming algorithms found in standard
algorithm textbooks. There are many previous methods for deriving
efficient algorithms, but none is as simple, general, and systematic as
ours.
BibTeX
gzip'd
PostScript
PostScript
Scott Stoller's Home Page