最优磁盘文件存储问题

1. 问题描述

  设磁盘上有个文件，每个文件占用磁盘上的1个磁道。这个文件的检索概率分别为,且。磁头从当前磁道移到被检索信息磁道所需的时间可用这2个磁道之间的径向距离来衡量。如果文件存放在第道上,，则检索这n的文件的期望时间是。式中，是第道与第道之间的径向距离。

  磁盘文件的最优存储问题要求确定这n个文件在磁盘上的存储位置，是期望检索时间达到最小。试设计一个解此问题的算法，并分析算法的正确性与计算复杂性。

• 算法设计：对于给定的文件检索概率，计算磁盘文件最优存储方案。

1.1. 算法思想

  利用贪心算法来进行设计，很容易由存储的期望时间想到应该把概率大的先进行安排且彼此靠的最近,然后再依次安排概率低的。具体的方案如下：先将n个文件按照检索概率从大到小排序，即，然后将检索概率最大的文件放在中间磁道，次大的和第三大的放在最大的两边，第四大的放在次大的右侧，第五大的放在第三大的左侧，依此类推，如题中所给案例，即得到磁盘文件的最优存储位置。

1.2. 核心代码

double greedy(vector<double> data,int n) {
    sort(data.begin(), data.end(), compare);  //降序排序，得到[f1,f2,f3,f4,f5,...,fn]

    vector<double> result(n);

    int mid = (n - 1) / 2;
    result[mid] = data[0];  //按照...,f5,f3,f1,f2,f4,...的方式对磁盘文件进行排列
    for (int i = mid - 1; i >= 0; i--)
        result[i] = data[2 * (mid - i)];
    for (int i = mid + 1; i < n; i++)
        result[i] = data[2 * (i - mid) - 1];
    for (int i = 0; i < n; i++) cout <<  "  " << result[i] << endl;

    double sum = 0;
    double cost = 0;
    for (int i = 0; i < n; i++) {  //计算最小期望检索时间
        sum += result[i];
        for (int j = i + 1; j < n; j++)
            cost += result[i] * result[j] * (j - i);
    }
    return cost / sum / sum;
}

1.3. 结论与算法分析

TIM截图20190513190000.png