缓存标记算法分析

Question

我有一些问题来理解在Kleinberg Tardos "Algoritms设计“一书中对标记算法的分析。

在关于随机化的章节中，特别是在关于随机缓存(13.8)的章节中，本书介绍了一类特殊的算法，称为标记算法，可用于管理系统的缓存。这种类型的算法以内存项的请求序列$\sigma$作为输入，并使用不同的阶段处理这些请求。每个阶段的定义如下：

Each memory item can be either marked or unmarked 
At the beginning of the phase, all items are unmarked 
On a request to item s: 
    Mark s 
    If s is in the cache, then evict nothing
    Else s is not in the cache:
       If all items currently in the cache are marked then 
           Declare the phase over 
           Processing of s is deferred to start of next phase
       Else evict an unmarked item from the cache 
       Endif
    Endif

现在在分析算法的过程中，书中说：

为了使分析更容易讨论，我们将在开始和结束时用一些额外的请求“填充”序列σ.我们设想一个“阶段0”发生在first阶段之前，在这个阶段中，缓存中最初的所有项都被请求一次。..。我们还设想，final阶段r以尾声结束，其中当前处于最优算法缓存中的每一项都会以roundrobin方式被请求两次。

其中，最优算法是假设性算法，对于给定的序列σ，该算法会产生最小的失分数。

我很难理解为什么这本书会做出这样的假设。特别是同一节以下部分的书指出：

在每个阶段，σ都包含对完全k个不同项的访问。接下来的阶段从访问另一个(k+1)第一项开始。 标记算法在每个阶段最多会产生k个缺失，因为在所有r阶段中最多只会出现kr缺失。

现在考虑的序列可能是(至少对于我所未发现的)填充序列，但是为什么要使用填充序列而不是正常的序列σ呢？

如果我使用相同的技术来证明它也适用于非填充序列，那么有一些特殊的情况需要考虑。

Answer 1

但是为什么要使用填充序列而不是正常的σ序列？

我会说这只是数学把戏。您需要更多或更少的具体时间来实现初始缓存。现在，填充序列清楚地指出，它在0阶段完成任务，而不太关心在此之前发生了什么。否则，您需要一遍又一遍地思考什么时候和为什么某些特定的项需要缓存。

出于类似的原因，你可能需要尾声。老实说，我不知道为什么，但你应该看到尾声在算法校对中的引用。

基本上，您可以计算裸序列和填充序列。从你引用的部分打样，我看到作者找到了一些准确的访问/错过的次数。使用填充序列计算“错过”比较容易，因为它处于可控状态。用足够长的顺序填充感情是可以忽略的，但没有它呢？嗯，没有它，你有相当不稳定的范围的“想念”，是无法精确计算的。如果没有精确的计算，我们就无法证明算法的性能。