Abstract
In this article we study the amortized efficiency of the “move-to-front” and similar rules for dynamically maintaining a linear list. Under the assumption that accessing the ith element from the front of the list takes θ(i) time, we show that move-to-front is within a constant factor of optimum among a wide class of list maintenance rules. Other natural heuristics, such as the transpose and frequency count rules, do not share this property. We generalize our results to show that move-to-front is within a constant factor of optimum as long as the access cost is a convex function. We also study paging, a setting in which the access cost is not convex. The paging rule corresponding to move-to-front is the “least recently used” (LRU) replacement rule. We analyze the amortized complexity of LRU, showing that its efficiency differs from that of the off-line paging rule (Belady's MIN algorithm) by a factor that depends on the size of fast memory. No on-line paging algorithm has better amortized performance.
Original language | English (US) |
---|---|
Pages (from-to) | 202-208 |
Number of pages | 7 |
Journal | Communications of the ACM |
Volume | 28 |
Issue number | 2 |
DOIs | |
State | Published - Feb 1 1985 |
Externally published | Yes |
All Science Journal Classification (ASJC) codes
- General Computer Science