华为机考真题 -- 内存冷热标记

题目描述：

现代计算机系统中通常存在多级的存储设备，针对海量 workload 的优化的一种思路是将热点内存页优先放到快速存储层级，这就需要对内存页进行冷热标记。一种典型的方案是基于内存页的访问频次进行标记，如果统计窗口内访问次数大于等于设定阈值，则认为是热内存页，否则是冷内存页。对于统计窗口内跟踪到的访存序列和阈值，现在需要实现基于频次的冷热标记。内存页使用页框号作为标识。

输入描述：

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

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

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

输出描述：

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

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

示例1：

输入
10
1 2 1 2 1 2 1 2 1 2
5
输出
2
1
2
说明：内存页 1 和内存页 2 均被访问了 5 次，达到了阈值 5，因此热内存页有 2 个。内存页 1和内存页 2 的访问频次相等，页框号小的排前面。

示例2：

输入
5
1 2 3 4 5
3
输出
0
说明：访存跟踪里面访问频次没有超过 3 的，因此热内存页个数为 0。

C++源码：

#include <iostream>
#include <sstream>
#include <vector>
#include <map>
#include <algorithm>

using namespace std;

bool compare(const pair<int, int>& a, const pair<int, int>& b) {
    return (a.second * 100 + (100 - a.first)) > (b.second * 100 + (100 - b.first));
}

int main() {
    int num;
    cin >> num;
    string line;
    getline(cin, line); // Consume the newline character left by cin
    getline(cin, line);
    stringstream ss(line);
    vector<int> l;
    int temp;
    while (ss >> temp) {
        l.push_back(temp);
    }
    int threshold;
    cin >> threshold;

    map<int, int> dic;
    for (int i : l) {
        dic[i]++;
    }

    map<int, int> new_dic;
    for (const auto& entry : dic) {
        if (entry.second >= threshold) {
            new_dic[entry.first] = entry.second;
        }
    }

    vector<pair<int, int>> sorted_items(new_dic.begin(), new_dic.end());
    sort(sorted_items.begin(), sorted_items.end(), compare);

    if (num == 0 || sorted_items.empty()) {
        cout << 0 << endl;
    }
    else {
        cout << sorted_items.size() << endl;
        for (const auto& item : sorted_items) {
            cout << item.first << endl;
        }
    }

    system("pause");
    return 0;
}

原文地址：https://blog.csdn.net/qq_25360769/article/details/140313519

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！