2015-07-11

b439. 快取置換機制

1. Problem
1. 1.1. 背景
  1. 1.1.1. 方案一
  2. 1.1.2. 方案二
2. 1.2. 問題描述
2. Sample Input
3. Sample Output
4. Solution

Problem

背景

編寫程式不僅僅是在數學分析上達到高效率，儘管數學分析的複雜度不是最好，理解電腦運作模式也能有效地讓程式變快。例如資料結構 Unrolled linked list (常翻譯成塊狀鏈表) 便是利用此一優勢，讓速度顯著地提升，之所以能追上不少常數大的平衡樹操作運用的技巧就是快取效能改善。

講一個更簡單的例子，宣告整數陣列的兩個方案：

方案一

1	const int LARGE_SIZE = 1<<30; int A[LARGE_SIZE], B[LARGE_SIZE];

方案二

1	const int LARGE_SIZE = 1<<30; struct DATA { int A, B; } E[LARGE_SIZE];

演算法的複雜度倘若一樣，若在 A, B 相當高頻率的替換，則快取操作必須不斷地將內容置換，若 A, B 在算法中是獨立運算，則方案一的寫法會來得更好，反之取用方案二會比較好。最常見的運作可以在軟體模擬矩陣乘法中見到，預先將矩陣轉置，利用快取優勢速度可以快上 8 倍以上。

問題描述

給予一個記憶體空間大小為 $M$，使用 Least Recently Used (LRU) 策略進行置換，LRU 的策略為將最久沒有被使用過的空間替換掉，也就是需要從硬碟讀取 $disk[i]$ 到 $memory$ 時，發現記憶體都已經用光，則把不常用的 $mem[j]$ 寫入 $disk[k]$，再將 $disk[i]$ 內容寫入 $mem[j]$。

下圖是一個 $M = 4$ 簡單的範例：

       +---+     +---+     +---+     +---+     +---+     +---+     +---+     +---+
mem[0] | 1 |     | 1 |     | 1 |     | 1 |     | 1 |     | 1 |     | 1 |     | 1 |
       +---+     +---+     +---+     +---+     +---+     +---+     +---+     +---+
mem[1] |   |     | 2 |     | 2 |     | 2 |     | 2 |     | 2 |     | 2 |     | 2 |
       +---+ +-> +---+ +-> +---+ +-> +---+ +-> +---+ +-> +---+ +-> +---+ +-> +---+
mem[2] |   |     |   |     | 3 |     | 3 |     | 3 |     | 3 |     | 5 |     | 5 |
       +---+     +---+     +---+     +---+     +---+     +---+     +---+     +---+
mem[3] |   |     |   |     |   |     | 4 |     | 4 |     | 4 |     | 4 |     | 3 |
       +---+     +---+     +---+     +---+     +---+     +---+     +---+     +---+ 
         1         2         3         4         1         2         5         3

依序使用 1, 2, 3, 4, 1, 2, 5, 3 的配置情況，特別是在 5 使用的時候，會將記憶體中上一次最晚使用的 3 替換掉。

現在寫程式去模擬置換情況。

Sample Input

Sample Output

Solution

軟體仿作，使用一個 hash 和一個 list 進行維護，而不是使用 priority queue 來維護，用 list 取代之。當進行取址時，順道把對應 list 指針移動，所有步驟期望複雜度都是在 $O(1)$ 完成，若使用 priority queue 會掉到 $O(\log n)$ 去進行更新。

換出作業系統題目，來一個最常見到的快取 LRU 算法。這個問題在 Leetcode OJ 上面也有，公司面試有機會遇到。

但實作時被自己坑，比較柳柳州給予的測試，速度居然慢個二十多倍。原因是這樣子的

1 2	map[key] = value; return map.find(key);

替換成以下寫法，速度就起飛了。

1	return map.insert({key, value}).first;

也就是說插入的時候順便把指針拿到，避免第二次搜索。

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, list<int>::iterator> PIT_TYPE;
typedef unordered_map<int, pair<int, list<int>::iterator> >::iterator HIT_TYPE;
class LRUCache {
public:	
    int memIdx, size;
    list<int> time;
    vector<int> mem;
    unordered_map<int, PIT_TYPE> addr;
    LRUCache(int capacity) {
    	size = capacity;
        mem.resize(capacity, 0);
        addr.clear(), time.clear();
        memIdx = 0;
    }
    
    pair<int, int> get(int key) {
    	it = addr.find(key);
        if (it == addr.end())
            it = replace(key), mem[it->second.first] = 0;
        it->second.second = recent(it->second.second);
        return make_pair(it->second.first, mem[it->second.first]);
    }
    
    HIT_TYPE set(int key, int value) {
        it = addr.find(key);
        if (it == addr.end())
        	it = replace(key);
        it->second.second = recent(it->second.second);
        mem[it->second.first] = value;
        return it;
    }
private:
    HIT_TYPE it;
    HIT_TYPE replace(int key) {
        int mpos = -1, trash;
        list<int>::iterator lpos;
        if (addr.size() == size) {
            trash = time.front(), time.pop_front();
            it = addr.find(trash);
            mpos = it->second.first;
            addr.erase(it);
        } else {
            mpos = memIdx++;
        }
        lpos = time.insert(time.end(), key);
        return addr.insert({key, make_pair(mpos, lpos)}).first;
    }
    list<int>::iterator recent(list<int>::iterator p) {
        int key = *p;
        time.erase(p);
        return time.insert(time.end(), key);
    }
};
int main() {
    int M, cmd, x, y;
    pair<int, int> t;
    scanf("%d", &M);
    
    LRUCache LL(M);
    while (scanf("%d", &cmd) == 1) {
        if (cmd == 0) {
            scanf("%d", &x);
            pair<int, int> t = LL.get(x);
            printf("%d %d\n", t.first, t.second);
        } else {
            scanf("%d %d", &x, &y);
            LL.set(x, y);
        }
    }
    return 0;
}

Morris' Blog