了解OPT算法
好的，我正在尝试理解OPT算法，然后它会让我很容易编码。 我不能跟随幻灯片，它没有任何意义。 有人可以一步一步地告诉我如何做到这一点吗？
这看起来与LRU算法相同。 我们用计数器保留第二个arrays吗？
您显然必须事先知道将要使用哪些页面以及使用的顺序; 这是您的示例中的列表1, 2, 3, ..., 4, 5 。 当您必须替换页面时，您选择包含将在所有页面中最后使用的页面的框架。
在此示例中，您可以访问第1,2,3,4,1和2页而不会出现任何页面错误（因为所有页面当前都已交换）。
您的下一页访问（第5页）不在任何框架中，因此您必须选择一个框架才能将其放入。 根据即将到来的页面匹配（1,2,3,4），将最后访问第4页（第4帧），因此您将第5页交换到第4帧（如图所示）。
访问下一页，1,2和3没有任何错误。
现在访问了第4页，但它之前已被换出，因此您有页面错误。 您的即将到来的访问列表仅显示第5页，因此可以换出1,2和3中的任何一个。 选择1，大概是因为它是第一个。
最优算法只是一种算法，导致理论上最少的高速缓存未命中。
换句话说， 在你有了如何使用缓存之后，才能知道最优。 这意味着您无法提前编写最佳算法; 因为，您不知道如何实际使用缓存。
优化算法作为实际算法的基线非常有用。 每个非平凡的缓存问题最终都会缓存缺失。 知道特定运行的“绝对最小”未命中数可以为比较两个缓存算法提供基线。
例如，如果您必须错过缓存四次，那么与错过缓存七次的算法相比，错过缓存六次的算法看起来相当不错。 如果你必须错过1000次缓存，那么错过缓存1006次的算法和错过缓存1007次的算法几乎是等效的。
根据缓存的使用模式，某些算法比其他算法更频繁地访问缓存。 一个例子是LRU，它将从缓存中删除很少使用的项目：如果您倾向于在一段小时间内对相同项目进行多次访问，那么这是很好的。 另一方面，如果您需要多次访问每个项目，但是一旦按顺序（如在循环中），则LRU可能具有可怕的性能（~100％缓存未命中），因为每次访问仅从缓存中踢出一个项目。 巧合的是，MRU（新项目取代最近使用的）缓存在这些条件下的性能优于LRU，因为至少缓存会对前几个项目执行一次。