lfu页面置换算法例题

### LFU 页面置换算法 示例题目

#### 示例场景描述
假设有一个具有四个页面框的内存系统，采用最少使用 (LFU) 页面置换算法来管理页面。初始状态下，所有页面框为空。

给定一系列页面访问序列如下：

| 时间 | 访问页面 |
|------|----------|
| t=1 | A |
| t=2 | B |
| t=3 | C |
| t=4 | D |
| t=5 | E |
| t=6 | F |

其中每个字母代表不同的虚拟地址空间中的一页数据。每当遇到一个新的页面时，如果当前没有足够的空闲帧容纳新页面，则按照 LFU 算法替换掉最不常用的页面。

#### 运行过程分析

- **t=1**: 将A放入第一个可用的页面框内；此时无其他选项可选。

- **t=2**: 同样地，B也被放置于第二个位置上；同样不存在竞争情况。

- **t=3**: 接下来C进入第三个槽位；依旧如此操作直到填满整个缓存区为止。

- **t=4**: 此刻D到来并占据最后一个剩余的位置，至此四页已全部装载完毕。

- **t=5**: 当E到达时发现已经没有更多空白区域可供分配了。因此需要依据频率统计决定哪个是最少使用的项以便将其驱逐出去。由于每一页仅被引用过一次，在这种情况下可以随机挑选任意一项作为牺牲品——这里选择移除A，并让位于新的访客E。

- **t=6**: 对F而言，再次面临相同的选择困境。现在有三个候选者(B,C,D)，它们各自拥有相同的最低频次记录(即各有一次命中)。于是乎，可以从这三个之中选取任何一个进行淘汰处理。此处假定选择了B来进行替换。

最终状态下的页面布局可能是这样的：{C, D, E, F}[^1]

from collections import defaultdict, OrderedDict

class LFUCache:

    def __init__(self, capacity: int):
        self.capacity = capacity
        self.page_frequency = defaultdict(int)
        self.frequency_page_map = {}
        self.cache = OrderedDict()

    def get(self, page_id: str) -> any:
        if page_id not in self.cache:
            return None
        
        value = self.cache.pop(page_id)
        self.cache[page_id] = value
        frequency = self.page_frequency[page_id]
        
        # Remove from old frequency list and add to new one.
        del self.frequency_page_map[frequency][page_id]
        if not self.frequency_page_map[frequency]:
            del self.frequency_page_map[frequency]
            
        updated_freq = frequency + 1
        self.page_frequency[page_id] += 1
        if updated_freq not in self.frequency_page_map:
            self.frequency_page_map[updated_freq] = OrderedDict()
        self.frequency_page_map[updated_freq][page_id] = True
            
        return value
    
    def put(self, page_id: str, value: any) -> None:
        if self.capacity <= 0:
            return
        
        if page_id in self.cache:
            self.get(page_id)
            self.cache[page_id] = value
            return
        
        if len(self.cache) >= self.capacity:
            min_freq = min(self.frequency_page_map.keys())
            lru_page_in_min_freq = next(iter(self.frequency_page_map[min_freq]))
            del self.cache[lru_page_in_min_freq]
            del self.page_frequency[lru_page_in_min_freq]
            del self.frequency_page_map[min_freq][lru_page_in_min_freq]
            if not self.frequency_page_map[min_freq]:
                del self.frequency_page_map[min_freq]
                
        self.cache[page_id] = value
        self.page_frequency[page_id] = 1
        if 1 not in self.frequency_page_map:
            self.frequency_page_map[1] = OrderedDict()
        self.frequency_page_map[1][page_id] = True


lfu_cache_example = LFUCache(capacity=4)

actions_sequence = [
    ('put', 'A'),
    ('put', 'B'),
    ('put', 'C'),
    ('put', 'D'),
    ('put', 'E'), 
    ('put', 'F')
]

for action, arg in actions_sequence:
    getattr(lfu_cache_example, action)(arg)
print(list(lfu_cache_example.cache))