现在的位置: 首页 > 综合 > 正文

编程之美4.5 磁带文件存放优化

2019年01月04日 ⁄ 综合 ⁄ 共 495字 ⁄ 字号 评论关闭

对于如何得到的文件平均访问长度我就不多说了,课本中推导得到:

前两种情况,若文件的被访问概率相等或者文件长度一样,比较容易理解,也不多说

对于第三种情况,课本中只是根据一个例子来进行猜测,而且课本中也出现了一点错误;对于两种情况,排列顺序为AB或BA,第二种文件的P/L应该是

0.4/10=0.04以及0.6/6=0.1

这里给出一种数学分析方法

对于一种最佳存储顺序,不能存在i使得,P[i]/L[i] > p[i+1]/L[i+1]

证明(反证法):假设存在i使得上述条件成立,交换第i和第i+1个文件,则

1) 在新序列中访问原第i个文件,需要多访问原第i+1个文件,从而增加访问长度P[i]*L[i+1]

2) 在新序列中访问原第i+1个文件,不需访问原第i个文件,从而减少访问长度P[i+1]*L[i]

从而增加访问长度P[i]*L[i+1]-P[i+1]*L[i],又P[i]/L[i] > p[i+1]/L[i+1]成立,则P[i]*L[i+1]-P[i+1]*L[i]<0,从而存在更好的存储顺序,与最佳存储顺序矛盾

故原命题成立,从而得到课本中的结论,P[i]/L[i]的值从大到小排列即为最佳存储顺序

抱歉!评论已关闭.