Lecture Note 02 EECS 4101/5101 Instructor: Andy Mirzaian
SELF-ADJUSTING LINEAR LISTS Analysis of the “Move to Front” Heuristic
The problem we shall study here (see [3]) is often called the dictionary problem: Maintain a set of items under an intermixed sequence of the following kinds of opera- tions:
access(x): insert(x): delete(x):
Locate item x in the set. Insert item x in the set. Delete item x from the set.
In discussing this problem, we shall use n to denote the maximum number of items ever in the set at one time and m to denote the total number of operations in the sequence of operations. We shall generally assume that the initial set is empty. A simple way to solve the dictionary problem is to represent the set by an unsorted list. To access an item, we scan the list from the front until locating the item. To insert an item, we scan the entire list to verify that the item is not already present and then insert it at the rear of the list. To delete an item, we scan the list from the front to find the item and then delete it. In addi- tion to performing access, insert, and delete operations, we may occasionally want to rearrange the list by exchanging pairs of consecutive items. This can speed up later oper- ations.
In this note we shall only consider algorithms that solve the dictionary problem in the manner described above. We define the cost of the various operations as follows: Accessing or deleting the ith item on the list costs i units of time. Inserting a new item costs l + 1 units of time, where l is the size of the list before the insertion. Immediately after an access or insertion of an item x, we allow x to be moved at no cost to any posi- tion closer to the front of the list; we call the exchanges used for this purpose free exchanges. Any other exchange , called paid exchange, costs one unit of time.
Our goal is to find a simple rule for updating the list (by performing exchanges) that will make the total cost of a sequence of operations as small as possible. Three rules have been extensively studied, under the rubric of self-organizing linear lists:
Move-to-Front (MF):
Transpose (T):
Frequency Count (FC):
After accessing or inserting an item, move it to the front of the list, without changing the relative order of the other items.
After accessing or inserting an item, exchange it with the immediately preceding item.
Maintain a frequency count for each item, initially zero. Increase the count of an item by 1 whenever it is inserted or accessed; reduce its count to zero when it is deleted. Maintain the list so that the items are in nonincreasing order by fre- quency count.
-2-
Example 1: We give an example for the Move-to-Front rule.
acd −−−−→ bacd −−−−→ cbad −−−−→ cbd.
insert(b) access(c) delete(a) The cost of this sequence is 4 + 3 + 3 =10 units of time.
The Static Dictionary Problem
The static dictionary problem corresponds to the case where the list initially con- tains n items and only access operations are performed on the list (no delete or insert operations). In other words, the set of items on the list is fixed. To analyze the static dic- tionary problem the above rules are often compared against the optimum static rule, called decreasing frequency (DF), which uses the fixed list with the items arranged in nonincreasing order by access frequency. Among algorithms that do no rearranging of the list, decreasing frequency minimizes the total access cost.
Note that the decreasing frequency rule assumes advance knowledge about the entire sequence of accesses. This kind of a problem is called off-line, that is the entire sequence of operations is known prior to any computation. (An on-line problem is one in which we have to complete the current operation before the next operation is known.)
Suppose the list contains the set of items { x1 , x2 ,…, xn }, and s is a sequence of m access operations. Let ki , 1 ≤ i ≤ n , be the number of accesses to item xi in sequence
n
s. Note that Σki=m. We may assume, without loss of generality, that
i=1
k1 ≥ k2 ≥ … ≥ kn . In the decreasing frequency rule (DF) we organize the list in nonin-
creasing order of access frequency, that is in the order x1 , x2 , … , xn and never change this arrangement. The total cost of processing the sequence s on the list under the decreasing frequency rule is
n CDF(s) = Σ i ⋅ ki
i=1
In this section we will show that the total cost under the Move-to-Front rule is at most twice that much even though the MF-rule has no advance knowledge about access fre- quencies.
Theorem 1: Let CMF(s) be the cost of processing sequence s of m access operations under the MF-rule starting with the initial list x1,x2,…,xn. Then CMF(s) ≤ 2CDF(s)−m.
Proof: Let t , 1 ≤ j ≤ k , be the cost of the jth access to item x under the move-to-front iji i
rule. We are going to derive an upper bound on
nki n nki CMF(s)−CDF(s) = ΣΣtij −Σi⋅ki = Σ(Σ(tij −i)).
i=1 j=1 i=1 i=1 j=1
Consider an arbitrary pair i , j . There are t − 1 items in front of x just prior to the jth
ij i
access to item xi. There can be at most i −1 items xh, h < i, in front of xi at that instant.
We conclude that if tij > i, then there must have been at least tij − i accesses to items xh ,
h > i, between the (j −1)th and the jth access to item x . (Why? Because each accessed i
-3-
item is moved to the front of the list in the MF-rule. Also note that we consider the 0th access to be the initial configuration.) Let us define
A = { x h > i and x is accessed between the ( j −1)th and jth access to x } . ijhh i
Then, from the above discussion we conclude that
Aij ≥tij −i
On the other hand, since the total number of accesses to items xh, h > i, in sequence s is
ki+1 +ki+2 +…+kn,weconclude
ki
ΣAij ≤ki+1+ki+2+…+kn. j=1
From the above two equations we conclude
ki
Σ(tij −i) ≤ ki+1 +…+kn j=1
for all i,1 ≤ i ≤ n , and therefore
CMF(s)−CDF(s) ≤ Σ(ki+1 +…+kn )
i=1
n
= Σ(i −1)⋅ ki
i=1
nn =Σiki −Σki i=1 i=1
= CDF(s) − m.
There is another way of interpreting the proof of Theorem 1 which leads to an
account to be used shortly. We argued above that if tij > i then there were at least tij − i
accesses … . This suggests to charge the “excess cost” of tij − i of the jth access to xi to
the accesses to items x , h > i , between the (j −1)th and the jth access to x , i.e. to hi
charge the excess cost to those xh , h > i, which are in front of xi when item xi is accessed for the jth time. In other words, whenever we access xh then we charge an extra h−1 time units to this access and use these time units to pay for the excess cost of accesses to items xi , i < h . In this way, the amortized cost of accessing xh is 2h −1. We can generalize this idea in the amortized analysis as follows.
Let s be an arbitrary sequence of m access, insert, and delete operations starting with the empty list and let A be an arbitrary algorithm. Let C−A(s) be the cost of algorithm A on sequence s not counting paid exchanges, let XA(s) be the number of paid exchanges, and let FA(s) be the number of free exchanges. Note that XMF(s) = XT(s) = XFC(s) = 0
n
This completes the proof of the theorem.
Amortized Analysis of the General Case
-4-
and that FA(s) for any algorithm A is at most C−A(s) − m and the total cost of algorithm A, including paid exchanges, is C A(s) = C−A(s) + X A(s).
Theorem 2: For any algorithm A and any sequence s of m access, insert, and delete operations starting with the empty list
CMF(s) ≤ 2C−A(s)+XA(s)−FA(s)−m ≤ 2CA(s)−m.
Proof: To obtain the theorem, we use as the potential function the number of inversions in MF’s list with respect to A’s list. For any two lists containing the same items, an inver- sion in one list with respect to the other is an unordered pair of items x , y , such that x occurs anywhere before y in one list and anywhere after y in the other. With this poten- tial function we shall show that the amortized time for MF to access item i costs at most 2i−1, the amortized time for MF to insert an item into a list of size i is at most 2(i + 1) − 1, and the amortized time for MF to delete item i costs at most i, where we iden- tify an item by its position in A’s list. Furthermore, the amortized time charged to MF when A does an exchange is −1 if the exchange is free and at most 1 if the exchange is paid.
The initial configuration has zero potential since the initial lists are empty, and the final configuration has a non-negative potential. Thus the actual cost to MF of a sequence of operations is bounded from above by the sum of the operations’ amortized times. The sum of the amortized times is in turn bounded by the right-hand side of the inequality we wish to prove. (An access or an insert has amortized time 2cA −1, where cA is the actual cost of the operation to A; the amortized time of a deletion is ≤ cA ≤ 2cA − 1. The −1’s, one per operation, sum to −m.)
It remains for us to bound the amortized times of the operations. Consider an access by A to item i (i.e. the ith item in A’s list). Thus, A’s actual access cost to item i is cA = i. Let k be the position of item i in MF’s list and let p be the number of items that precede item i in both lists. Thus, the number of items that precede i in MF’s list but succede i in A’s list is k −1 − p. (See Figure 1.)
1
2
.. .
i
i+1
A’s List
MF’s List
i
p
k- 1- p
i
k
Figure 1. Arrangement of A’s and MF’s lists in the proof of Theorem 2.
TheamortizedcostofaccesstoitemibyMFiscˆMF =cMF +∆Φ. WeseethatcMF =k. What is ∆Φ? Moving i to the front of MF’s list creates p inversions and destroys
i=1
(b) EMF=1+2⋅Σpipj
1≤i
denote the expected (i.e. average) cost of a single access operation by algorithm A. Then we have:
Theorem 3: The following hold:
n
(a) EDF =Σi⋅pi
† For an access/insert operation, the accessed/inserted item appears in front of the MF’s list by now.
expected value of this sum plus one (for item xi itself), i.e.,
n
li = 1 + E [ Σ Yij ] .
j=1 j≠i
j≠i
-6-
Proof:
Part (a): This follows directly from the definition of expectation. Part (b): We can write
n
EMF =Σli⋅pi, i=1
where li is the expected position of item xi on the list. But what is the value of li? Let us define the following 0/1 random variables:
1 if x j appears before xi in the list Yij =
0 otherwise
Now we see that the number of items preceding xi in MF’s list is Σ Yij. Thus, li is the
Using linearity of expectation we can move the expectation inside the sum and get
nn
E [ Σ Yij ] = Σ E [ Yij ] .
j=1 j=1 j≠i j≠i
Now the question is what is E [ Yij ]? Let pij = Prob[Yij = 1] be the probability that item xj is in front of xi. Then, we have
Thus,
li =1+Σpij.
n j=1
E[Yij]=1⋅pij +0⋅(1−pij)=pij.
Now, what is pij? It is a conditional probability. Let us define the following two proba- bilistic events. Let A denote the event corresponding to the last access to either of items xi or xj, and let B be the event corresponding to that last event being an access to item x j . Here we use the argument that currently x j appears before xi if and only if the latest access to either of xi or x j was an access to x j . Thus, pij is the conditional probability
pij = Prob[B A]. Using the formula for conditional probabilities, we have
n j=1
j≠i
Prob[A∩B] pj =
pij = Prob[B A]=
Putting the above formulas together, we get the result:
nn
EMF =Σpi⋅[1+Σpij]
i=1 j=1 j≠i
pi + pj
.
Prob[A]
-7-
Σn nnpp
= pi+ΣΣi j
i=1 i=1 j=1 pi + pj j≠i
=1+2⋅ Σ pipj . 1≤i
n−2 n(n −1)
n12 EMF= + − .
2 3 3(3n − 4) References
[1] D.E. Knuth, ‘‘The Art of Computer Programming’’, vol III, 1973, pages 398-399.
[2] K. Mehlhorn, ‘‘Data Structures and algorithms’’, vol I, 1984, pages 256-263.
(This includes both the amortized and average case analysis of the move-to-front heuristic.)
[3] D.D. Sleator and R.E. Tarjan, ‘‘Amortized efficiency of list update and paging rules’’, Communications of ACM, 28(2), 1985, pp. 202-208.
(This is the original paper that does the amortized analysis of the move-to-front heuristic.)