PRESENTATION ON ●OPTIMAL STORAGE ON TAPES ●OPTIMAL MERGE PATTERNS
PRESENTED TO ■ DR. VINAY PATHAK RESPENTED BYSUNIL KUMAR III rd C.S.E. S.R.No. – 108/07
PROBLEM
Tapes
Optimal Storage on
ALL SIX PERMUTATIONS
1
2
3
1
3
2
2
3
1
2
1
3
3
1
2
3
2
1
FOR
n=3
MRT ( Mean Retrival Time ) v Let there are n programs namely i1,i2,i3,i4.......................in on tape then time tj required to retrive program ij
tj ∝ ∑
li
k
v If all program are retrived equally and every time head point to the front , then expected MRT is given by
MRT =(1/n)∑
tj
∑ ∑ li
v Minimizing the MRT to minimizing D (isI )equivalent =
1≤ j ≤ n 1≤ k ≤ j
k
Example Let n = 3 and (l1,l2,l3) = (5,10,3) Ordering I 1 ,2 , 3 5 + 5 + 1 ,3 , 2 5 + 5 + 2 ,1 , 3 10 + 10 2 ,3 , 1 10 + 10 3 ,1 , 2 3 + 3 + 3 ,2 , 1 3 + 3 +
D(I) 10 + 5 + 10 + 3 = 3 + 5 + 3 + 10 = + 5 + 10 + 5 + 3= + 3 + 10 + 3 + 5= 5 + 3 + 5 + 10 = 10 + 3 + 10 + 5 =
38 31 43 41 29 34
The Greedy Solution Make tape empty vfor i := 1 to n do
Øgrab the next shortest file Øput it next on tape
vThe algorithm takes the best short term choice without checking to see weather it is the best long term decision.
Example Le t n = 5 , a n d l1 = 5 , l2= 7 , l3= 10 , l4 = 2 0 , l5 = 3 0 TA P E -
SORTED ORDER IS 5,7,10,20,30
Insert 5 5
Insert 7
5
7
Insert
10 5
7
10
Insert 20
5
7
10
20
Insert 30 5
7
10
20
30
ALGO FOR MORE THAN ONE TAPE 1. Algorithm Store(n,m) 2. //n is the no of programs and m the no of tapes 3. {
j:=1;//Next tape to store on for i:=1 to n do { write(“append program”,i,”to permutation for tape”,j); 8. j:=(j+1)mod m; 9. } 10. } 4. 5. 6. 7.
Example vWe want to store files of lengths (in MB) {12 34 56 73 24 11 34 56 78 91 34 45} on three tapes. How should we store them on the three tapes so that the mean retrieval time is minimized? vSOLUTION: STORE FILES BY NONDECREASING LENGTH vFirst sort the files in increasing order of length. For this we can use heapsort, meregesort or quicksort algorithms.
S o rte d E le 4 m e n ts a re 11 12 24 34 34 34 45 56 56 73 78 91
N o w d istrib u te th e file s: First e le m e n t 1 1
In se rtin g 1 1 Tape 1 Tape 2 Tape 3
11
In se rtin g 1 2 Tape 1 Tape 2 Tape 3
11 12
In se rtin g 2 4 Tape 1 Tape 2 Tape 3
11 12 24
In se rtin g 3 4 Tape Tape 12 Tape 3
11 12 24
34
In se rtin g 3 4 Tape Tape 12 Tape 3
11 12 24
34 34
In se rtin g 4 5 Tape Tape 12 Tape 3
11 12 24
34 34 34
45
In se rtin g 5 6
Tape Tape 12 Tape 3
11 12 24
34 34 34
45 56
In se rtin g 5 6 Tape Tape 12 Tape 3
11 12 24
34 34 34
45 56 56
In se rtin g 7 3 Tape Tape 12 Tape 3
11 12 24
34 34 34
45 56 56
73
In se rtin g 7 8 Tape Tape 12 Tape 3
11 12 24
34 34 34
45 56 56
73 78
In se rtin g 9 1 Tape Tape 12 Tape 3
11 12 24
34 34 34
45 56 56
73 78 91
TIME COMPLEXITY
The time is consumed only in shorting becoz in writting and finding the tape on which we have to write the time consumed is constant.So time consumed is equal to time taken by any sorting algo
T(n)=O(n ln n)+θ(1) =O(n ln n)
Optimal Merge Patterns P R O B LE M
Example. Suppose there are 3 sorted lists L1, L2, and L3, of sizes 30, 20, and 10, respectively, which need to be merged into a combined sorted list, but we can merge only two at a time. We intend to find an optimal merge pattern which minimizes the total number of comparisons. For example, we can merge L1 and L2, which uses 30 + 20 = 50 comparisons resulting in a list of size 50. We can then merge this list with list L3, using another 50 + 10 = 60 comparisons, so the total number of comparisons is 50 + 60 = 110. Alternatively, we can merge lists L2 and L3, using 20 + 10 = 30 comparisons, the resulting list (size 30) can then be merged with list L1, for another 30 + 30 = 60 comparisons. So the total number of comparisons is 30 + 60 = 90. It doesn’t take long to see that this latter
Binary Merge Trees : W e ca n d e p ict th e m e rg e p a tte rn s u sin g a binary tree, built from the leaf nodes (the initial lists) towards the root in which each merge of two nodes creates a parent node whose size is the sum of the sizes of the two children. For example, the two previous merge patterns are depicted in the following two figures: Cost = 30*2 + 20*2 + 10*1 = 110
60
10
50 30
20
Cost = 30*1 + 20*2 + 10*2 = 90
60 30
30 20
10
Merge L2 and L3, then with Merge L1 and L2, then L1 with L3 merge cost = sum of all weighted external path lengths
ALGORITH M
treenode = record{ treenode* lchild; treenode*rchild; integer weight;}; 1. Algorithm Tree(n) 2. // list is a global list of n single node 3. //binary trees as described above 4. { 5. for i:= 1 to n-1 do 6. { 7. pt:= new treenode;//Get a new treevnode 8. (pt->lchild):=Least(list); 9. (pt->rchild):=Least(list); 10. (pt->wieght):= ((pt->lchild)->wieght)+((pt->rchild)-> wieght); 11. Insert (list,pt);//Merge 2 trees with smallest length 12. } 13. return Least(list) //tree left in list is merged tree 14.}
E xa m p le o f th e o p tim a lm e rg e tre e a lg o rith m : 2
3
5
7
Initially, 5 leaf nodes with sizes
9
5 2
3
5
7
Iteration 1: merge 2 and 3 into 5
9
10
Iteration 2: merge 5 and 5 into 10
5
5 2
16
3
7
9
Iteration 3: merge 7 and 9 (chosen among 7, 9, and 10) into 16
26 16
10 5
5 2
3
Iteration 4: merge 10 and 16 into 26
7
9
Cost = 2*3 + 3*3 + 5*2 + 7*2 + 9*2 = 57.
TIME COMPLEXITY § The main for loop executed n-1 times § If list is kept in nondecreasing order of the weights of roots then Least (list) take only O(1)time & Insert(list,pt) will take O(n) time .
Hence the total time taken will be
O(n2)
Greedy Solution
vThe solution is greedy becoz at each step we are merging smallest files without caring of final result v vThe cost is directly proportional tothe sum of productof depth of external leaves to their weights
∑1≤i≤n diqi path length
called as weighted external
Proof of optimality of the tree algorithm We use induction on n 1 to show that the tree algo is optimalin that it gives the minimum total weighted external path lengths (among all possible ways to merge the given leaf nodes into a binary tree). Ø (Basis) When n= 1. There is no internal nodes so tree is optimal. Ø (Induction Hypothesis) Suppose the merge tree is optimal when there are k leaf nodes, for some k 1
Ø (Induction) Consider (k+ 1) leaf nodes. Call them a1, a2, …, and ak+1 . We may assume nodes a1, a2 are of the smallest values, which are merged in the first step of the merge algorithm into node b. We call the merge tree T, the part excluding a1, a2 T’ (see figure). Suppose an optimal binary merge tree is S. We make two observations.
. ( 1 ) Ifnode x of S is a deepest internal node , we may sw a p its tw o ch ild re n w ith n o d e s a 1 , a 2 in S w ith o u t in cre a sin g th e to ta lw e ig h te d exte rn a lp a th le n g th s. T h u s, w e m a y a ssu m e tre e S has a subtree S ’ with le a f n o d e s x , a 3 , …, and a k +1 . ( 2 ) The tree S ’ m u st b e a n o p tim a ltre e fo r k nodes x , a 3 , …, and a k +1 B y in d u ctio n h yp o th e sis, tre e S ’ has a total weighted exte rn a l p a th le n g th s e q u a lto th a t o f tre e T ’. T h e re fo re , th e to ta l w e ig h te d exte rn a lp a th le n g th s o f T equals to that of tree S , proving the optimality of T . T b
a1
T’ a2
S
S’
x
a1
a2
THANK !
YOU