返回目录

题目描述

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

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

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

输入描述

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

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

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

输出描述

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

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

示例:

输入10
 1  2 1 2 1 2 1 2 1 2
 5
输出2
1
2
说明内存页1和内存页2均被访问了5次，达到了
阈值5，因此热内存页有2个。内存页1和内
存页2的访问频次相等，页框号小的排前面。
输入5
1 2 3 4 5
3
输出0
说明访存跟踪里面访存频次没有超过3的，因此热
内存个数为0。

题目解析

简单的多条件排序问题。

具体逻辑请看代码实现。

Python算法源码

class MemoryAnalyzer:
    def __init__(self, memory_size, sequence, threshold_value):
        self.memory_size = memory_size
        self.sequence = sequence
        self.threshold_value = threshold_value

    def analyze_memory(self):
        page_counts = {}
        for num in self.sequence:
            page_counts.setdefault(num, 0)
            page_counts[num] += 1

        hot_pages = list(filter(lambda x: x[1] >= self.threshold_value, page_counts.items()))

        print(len(hot_pages))

        if hot_pages:
            hot_pages.sort(key=lambda x: (-x[1], x[0]))

            for page, _ in hot_pages:
                print(page)

# 获取输入
memory_size = int(input("Enter memory size: "))
sequence = list(map(int, input("Enter memory sequence: ").split()))
threshold_value = int(input("Enter threshold value: "))

# 实例化并分析内存
analyzer = MemoryAnalyzer(memory_size, sequence, threshold_value)
analyzer.analyze_memory()

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;
}

Java算法源码

import java.util.HashMap;
import java.util.Scanner;
import java.util.Map.Entry;
import java.util.stream.Collectors;

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();

        // 过滤出现次数达到阈值的内存页
        HashMap<Integer, Integer> hotPages = filterHotPages(cnts, threshold);

        // 打印热内存页数量和页框号
        printHotPages(hotPages);
    }

    // 过滤出现次数达到阈值的内存页
    public static HashMap<Integer, Integer> filterHotPages(HashMap<Integer, Integer> cnts, int threshold) {
        HashMap<Integer, Integer> hotPages = new HashMap<>();
        for (Entry<Integer, Integer> entry : cnts.entrySet()) {
            if (entry.getValue() >= threshold) {
                hotPages.put(entry.getKey(), entry.getValue());
            }
        }
        return hotPages;
    }

    // 打印热内存页数量和页框号
    public static void printHotPages(HashMap<Integer, Integer> hotPages) {
        System.out.println(hotPages.size());
        hotPages.entrySet().stream()
                .sorted((a, b) -> b.getValue() - a.getValue() != 0
                        ? b.getValue() - a.getValue()
                        : a.getKey() - b.getKey())
                .forEach(a -> System.out.println(a.getKey()));
    }
}
最后修改：2024 年 03 月 31 日
© 允许规范转载
如果觉得我的文章对你有用，请随意赞赏