算法导论15.4 Exercises 答案

15.4-1

FURTHEST-IN-FUTURE(C, k, B, i, n)
  // T是一个字典，将一个数映射成它在B的所有下标的列表。
  let T be a new HASH-MAP
  // Q是一个支持以O(lg n)的时间复杂度进行增加，删除，查询，修改的有序数据结构，以key作为排序关键字。
  let Q be a new ORDERED-SET
  //如果T不存在关键字B[j]，INSERT方法将会为其创建并且初始化出一个对应的空列表。
  for j = i to n
    INSERT(T[B[j]], j)
  for each b in C
    INSERT(T[b], +∞)
    let p be a new node
    p.key = T[b][1]
    p.ID = b
    INSERT(Q, p)
  for j = i to n
    if SEARCH(S, B[i])
      print b_i: a cache hit
    else
      print b_i: a cache miss
      if Q.size == k
        // MAX用于获取Q中的最大值。
        p = MAX(Q)
        DELETE(Q, p)
        print p.ID is evicted
      let p be a new node
      p.ID = B[i]
      p.key is the smallest number x in T[B[i]] such that x > i or +∞ if T[B[i]] isn't existed
      INSERT(Q, p)  

15.4-2

假设请求序列为\(b=[1,2,3,4,5,1,2,3]\)，缓存快\(C\)的大小\(k=3\)，那么按照LRU算法和FF算法的定义，可以列出下表：

\(\begin{array}{|c|c|c|c|c|} \hline b&C_\text{LRU}&\text{LRU cache miss occured}& C_\text{FF} & \text{FF cache miss occured}\\ \hline 1&[1]&\texttt{YES}&[1]&\texttt{YES}\\ \hline 2&[2,1]&\texttt{YES}&[1,2]&\texttt{YES}\\ \hline 3&[3,2,1]&\texttt{YES}&[1,2,3]&\texttt{YES}\\ \hline 4&[4,3,2]&\texttt{YES}&[1,2,4]&\texttt{YES}\\ \hline 5&[5,4,3]&\texttt{YES}&[1,2,5]&\texttt{YES}\\ \hline 1&[1,5,4]&\texttt{YES}&[1,2,5]&\texttt{NO}\\ \hline 2&[2,1,5]&\texttt{YES}&[1,2,5]&\texttt{NO}\\ \hline 3&[3,2,1]&\texttt{YES}&[1,2,3]&\texttt{YES}\\ \hline \end{array}\)

可以发现，LRU算法在整个过程中总是在发生缓存缺失，而FF算法命中了\(2\)次。因此这个例子说明LRU算法并非是离线缓存算法中最优的。

15.4-3

\(x\)是\(b_i\)被请求时\(C\)中被替换的块，\(y\)是\(b_j\)被请求时被替换的块。如果换成这种方式，那么在请求\(b_i\)和\(b_j\)替换掉的块是同一个块，这种证明忽略了最优策略下，分别请求\(b_i\)和\(b_j\)所替换的块不一定相同的事实。

15.4-4

假设当前处在第\(i\)个访问序列，在原问题（最多只能有一个块进入缓存）的最优策略\(S\)下，此时的缓存配置为\(C_{S,i}\)（如果缓存未充满数据，为方便证明，假设\(C\)未充满的一部分都是永远不会被用到的过期数据）。按照这个最优策略\(S\)，在从\(i\)到\(j(j>i)\)的过程中，替换掉的总是属于\(C_{S,i}\)的旧数据（假设一共发生了\(m\)次，也就是说，从\(i\)到\(j\)的这\(m\)次缓存缺失，最优策略采取的都是从\(C_{S,i}\)中选择块进行替换，在这个过程中，新替换进来的块都不会被替换掉。那么假设替换进来的\(m\)个块为\(I\)，被替换的\(m\)个块为\(D\)），那么在新问题中（可以多个块同时进入缓存）的最优解\(S'\)，访问\(b_i\)时，这单次请求就可以直接从\(C_{S',i}\)（注意\(C_{S,i}=C_{S',i}\)）中属于\(D\)的\(m\)个块，替换成属于\(I\)的\(m\)个块。只要\(m\ge 1\)，这种预先加载多个块的效率不差于只加载一个块的效率。