首页 > 技术文章 > 编程之美 4.5磁带文件存放优化

Linkabox 2013-10-09 00:41 原文

磁带的特性:线性存储、价格低廉、海量的存储空间

问题:设现在有n份文件长度为L[0]、L[1]、L[2]….L[n-1],访问概率为P[0]、P[1]、P[2]…P[n-1]

1.访问概率相等的情况下,如何安排存储顺序最好?

何为最好其实就是访问文件的平均长度最小,平均长度可以通过下式求得:

clip_image002

p相等的情况下=p*{n*L[0]+(n - 1)*L[1]+…+L[n-1]}

可以看出想让E(L)最小,只要把短的尽量往前放就可以了。

所以p相等时,按照文件长度由短到长存储最佳。

2.长度一样的情况下,如何安排呢?

通过上面的公式,可知概率越高放在前的,可以使E(L)越短,按访问概率从大到小排列文件最好。

3.长度与访问概率都不相同的情况下,又怎么安排呢?

举例观察:A、B文件长度分别为10、6,访问概率为0.4、0.6

B前A后,E(L)=0.6*6+0.4*(6+10)=10。(P/L分别为A:0.6/6=0.1,B:0.4/16=0.025)

A前B后,E(L)=0.4*10+0.6*(6+10)=13.6。(P/L分别为A:0.4/10=0.04,B:0.6/16=0.0375)

可以看出大概规律,就是P[i]/L[i]的值由大到小排列最佳。

推荐阅读