(100分)- 内存冷热标记（Java JS Python C）

(100分)- 内存冷热标记Java JS Python C题目描述现代计算机系统中通常存在多级的存储设备针对海量 workload 的优化的一种思路是将热点内存页优先放到快速存储层级这就需要对内存页进行冷热标记。一种典型的方案是基于内存页的访问频次进行标记如果统计窗口内访问次数大于等于设定阈值则认为是热内存页否则是冷内存页。对于统计窗口内跟踪到的访存序列和阈值现在需要实现基于频次的冷热标记。内存页使用页框号作为标识。输入描述第一行输入为 N表示访存序列的记录条数0 N ≤ 10000。第二行为访存序列空格分隔的 N 个内存页框号页面号范围 0 ~ 65535同一个页框号可能重复出现出现的次数即为对应框号的频次。第三行为热内存的频次阈值 T正整数范围 1 ≤ T ≤ 10000。输出描述第一行输出标记为热内存的内存页个数如果没有被标记的热内存页则输出 0 。如果第一行 0则接下来按照访问频次降序输出内存页框号一行一个频次一样的页框号页框号小的排前面。用例输入101 2 1 2 1 2 1 2 1 25输出212说明内存页1和内存页2均被访问了5次达到了阈值5因此热内存页有2个。内存页1和内存页2的访问频次相等页框号小的排前面。输入51 2 3 4 53输出0说明访存跟踪里面访存频次没有超过3的因此热内存个数为0。题目解析多条件排序的实现方案。具体逻辑详见代码实现部分。JavaScript算法源码const rl require(readline).createInterface({ input: process.stdin }); var iter rl[Symbol.asyncIterator](); const readline async () (await iter.next()).value; void (async function () { const n parseInt(await readline()); const seqs (await readline()).split( ).map(Number); const cnts {}; for (let num of seqs) { cnts[num] (cnts[num] ?? 0) 1; // ?? 是高级语法如果cnts[num]为null或者undefined时返回0实际牛客环境可能不支持 } const threshold parseInt(await readline()); // Object.entries返回的是数组返回值数组的元素也是一个数组[key, value]其中key,value就是对象的键值对 const entries Object.entries(cnts).filter((a) a[1] threshold); console.log(entries.length); // entries元素数组的索引0是对象key索引1是对象val entries .sort((a, b) (a[1] ! b[1] ? b[1] - a[1] : a[0] - b[0])) .forEach((a) console.log(a[0])); })();Java算法源码import java.util.HashMap; import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc new Scanner(System.in); int n sc.nextInt(); HashMapInteger, Integer cnts new HashMap(); for (int i 0; i n; i) { int num sc.nextInt(); cnts.put(num, cnts.getOrDefault(num, 0) 1); } int threshold sc.nextInt(); cnts.keySet().removeIf(num - cnts.get(num) threshold); System.out.println(cnts.size()); cnts.entrySet().stream() .sorted( (a, b) - a.getValue() - b.getValue() ! 0 ? b.getValue() - a.getValue() : a.getKey() - b.getKey()) .forEach(a - System.out.println(a.getKey())); } }Python算法源码# 输入获取 n int(input()) seqs list(map(int, input().split())) threshold int(input()) # 统计各个内存页框号出现的次数 cnts {} for num in seqs: cnts.setdefault(num, 0) cnts[num] 1 # 过滤出现次数达到阈值的内存页即热内存页数量 items list(filter(lambda x: x[1] threshold, cnts.items())) # 打印热内存页数量 print(len(items)) # 如果存在热内存页 if len(items) 0: # 那么优先按照访问频次降序如果访问频次相同则再按页框号升序items中记录元素是[页框号, 访问频次] items.sort(keylambda x: (-x[1], x[0])) for num, _ in items: print(num)C算法源码#include stdio.h #include stdlib.h #define MAX_SIZE 10000 typedef struct Mem { int num; int count; } Mem; int cmp(const void *a, const void *b) { Mem *A *((Mem **) a); Mem *B *((Mem **) b); if (A-count ! B-count) { return B-count - A-count; } else { return A-num - B-num; } } int main() { int n; scanf(%d, n); Mem *mem[MAX_SIZE]; int mem_size 0; for (int i 0; i n; i) { int num; scanf(%d, num); int j 0; for (; j mem_size; j) { if (mem[j]-num num) { mem[j]-count; break; } } if(j mem_size) continue; mem[mem_size] (Mem *) malloc(sizeof(Mem)); mem[mem_size]-num num; mem[mem_size]-count 1; mem_size; } int threshold; scanf(%d, threshold); qsort(mem, mem_size, sizeof(Mem *), cmp); int hot_mem_size mem_size; for (int i 0; i mem_size; i) { if (mem[i]-count threshold) { hot_mem_size i; break; } } printf(%d\n, hot_mem_size); for (int i 0; i hot_mem_size; i) { printf(%d\n, mem[i]-num); } return 0; }