`
love19820823
  • 浏览: 936988 次
文章分类
社区版块
存档分类
最新评论

《编程之美》——分离变量法,磁带访问优化方案(个人见解)

 
阅读更多

问题大概是:
已知:磁带的各个 文件F1、F2……Fn.文件的大小分别是L1、L2……Ln, 访问的频率分别是:f1、f2……fn。
求:怎么安排文件使得 磁带的平均访问长度 最短 (注:每次从头开始,而且是磁带的顺序访问)

个人感觉书上没有说清楚,就是弄的很含糊。其实总体思想就是 :分离变量法。把问题的其他因素先假设已知固定,看其他变量的影响。
1、单独从文件大小来看:
如果仅仅从文件大小看,那么访问F1的长度是L1,访问F2的长度是(L1+L2)……访问Fn的长度是(L1+L2+……+Ln),平均访问时间是:(L1)+(L1+L2)+……+(L1+L2+…+Ln)/n ={n*L1+(n-1)*L2+…+1*Ln}/n
要使得上述式子最小,也就是要L1尽量小(因为乘了n),然后L2次小(因为乘了n-1) …… 那么文件短的话在前面,也就是说L1、L2……Ln是递增序列,

2、单独从访问频率来看:
如果单独从访问频率看,文件大小相同都为L,那么平均访问为 (f1*L+f2*2L+f3*3L+…fn*nL)/n,其中f1+f2+…fn=1.
要使其最小,那么就是要*L的f1尽量大(因为乘的长度小),也就是按访问频率 从大到小 排列。

3、兼而顾之
从L看是 呈负的线性比例(L小在前), 从 访问频率看 呈现正的线性比例(f大在前)。那么就是关于f/L的多项式比例,f/L越大那么放在前面。 也就是L/f的反比,越小的放前面。

后言:
如果两者都是呈正相关A 和B,那么 就是关于 A*B的比例。

分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics