TAOCP 2.4 Exercise 11
Algorithm B spends much of its time locating all occurrences of a given name.
Section 2.4: Multilinked Structures
Exercise 11. [**] [23] What additional links or changes in the strategy of the algorithms of the text could make Algorithm B or Algorithm C faster?
Verified: yes
Solve time: 1m18s
Algorithm B spends much of its time locating all occurrences of a given name. A direct improvement is to maintain, for each Data Table entry, an additional link to the first Symbol Table node having that name, together with links chaining all Symbol Table nodes of equal name. Then step B6 need not search through unrelated entries; it can proceed directly to the relevant class of nodes.
Algorithm C spends much of its time determining whether two names are equal and finding all nodes that must be merged. A faster strategy is to represent each equivalence class by a distinguished representative and to let every node contain a link to that representative. When two classes are equated, the smaller class can be attached to the larger, updating representative links accordingly. Equality tests such as those in step C3 then reduce to testing whether two nodes have the same representative, instead of comparing names or traversing long chains. Such additional links reduce repeated searches and therefore decrease the running time of both algorithms.