算法导论27.3 Exercises 答案

发表于 2023-07-25 更新于 2025-12-23 分类于算法导论阅读次数：本文字数： 3k 阅读时长 ≈ 3 分钟

27.3-1

假设给出的序列为$1,2,1,5,4,4,1,2,4,2,3,4,5,2,2,1,2,2$，那么每个时期的过程如下表给出：

$\begin{array}{|c|c|l|c|c|}\hline
\text{epoch}&\text{request}&\text{cache}&\text{miss?(\texttt{Y/N})}&\text{miss count}\\hline
1&1&1&\texttt{Y}&3\
&2&2,1&\texttt{Y}\
&1&1,2&\texttt{N}\
&5&5,1,2&\texttt{Y}\\hline
2&4&4,5,1&\texttt{Y}&2\
&4&4,5,1&\texttt{N}\
&1&1,4,5&\texttt{N}\
&2&2,1,4&\texttt{Y}\
&4&4,2,1&\texttt{N}\
&2&2,4,1&\texttt{N}\\hline
3&3&3,2,4&\texttt{Y}&2\
&4&4,3,2&\texttt{N}\
&5&5,4,3&\texttt{Y}\\hline
4&2&2,5,4&\texttt{Y}&2\
&2&2,5,4&\texttt{N}\
&1&1,2,5&\texttt{Y}\
&2&2,1,5&\texttt{N}\
&2&2,1,5&\texttt{N}\\hline
\end{array}$

27.3-2

证明过程和定理27.2相似。我们先展示LFU算法的竞争比例具有下界$\Omega(n/k)$。

考虑构造如下长度为$n=(k+1)m$的请求序列，其中$m>1$：

$1,\dots,1,2,3,\dots,k,k+1,2,3,\dots,k,k+1\dots,2,3,\dots,k,k+1$

即先请求$m$次$1$，接下来对$2,3,\dots,k,k+1$这个序列按顺序请求$m$次。

考虑这个序列的请求未命中次数。一开始缓存是空的，因此请求$m$次$1$时，只发生$1$次未命中。对于接下来的$k-1$次从$2$到$k+1$的请求，从$2$到$k$依次请求都会发生一次未命中。当请求$k+1$时，缓存空间已满，由于从$2$到$k$至少都访问了$1$次（而$1$访问了$m$次），并且$2$在其中滞留最久，因此$2$将会被驱逐，对$k+1$加入缓存。接下来对$2$进行请求，缓存中从$3$到$k+1$至少都访问了$1$次（而$1$访问了$m$次），并且$3$在其中滞留最久，因此$3$会被驱逐，$2$将会被加入，接下来对$3$进行请求……可见，对$1$进行$m$次请求后，接下来的$km$次请求都会导致未命中，因此这个请求序列将会导致$km+1=n-m+1$次未命中。

对于一个最优离线算法，当$k+1$被请求时，应该将$1$驱逐掉。那么整个请求过程中，每个不同的块只会导致$1$次未命中，那么最优离线算法只会发生$k+1$次未命中。

因此，LFU算法的竞争比例的下限为$\dfrac{n-m+1}{k+1}=\Omega(n/k)$。

类似的，对于竞争比例的上界，对于任何规模为$n$的请求序列，任何缓存算法都会导致最多$n$次缓存缺失。由于请求不同块的种类数至少为$n$，因此所有缓存算法，包括离线最优缓存算法都会导致至少$k$次的缓存缺失，因此LFU算法的竞争比例上限为$O(n/k)$。

最终，LFU算法具有竞争比例$\Theta(n/k)$，也因此它是无界的。

27.3-3

同证明定理27.3的过程相同，按照相同的方式，为整个请求序列划分成一个个时期。

接下来考虑FIFO算法的行为。在每个时期中，对于任意一种特定块$b$，它仅仅在这个时期的第一次出现才会可能发生未命中（如果发生未命中，那么就会被加入到缓存中，并且在接下来的$k-1$次未命中发生都不会被驱逐）。而如果在这个时期中$b$再次出现，那么必定会命中，因为FIFO算法只保留最近使用的$k$个块，在此之前，$b$已经加载到缓存中，因此中间不会有超过$k-1$个不同的请求。最终在每个时期中，FIFO算法只会发生最多$k$次未命中。

接下来考虑离线最优算法的行为。由于每个时期的第一个请求必定是一个新请求，此时离线最优算法会触发$1$次未命中。那么，离线最优算法在每个时期中都至少会触发$1$次未命中。

因此，FIFO算法的竞争比例为$k/1=O(k)$，原结论成立。

27.3-4

同证明定理27.3的和题目27.3-3过程相同，按照相同的方式，为整个请求序列划分成一个个时期。

接下来考虑确定性MARKING算法的行为。在每个时期中，对于任意一种特定块$b$，它仅仅在这个时期的第一次出现才会可能发生未命中。此后，如果$b$再在同一时期被进行一次请求，那么一定会发生命中，并且已经被标记成了$1$。在每个时期的开始时，所有块的标记都已经是$1$，并且需要将它们的所有标记置$0$，并且使用确定性算法选择一个块进行驱逐。每个时期只有$k$种不同的块，最多只会导致$k$次未命中。

因此，确定性MARKING算法的竞争比例为$k/1=O(k)$，原结论成立。

27.3-5

定理27.4给出的是$l=0$前瞻的情况。

对于$1$前瞻的情况，考虑有这么一个对手$A$，他能够按照这个$1$前瞻的确定性算法$F_1$输出一个长串的请求块。

$F_1$只能够预测$A$的下$1$步操作，$A$也知道$F$能够预测到自己下$1$步的操作，但是$F_1$无法预测到$A$的下$2$步操作，但是$A$可以根据$F_1$算法的过程，提前构造好自己下$2$步的操作，使得$F$必定发生未命中。也就是说，$A$每产生相邻的两个请求必定会导致$F_1$发生一次未命中。因此，如果$0$前瞻算法$F_0$的竞争比例为$\Omega(k)$，那么$F_1$的竞争比例为$\Omega(k/2)=\Omega(k)$，原结论成立。

对于$l$前瞻的情况$(l>1)$，考虑某个在$1$前瞻算法$F_1$中达到竞争比例下界的请求序列$S$，并将请求这个请求序列中的每个块都向$l$前瞻算法$F_l$都请求$l$次，那么在$F_l$的视角中，这个请求序列相当于是$1$前瞻下的视角（因为最多只能预测到$1$个块）。那么$F_l$的未命中次数至少是$F_1$对请求序列$S$的未命中次数。但是在最优算法下，未命中次数是相同的。因此$F_l$的竞争比例为$\Omega(k/l)=\Omega(k)$，原结论成立。