背景

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

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

方案一

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

方案二

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 替換掉。

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