我们有n文件 f<sub>1</sub>...f<sub>n</sub>我们需要存储在磁盘上。每个文件 f<sub>i</sub>是s<sub>i</sub> <= B字节长，其中一页磁盘存储 B字节。我们可以将每个文件完全存储在一个页面上，或者将其拆分为两个连续的页面。连续的文件必须存储在相同或连续的页面上。我们将按顺序访问文件并对每个文件执行计算。每次我们访问一个与前一个文件不完全在同一页上的新文件时，我们的开销为 T<sub>page</sub>。用于将页面读入主存。此外，如果文件 f<sub>i</sub>分为两页，我们的开销为 T<sub>split</sub> * s<sub>i</sub>用于计算期间的缓存未命中。我们希望找到一种有效的算法来将文件存储在内存中，从而最大限度地减少总开销时间。
如果该问题的算法及时运行，则该算法被认为是有效的 O(nB) .
我的方法:
这似乎是重新安排文件以尽量减少缓存未命中。但是，声明说连续的文件需要存储在相同或连续的页面中。这意味着我们无法更改顺序以最适合可用页面。但是，由于文件是按顺序读取的，因此在读取数据时我们可以“向前看”以查看我们已读取的当前页面是否包含下一个文件。维护文件起点和终点的索引可能会有所帮助，以便在读取文件时，我们可以检查它是否包含下一个文件。
有人可以为这个问题建议一个动态规划算法吗？
最佳答案
如果您按顺序排列文件，那么您需要为每个文件做出一个决定——是否新页面。
有一个权衡:开始一个新页面通常会比拆分产生更少的成本，但它会让您留下更少的页面，这可能会使 future 的决策成本更高。
动态规划解决方案是衡量这些决策的所有可能序列如何影响这种权衡。
设 MIN_COST(r,i) 是布局前 i 个文件的最小成本，同时在最后使用的页面中剩余 r 个字节。 MIN_COST(r,i) = infinity 如果没有办法布局前 i 个文件，剩下 r 个字节。
对于 r = B-s0，MIN_COST(r,1) = 0，否则无穷大
对于每个 i>1，您可以从 MIN_COST(r, i-1) 的值计算所有 MIN_COST(r,i)，方法是简单地从所有 r 中尝试 2 个可能的决定(新页面或不新页面)记住每个新余数的新最低成本。
最后，最小成本布局的成本是 MIN_COST(r,n) 中最低的。如果您记得产生每个成本的决策顺序，那么您可以从最小的成本中获得顺序并相应地布置您的文件。
该算法执行 N 步，每步最多执行 2B 次恒定时间测试，总运行时间为 O(NB)。
关于algorithm - 高效文件存储算法，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/27422914/