算法导论27.3 Exercises 答案
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\)次未命中。
接下来考虑离线最优算法的行为。由于每个时期的第一个请求必定是一个新请求，此时离线最优算法会触发\(1\)次未命中。那么，离线最优算法在每个时期中都至少会触发\(1\)次未命中。
因此，确定性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)\)，原结论成立。