Python DAA Optimal Storage on Tapes
OPTIMAL STORAGE ON TAPES USING GREEDY METHOD
DESCRIPTION
Optimal Storage on Tapes is one of the applications in the Greedy Method, The objective of this algorithm is to find the Optimal retrieval time for accessing programs that are stored on tape.
Greedy Method:
This algorithm works in steps. In each step, it selects the best available options until all options are finished.
EXPLANATION
- There are 'n' programs that are to be stored on a computer tape of length (L).
- Associated with each program (i) is a length (l).
- Let the programs are stored in the order (I = i1, i2, i3, ....)
- If all programs are retrieved equally often then the expected or MEan Retrieval Time (MRT) is,
Example:
Let n=3, (l1, l2, l3) = (5, 10, 3), therefore we can keep the programs in 3! (6 ways) possible orders.
From the above graph, we can see the min(MRT) = 9.66. So, the best possible order of programs is (Program3, Program1, Program2)
By this, we can assume that storing programs in increasing order of their lengths can give the solution for Mean Retrieval Time.
ALGORITHM
This ordering can be carried out in O(n log n) time using an efficient sorting algorithm.
CODE
# Optimal Storage on Tapes using Greedy Method
def optimalstorage(n,new_dict):
sorted_dict = {}
temp = []
totalsum = t_sum = 0
print("Sorted Lengths for the programs ....")
s_v = sorted(new_dict.values())
for i in s_v:
for k in new_dict.keys():
if new_dict[k] == i:
sorted_dict[k] = new_dict[k]
break
print(sorted_dict)
for i in sorted_dict:
#print(sorted_dict[i])
v = sorted_dict[i]
t_sum += v
temp.append(t_sum)
totalsum = sum(temp)
print("Minimum value of sum of lengths",totalsum)
print("Mean Retrieval time is",totalsum/n)
n = int(input("Enter Number of Programs :"))
new_dict = {}
prgm = list()
length = list()
for i in range(n):
p = int(input("Enter the Program number :"))
l = int(input("Enter the Program length :"))
prgm.append(p)
length.append(l)
new_dict = dict( zip(prgm,length))
print("Entered Lengths for the programs ....")
print(new_dict)
optimalstorage(n,new_dict)
OUTPUT
Taking 3 programs (p1,p2,p3) with lengths = (5,10,3) respectively.
Taking 4 programs (p1,p2,p3,p4) with lengths = (12,5,8,4) respectively.
Comments