Inexpensive Method to Order Long Active Lists
Original Publication Date: 1989-Jul-01
Included in the Prior Art Database: 2005-Jan-28
Prior art involving long active lists is simply to manage them as FIFO or LIFO lists (push down stacks) for CPU efficiency and seek to minimize the ill effects of the lists being out of order. This article describes an inexpensive method to order long active lists. Assumptions: 1. That S is a set of elements with some desirable ordering attribute. 2. That the usage of the elements is independent of the ordering attribute. 3. That the elements of S are used on a demand basis. 4. That U denotes that proper subset of S which is presently in use. 5. That I denotes that proper subset of S which is not in use. 6. That the exchange rate of elements between U and I may be high (e.g., number of exchanges per minute greater than the number of elements in I). 7. That the number of elements in I may be large, e.g.