刷题笔记合集🔗

内存冷热标记

问题描述

现代计算机系统中通常存在多级的存储设备，针对海量 workload 的优化的一种思路是将热点内存页优先放到快速存储层级，这就需要对内存页进行冷热标记。

一种典型的方案是基于内存页的访问频次进行标记，如果统计窗口内访问次数大于等于设定阈值，则认为是热内存页，否则是冷内存页。

对于统计窗口内跟踪到的访存序列和阈值，现在需要实现基于频次的冷热标记。内存页使用页框号作为标识。

输入格式

第一行输入为 ，表示访存序列的记录条数，。

第二行为访存序列，空格分隔的 个内存页框号，页面号范围 ，同一个页框号可能重复出现，出现的次数即为对应框号的频次。

第三行为热内存的频次阈值 ，正整数范围 。

输出格式

第一行输出标记为热内存的内存页个数，如果没有被标记的热内存页，则输出 。

如果第一行 ，则接下来按照访问频次降序输出内存页框号，一行一个，频次一样的页框号，页框号小的排前面。

样例输入

10
1 2 1 2 1 2 1 2 1 2
5

5
1 2 3 4 5
3

样例输出

2
1
2

0

数据范围

• ，其中 为访存序列的记录条数
• 页面号范围
• ，其中 为热内存的频次阈值

题解

这道题目考察的是哈希表的使用以及多条件排序。整体思路非常直观：统计每个内存页框号出现的次数，然后按照要求进行排序和输出。

具体步骤如下：

1. 读取输入：访存序列长度N、访存序列和频次阈值T
2. 使用哈希表统计每个内存页框号出现的次数
3. 筛选出出现次数大于等于阈值T的内存页框号，这些是热内存页
4. 对热内存页进行排序：首先按频次降序，频次相同则按页框号升序
5. 按要求输出结果

在本题中，排序是一个关键点。在大多数语言中，我们可以定义一个自定义的排序规则来实现多条件排序。在Python中，可以使用sort函数的key参数；在C++中，可以重载比较函数；在Java中，可以使用Comparator接口。

时间复杂度分析：

• 统计频次需要O(N)时间
• 排序需要O(M log M)时间，其中M是热内存页的数量，最坏情况下M = N
• 因此，总体时间复杂度为O(N + N log N) = O(N log N)

空间复杂度为O(N)，主要用于存储哈希表。

对于给定的数据范围（N最大为10000），这个算法的效率是完全可以接受的。

参考代码

• Python

import sys
input = lambda:sys.stdin.readline().strip()

# 读取输入
n = int(input())
page_frames = list(map(int, input().split()))
threshold = int(input())

# 统计每个页框号出现的频次
frequency = {}
for frame in page_frames:
    frequency[frame] = frequency.get(frame, 0) + 1

# 筛选出热内存页
hot_pages = [(frame, freq) for frame, freq in frequency.items() if freq >= threshold]

# 输出结果
print(len(hot_pages))
if hot_pages:
    # 按频次降序排列，频次相同则按页框号升序
    hot_pages.sort(key=lambda x: (-x[1], x[0]))
    for frame, _ in hot_pages:
        print(frame)

• Cpp

#include <bits/stdc++.h>
using namespace std;

in