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

题目描述

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

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

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

输入描述

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

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

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

输出描述

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

如果第一行 > 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();

    HashMap<Integer, 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(key=lambda 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("%dn", hot_mem_size);

    for (int i = 0; i < hot_mem_size; i++) {
        printf("%dn", mem[i]->num);
    }

    return 0;
}