内存冷热标记（C语言）

题目来自于博主算法大师的专栏：最新华为OD机试C卷+AB卷+OJ（C++JavaJSPy） https://blog.csdn.net/banxia_frontend/category_12225173.html

题目描述

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

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

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

输入描述

第一行输入为 N，表示访存序列的记录条数，0 < N ≤ 10000

第二行为访存序列，空格分隔的 N 个内存页框号

第三行为阈值

输出描述

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

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

用例1

输入

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

输出

2
1
2
1
2
3

说明 ：在这个例子中，内存页框号 1 和 2 都被访问了 5 次，达到了阈值，因此它们被标记为热内存页。输出首先是热内存页的数量 2，然后是按照访问频次降序排列的页框号 1 和 2(频次一样的页框号，页框号小的排前面)。

用例2

输入

5
1 2 3 4 5
3
1
2
3

输出

0
1

说明：在这个例子中，没有任何内存页的访问次数达到阈值 3，因此没有热内存页，输出为 0。

代码

#include <stdio.h>
#include <stdlib.h>
// 定义一个常量，用于限制内存页框号的最大数量
#define MAX_NUM 10000

// 定义结构体PageFrequency，存储每个内存页框号及其访问频次
typedef struct {
    int num;       // 内存页框号
    int frequency; // 访问频次
} PageFrequency;

// 定义比较函数cmp，用于qsort排序。这里按照访问频次降序排序，频次相同时按照页框号升序排序
int cmp(const void *a, const void *b) {
    PageFrequency *p1 = (PageFrequency *)a;
    PageFrequency *p2 = (PageFrequency *)b;
    if (p1->frequency != p2->frequency) {
        return p2->frequency - p1->frequency; // 频次高的排在前面
    } else {
        return p1->num - p2->num;             // 频次相同时，页框号小的排前面
    }
}

int main() {
    int n; // 访存序列记录条数
    scanf("%d", &n);

    // 创建数组page存储输入的访存序列
    int page[n];
    for (int i = 0; i < n; i++) {
        scanf("%d", &page[i]);
    }

    int threshold; // 访问频次阈值
    scanf("%d", &threshold);

    // 初始化所有内存页框的访问频次为0
    PageFrequency p[MAX_NUM] = {0};

    // 根据访存序列统计各个内存页框的访问频次
    for (int i = 0; i < n; i++) {
        p[page[i]].num = page[i]; // 设置页框号
        p[page[i]].frequency++;   // 增加对应页框号的访问频次
    }

    // 创建hot数组存储标记为热内存页的页框信息
    PageFrequency hot[MAX_NUM];
    int hot_num = 0; // 热内存页的数量

    // 遍历所有内存页框，找出访问频次大于等于阈值的页框并加入hot数组
    for (int i = 0; i < MAX_NUM; i++) {
        if (p[i].frequency >= threshold) {
            hot[hot_num].num = p[i].num;
            hot[hot_num].frequency = p[i].frequency;
            hot_num++;
        }
    }

    // 输出热内存页的数量
    printf("%d\n", hot_num);

    // 如果存在热内存页，则对hot数组进行排序，并输出排序后的页框号
    if (hot_num > 0) {
        qsort(hot, hot_num, sizeof(PageFrequency), cmp);
        for (int i = 0; i < hot_num; i++) {
            printf("%d\n", hot[i].num);
        }
    }

    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70

注意

1、为什么 PageFrequency *p1 这里面要加*

在C语言中，* 是指针运算符。当我们声明一个变量如 PageFrequency *p1 时，p1 是一个指向 PageFrequency 结构体类型的指针。

这里的 * 表示 p1 变量存储的是一个地址，这个地址指向一块内存区域，该内存区域存放着一个 PageFrequency 结构体实例的数据（即包含 num 和 frequency 成员）。

在 cmp 函数内部，我们需要访问通过指针传递进来的结构体成员，所以需要对指针解引用。例如，p1->frequency 实际上是访问 p1 所指向的 PageFrequency 结构体实例中的 frequency 成员。这里的 -> 运算符用于通过结构体指针访问结构体成员。

总结一下，PageFrequency *p1 中的 * 表示 p1 是一个指针，并且在后续代码中使用 p1->frequency 或 p1->num 来访问结构体成员时，体现了指针解引用的过程。

2、结构体的初始化

typedef struct {
    int num;
    int frequency;
} Hot;
Hot hot[MAX_NUM]={0};
1
2
3
4
5

Hot hot[MAX_NUM]={0};大括号 {0} 是对数组所有元素进行初始化，这里的 0 表示对数组中每个结构体实例的所有成员都初始化为零（即 num 和 frequency 都被初始化为 0）。

3、本题中由于需要实现“频次一样的页框号，页框号小的排前面”，所以使用了结构体，便于按要求排序