Browse Prior Art Database

Inexpensive Method to Order Long Active Lists

IP.com Disclosure Number: IPCOM000035363D
Original Publication Date: 1989-Jul-01
Included in the Prior Art Database: 2005-Jan-28

Publishing Venue

IBM

Related People

Authors:
Guenther, RL VanLeer, PW Zelek, MC [+details]

Abstract

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.