It is interesting that debits arise in Tarjan's analysis of path compression since path compression is essentially an application of memoization to the find function.
Amortization and Persistence Until this work, amortization and persistence were thought to be incompatible. Several researchers [DST94, Ram92] had noted that amortized data structures could not be made efficiently persistent using existing techniques for adding persistence to ephemeral data structures, such as [DSST89, Die89], for reasons similar to those cited in Section 5.6.
Ironically, these techniques produce persistent data structures with amortized bounds, but the underlying data structure must be worst-case. (These tech- niques have other limitations as well. Most notably, they cannot be applied to data structures supporting functions that combine two or more versions. Ex- amples of offending functions include list catenation and set union.)
The idea that lazy evaluation could reconcile amortization and persistence first appeared, in rudimentary form, in [Oka95c]. The theory and practice of this technique were further developed in [Oka95a, Oka96b].
f There is a clear analogy here to the spontaneous creation and mutual annihilation of particle- antiparticle pairs in physics. In fact, a better name for these debits might be "anticredits".
Amortization and Functional Data Structures In his thesis, Schoenmak- ers [Sch93] studies amortized data structures in a strict functional language, concentrating on formal derivations of amortized bounds using the traditional physicist's method. He avoids the problems of persistence by insisting that data structures only be used in a single-threaded fashion.
Queues and Binomial Heaps The queues in Section 6.3.2 and the lazy bi- nomial heaps in Section 6.4.1 first appeared in [Oka96b]. The analysis of lazy binomial heaps can also be applied to King's implementation of binomial heaps [Kin94].
Time-Analysis of Lazy Programs Several researchers have developed theo- retical frameworks for analyzing the time complexity of lazy programs [BH89, San90, San95, Wad88]. However, these frameworks are not yet mature enough to be useful in practice. One difficulty is that these frameworks are, in some ways, too general. In each of these systems, the cost of a program is calcu- lated with respect to some context, which is a description of how the result of the program will be used. However, this approach is often inappropriate for a methodology of program development in which data structures are designed as abstract data types whose behavior, including time complexity, is specified in isolation. In contrast, our analyses prove results that are independent of context (i.e., that hold regardless of how the data structures are used).
7
Eliminating Amortization
Most of the time, we do not care whether a data structure has amortized bounds or worst-case bounds; our primary criteria for choosing one data structure over another are overall efficiency and simplicity of implementation (and perhaps availability of source code). However, in some application areas, it is important to bound the running times of individual operations, rather than sequences of operations. In these situations, a worst-case data structure will often be preferable to an amortized data structure, even if the amortized data structure is simpler and faster overall. Raman [Ram92] identifies several such application areas, including
• Real-time systems: In real-time systems, predictability is more impor- tant than raw speed [Sta88]. If an expensive operation causes the system to miss a hard deadline, it does not matter how many cheap operations finished well ahead of schedule.
• Parallel systems: If one processor in a synchronous system executes an expensive operation while the other processors execute cheap operations, then the other processors may sit idle until the slow processor finishes.
• Interactive systems: Interactive systems are similar to real-time sys- tems — users often value consistency more than raw speed [But83]. For instance, users might prefer 100 1-second response times to 99 0.25- second response times and 1 25-second response time, even though the latter scenario is twice as fast.
Remark Raman also identified a fourth application area — persistent data structures. As discussed in the previous chapter, amortization was thought to be incompatible with persistence. But, of course, we now know this to be untrue. O
83
Does this mean that amortized data structures are of no interest to program- mers in these areas? Not at all. Since amortized data structures are often simpler than worst-case data structures, it is sometimes easier to design an amortized data structure, and then convert it to a worst-case data structure, than to design a worst-case data structure from scratch.
In this chapter, we describe scheduling — a technique for converting lazy amortized data structures to worst-case data structures by systematically forc- ing lazy components in such a way that no suspension ever takes very long to execute. Scheduling extends every object with an extra component, called a schedule, that regulates the order in which the lazy components of that object are forced.