algorithm - 算法 - 给定一系列内存访问，给出缓存未命中的最小数量

Question

给定的输入是：缓存大小、s内存条目数n和一系列内存访问。

给出可能的最小缓存未命中数。

例子：

s = 3，n = 4 1 2 3 1 4 1 2 3 min_miss = 4

我被困了一整天。提前致谢！

您可以决定缓存采取的任何行为。例如，即使条目被访问，您也不必接受。它不需要是规则的。您不需要遵循固定的“规则”来缓存。

Answer 1

尝试遵循http://en.wikipedia.org/wiki/Page_replacement_algorithm#The_theoretically_optimal_page_replacement_algorithm - 当您需要换掉一些东西时，换掉在尽可能长的时间内不会再次使用的项目。由于您提前获得了整个内存访问序列，这对您来说是可行的。这显然是局部最优的，至少直到缓存变满后的第一次缓存未命中，因为到那时，其他所有策略都至少有一次缓存未命中。对我来说，这是全局最优的并不明显 - 搜索我在http://www.stanford.edu/~bvr/psfiles/paging.pdf找到了一个证明，声称它的最优性的其他证明确实存在但甚至是更长。