高效的文件存储算法

Question

我们有n个文件f1...fn需要存储在磁盘上。每个文件fi的大小为si<=B字节，其中一个磁盘页面可以存储B字节。我们可以将每个文件完整地存储在一页中，或者在两个连续页面之间拆分它。连续的文件必须存储在同一页面或连续页面上。我们将按顺序访问文件并对每个文件执行计算。每次访问与前一个文件不完全位于同一页上的新文件时，我们都需要花费Tpage的开销将该页面读入主存储器。此外，如果文件fi在两个页面之间拆分，则我们在计算期间会有Tsplit * si的缓存未命中开销。我们希望找到一种有效的算法来存储文件在内存中，以最小化总超额时间。

这个问题的算法被认为是有效的，如果运行时间为O(nB)。

我的方法是重新安排文件以减少缓存未命中。然而，该语句说连续的文件需要存储在相同或连续的页面上。这意味着我们不能改变顺序以最适合可用页面。但是，由于文件是按顺序读取的，因此在读取数据时我们可以“向前查看”以查看当前已读取的页面是否包含下一个文件。维护文件起始点和结束点的索引可能有助于在读取文件时检查它是否包含下一个文件。

有人能否为此问题提供动态规划算法？

- Fahad Zulfiqar

---

总页面越少，缓存未命中就越少。那么尽可能填满每个页面的缺点是什么？无论如何，您都需要从文件到页面/偏移量的映射，不是吗？我不明白DP对您有什么作用。 - Scott Hunter

@ScottHunter：我也在想，最优的方法一定是尽可能地填满页面，使用未分割的文件，因为当决定如何处理第一个不适合当前页面的文件时，无论是否拆分，都会产生Tpage，而不拆分可以节省Tsplit * si。但是：现在选择拆分可能会减少所需的总页面数，这意味着它可能是一个净胜利。 - j_random_hacker

Answer 1

如果您按顺序排列文件，那么对于每个文件，您需要做出一个决定——新建页面还是不新建。

这里有一个权衡：开始新页面通常会产生比分割更小的成本，但它会留下更少的页面剩余，这可能会使未来的决策成本更高。

动态规划的解决方案是测量所有可能的这些决策序列如何影响这种权衡。

让MIN_COST(r,i)表示布置前i个文件时，在最后一页中剩余r字节的情况下的最小成本。如果没有办法布置前i个文件并留下r字节，则MIN_COST(r,i)=无穷大。

当r=B-s0时，MIN_COST(r,1)=0，否则为无穷大。

对于每个i>1，您可以通过从所有r尝试出2个可能的决策（新页面或不新页面）并记住每个新余数的新最小成本来计算所有MIN_COST(r,i)的值，从而从MIN_COST(r,i-1)的值计算出所有MIN_COST(r,i)。

最后，最小成本布局的成本是MIN_COST(r,n)中最低的。如果您记得产生每个成本的决策序列，那么您可以从最小成本获得序列并相应地布置文件。

该算法执行N步操作，在每一步中最多进行2B个常数时间测试，总运行时间为O(NB)。

- Matt Timmermans