Save Subtree List
Original Publication Date: 1992-Nov-01
Included in the Prior Art Database: 2005-Mar-25
Publishing Venue
IBM
Related People
Brown, RW: AUTHOR [+3]
Abstract
A programming design is proposed that could enhance the performance of certain algorithms. Algorithms that must parse vast amounts of data looking for a subset of the data may obtain performance improvements using this design.
Save Subtree List
A programming
design is proposed that could enhance the
performance of certain algorithms.
Algorithms that must parse vast
amounts of data looking for a subset of the data may obtain
performance improvements using this design.
The idea is to identify the data for which
the algorithm is
parsing prior to parsing. This data is
stored, redundantly, in a
format that is suitable for the algorithm.
When the algorithm needs
the data, the smaller stored set of data is parsed rather than the
larger data.
Two main
factors that affect the performance improvements are:
1. The total amount of data being
parsed by the old algorithm.
2. The amount of data being looked for.
The
performance gain is proportional to the total amount of
data being parsed and inversely proportional to the amount of data
being looked for. A trade-off to
consider is the amount of data
being looked for. Since this data must
be redundantly stored, more
storage is necessary. Depending on the
situation, this could negate,
partially or totally, the performance gains.
This
technique may be employed when it is desired to
graphically display a hierarchy of subroutine calls within a program.
To do this, the statements in a program which include subroutine
calls must be parsed to identify the appropriate statements. A
program may contain hundreds or thousands of statements. Within all
these statements, only a dozen or two stateme...