返回目录

题目描述

请设计一个文件缓存系统，该文件缓存系统可以指定缓存的最大值（单位为字节）。

文件缓存系统有两种操作：

• 存储文件（put）
• 读取文件（get）

操作命令为：

• put fileName fileSize
• get fileName

存储文件是把文件放入文件缓存系统中；

读取文件是从文件缓存系统中访问已存在，如果文件不存在，则不作任何操作。

当缓存空间不足以存放新的文件时，根据规则删除文件，直到剩余空间满足新的文件大小位置，再存放新文件。

具体的删除规则为：文件访问过后，会更新文件的最近访问时间和总的访问次数，当缓存不够时，按照第一优先顺序为访问次数从少到多，第二顺序为时间从老到新的方式来删除文件。

输入描述

第一行为缓存最大值m（整数，取值范围为 0 < m ≤ 52428800）

第二行为文件操作序列个数 n（0 ≤ n ≤ 300000）

从第三行起为文件操作序列，每个序列单独一行，文件操作定义为：

op file\_name file\_size

file\_name 是文件名，file\_size 是文件大小

输出描述

输出当前文件缓存中的文件名列表，文件名用英文逗号分隔，按字典顺序排序，如：

a,c

如果文件缓存中没有文件，则输出NONE

备注

1. 如果新文件的文件名和文件缓存中已有的文件名相同，则不会放在缓存中
2. 新的文件第一次存入到文件缓存中时，文件的总访问次数不会变化，文件的最近访问时间会更新到最新时间
3. 每次文件访问后，总访问次数加1，最近访问时间更新到最新时间
4. 任何两个文件的最近访问时间不会重复
5. 文件名不会为空，均为小写字母，最大长度为10
6. 缓存空间不足时，不能存放新文件
7. 每个文件大小都是大于 0 的整数

示例：

题思路

主要考察“最少使用频率”（Least Frequently Used, LFU）缓存策略的文件缓存系统。这种缓存系统特别适用于需要优先保留最常被访问的项的场景。解题思路和方法如下：

解题思路：

1. 初始化数据结构:

   • 存储文件及其属性（文件名、大小、访问次数、最后访问时间）。
   • 使用（最小堆）维护文件的删除顺序，基于访问次数和最后访问时间。

2. 处理输入:

   • 接收缓存的最大容量和操作数。
   • 对于每个操作（存储或获取文件），解析并执行相应的逻辑。

3. 缓存操作:

   • put方法：添加新文件到缓存。如果缓存已满，先移除访问次数最少且最早的文件，然后添加新文件。
   • get方法：从缓存中检索文件，同时更新其访问次数和最后访问时间。

4. 更新和维护缓存:

   • 每当文件被访问时，更新其在 文件信息和 最小堆中的信息。
   • 当缓存空间不足时，根据LFU策略移除文件。

LFU缓存方法：

LFU缓存是一种缓存算法，用于管理有限的资源（如内存）。其核心思想是当需要空间时，优先移除访问频率最低的项。与之相对的是LRU（最近最少使用）缓存，后者基于时间顺序（最近使用的）移除元素。

LFU缓存的关键特点：

• 访问计数：每个缓存项都有一个与之关联的访问计数器，记录该项被访问的次数。
• 优先级队列：使用优先级队列（如最小堆）来保持项的顺序，基于访问次数。
• 动态调整：缓存项的访问计数随着时间的推移动态更新，以反映其使用频率。

Python算法源码

import heapq

class FileCacheSystem:
    class File:
        def __init__(self, name, size, last_access_time):
            self.name = name  # 文件名
            self.size = size  # 文件大小
            self.access_count = 1  # 访问计数
            self.last_access_time = last_access_time  # 上次访问时间

    def __init__(self, max_cache_size):
        self.max_cache_size = max_cache_size  # 最大缓存大小
        self.current_cache_size = 0  # 当前缓存大小
        self.cache = {}  # 缓存字典，键为文件名，值为文件对象
        self.min_heap = []  # 最小堆，用于按大小和访问计数排序文件
        self.time = 0  # 记录操作时间

    def put(self, file_name, file_size):
        if file_size > self.max_cache_size:
            return

        if file_name in self.cache:
            self.get(file_name)
            return

        while self.current_cache_size + file_size > self.max_cache_size:
            _, _, to_remove = heapq.heappop(self.min_heap)  # 弹出堆顶元素
            del self.cache[to_remove]  # 从缓存中删除对应文件
            self.current_cache_size -= to_remove.size  # 更新当前缓存大小

        file = self.File(file_name, file_size, self.time)  # 创建文件对象
        self.cache[file_name] = file  # 将文件对象添加到缓存
        heapq.heappush(self.min_heap, (file.size, file.access_count, file))  # 将文件元组添加到最小堆
        self.current_cache_size += file_size  # 更新当前缓存大小
        self.time += 1  # 更新操作时间

    def get(self, file_name):
        if file_name not in self.cache:
            return

        file = self.cache[file_name]
        self.min_heap.remove((file.size, file.access_count, file))  # 从最小堆中移除对应文件
        file.access_count += 1  # 增加访问计数
        file.last_access_time = self.time  # 更新最后访问时间
        heapq.heappush(self.min_heap, (file.size, file.access_count, file))  # 将文件元组添加到最小堆
        self.time += 1  # 更新操作时间

    def get_current_cache(self):
        files = list(self.cache.keys())  # 获取缓存中的所有文件名
        files.sort()  # 对文件名排序
        return files  # 返回排序后的文件名列表

def main():
    max_cache_size = int(input())  # 输入最大缓存大小
    operations_count = int(input())  # 输入操作数

    cache_system = FileCacheSystem(max_cache_size)  # 创建文件缓存系统对象

    for _ in range(operations_count):
        operation, file_name, *extra = input().split()  # 输入操作和文件名
        if operation == "put":
            file_size = int(extra[0])  # 输入文件大小
            cache_system.put(file_name, file_size)  # 执行放置文件操作
        elif operation == "get":
            cache_system.get(file_name)  # 执行获取文件操作

    current_cache = cache_system.get_current_cache()  # 获取当前缓存中的文件名列表
    if not current_cache:
        print("NONE")  # 若当前缓存为空，则打印"NONE"
    else:
        print(",".join(current_cache))  # 打印当前缓存中的文件名，以逗号分隔

if __name__ == "__main__":
    main()  # 执行主函数

C算法源码

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_FILENAME_LENGTH 50

// 文件结构体
typedef struct {
    char name[MAX_FILENAME_LENGTH];  // 文件名
    int size;  // 文件大小
    int access_count;  // 访问计数
    int last_access_time;  // 上次访问时间
} File;

// 文件缓存系统结构体
typedef struct {
    int max_cache_size;  // 最大缓存大小
    int current_cache_size;  // 当前缓存大小
    File **cache;  // 缓存数组，存储文件指针
    int *min_heap;  // 最小堆数组，存储文件索引
    int time;  // 记录操作时间
} FileCacheSystem;

// 初始化文件缓存系统
FileCacheSystem* initFileCacheSystem(int max_cache_size) {
    FileCacheSystem *cache_system = (FileCacheSystem*)malloc(sizeof(FileCacheSystem));
    cache_system->max_cache_size = max_cache_size;
    cache_system->current_cache_size = 0;
    cache_system->cache = (File**)malloc(max_cache_size * sizeof(File*));
    cache_system->min_heap = (int*)malloc(max_cache_size * sizeof(int));
    cache_system->time = 0;
    return cache_system;
}

// 放置文件到缓存中
void put(FileCacheSystem *cache_system, char *file_name, int file_size) {
    if (file_size > cache_system->max_cache_size)
        return;

    for (int i = 0; i < cache_system->current_cache_size; i++) {
        if (strcmp(cache_system->cache[i]->name, file_name) == 0) {
            // 如果文件已存在于缓存中，更新文件信息
            cache_system->cache[i]->access_count++;
            cache_system->cache[i]->last_access_time = cache_system->time;
            return;
        }
    }

    while (cache_system->current_cache_size + file_size > cache_system->max_cache_size) {
        // 当缓存大小超过最大缓存大小时，移除最近最少访问的文件
        int to_remove_index = cache_system->min_heap[0];
        free(cache_system->cache[to_remove_index]);
        for (int i = 0; i < cache_system->current_cache_size - 1; i++) {
            cache_system->cache[i] = cache_system->cache[i + 1];
        }
        cache_system->current_cache_size--;
        for (int i = 0; i < cache_system->current_cache_size; i++) {
            if (cache_system->min_heap[i] == to_remove_index) {
                for (int j = i; j < cache_system->current_cache_size - 1; j++) {
                    cache_system->min_heap[j] = cache_system->min_heap[j + 1];
                }
                break;
            }
        }
    }

    // 创建新文件并放入缓存
    File *new_file = (File*)malloc(sizeof(File));
    strcpy(new_file->name, file_name);
    new_file->size = file_size;
    new_file->access_count = 1;
    new_file->last_access_time = cache_system->time;
    cache_system->cache[cache_system->current_cache_size] = new_file;
    cache_system->min_heap[cache_system->current_cache_size] = cache_system->current_cache_size;
    cache_system->current_cache_size++;
    cache_system->time++;
}

// 获取文件
void get(FileCacheSystem *cache_system, char *file_name) {
    for (int i = 0; i < cache_system->current_cache_size; i++) {
        if (strcmp(cache_system->cache[i]->name, file_name) == 0) {
            // 更新文件信息
            cache_system->cache[i]->access_count++;
            cache_system->cache[i]->last_access_time = cache_system->time;
            return;
        }
    }
}

// 获取当前缓存中的文件名列表
char** get_current_cache(FileCacheSystem *cache_system) {
    char **files = (char**)malloc(cache_system->current_cache_size * sizeof(char*));
    for (int i = 0; i < cache_system->current_cache_size; i++) {
        files[i] = (char*)malloc(MAX_FILENAME_LENGTH * sizeof(char));
        strcpy(files[i], cache_system->cache[i]->name);
    }
    return files;
}

// 主函数
int main() {
    int max_cache_size, operations_count;
    scanf("%d", &max_cache_size);  // 输入最大缓存大小
    scanf("%d", &operations_count);  // 输入操作数

    FileCacheSystem *cache_system = initFileCacheSystem(max_cache_size);  // 初始化文件缓存系统

    for (int i = 0; i < operations_count; i++) {
        char operation[4], file_name[MAX_FILENAME_LENGTH];
        int file_size;
        scanf("%s %s", operation, file_name);
        if (strcmp(operation, "put") == 0) {
            scanf("%d", &file_size);
            put(cache_system, file_name, file_size);  // 执行放置文件操作
        } else if (strcmp(operation, "get") == 0) {
            get(cache_system, file_name);  // 执行获取文件操作
        }
    }

    char **current_cache = get_current_cache(cache_system);  // 获取当前缓存中的文件名列表
    if (cache_system->current_cache_size == 0) {
        printf("NONE\n");  // 若当前缓存为空，则打印"NONE"
    } else {
        for (int i = 0; i < cache_system->current_cache_size; i++) {
            printf("%s", current_cache[i]);  // 打印当前缓存中的文件名
            if (i < cache_system->current_cache_size - 1)
                printf(",");
        }
        printf("\n");
    }

    // 释放内存
    for (int i = 0; i < cache_system->current_cache_size; i++) {
        free(current_cache[i]);
    }
    free(current_cache);
    for (int i = 0; i < cache_system->current_cache_size; i++) {
        free(cache_system->cache[i]);
    }
    free(cache_system->cache);
    free(cache_system->min_heap);
    free(cache_system);

    return 0;
}

Java算法源码

import java.util.*;

public class Main {
    // 文件缓存系统类
    static class FileCacheSystem {
        // 文件类
        private class File {
            String name; // 文件名
            int size; // 文件大小
            int accessCount; // 访问次数
            long lastAccessTime; // 最近访问时间

            // 文件构造函数
            File(String name, int size, long lastAccessTime) {
                this.name = name;
                this.size = size;
                this.accessCount = 1; // 初始访问次数为1
                this.lastAccessTime = lastAccessTime; // 设置最近访问时间
            }
        }

        // 缓存最大值
        private int maxCacheSize;
        // 当前缓存大小
        private int currentCacheSize = 0;
        // 缓存映射，存储文件名和文件信息
        private HashMap<String, File> cache;
        // 优先队列，用于维护删除顺序
        private PriorityQueue<File> minHeap;
        // 时间戳，用于更新文件的最近访问时间
        private long time;

        // 文件缓存系统构造函数
        public FileCacheSystem(int maxCacheSize) {
            this.maxCacheSize = maxCacheSize; // 设置缓存最大值
            this.cache = new HashMap<>(); // 初始化缓存映射
            // 初始化优先队列，比较器根据访问次数和最近访问时间排序
            this.minHeap = new PriorityQueue<>((a, b) -> {
                if (a.accessCount == b.accessCount) {
                    return Long.compare(a.lastAccessTime, b.lastAccessTime);
                }
                return a.accessCount - b.accessCount;
            });
            this.time = 0; // 初始化时间戳
        }

        // 存储文件方法
        public void put(String fileName, int fileSize) {
            if (fileSize > maxCacheSize) return; // 如果文件大小超过最大缓存，不存储

            if (cache.containsKey(fileName)) {
                get(fileName); // 如果文件已存在，更新访问次数和时间
                return;
            }

            // 当缓存空间不足时，删除访问次数最少且最早访问的文件
            while (currentCacheSize + fileSize > maxCacheSize) {
                File toRemove = minHeap.poll(); // 从优先队列中取出要删除的文件
                if (toRemove != null) {
                    cache.remove(toRemove.name); // 从缓存映射中删除
                    currentCacheSize -= toRemove.size; // 更新当前缓存大小
                }
            }

            // 创建新文件，添加到缓存映射和优先队列中
            File file = new File(fileName, fileSize, ++time);
            cache.put(fileName, file);
            minHeap.offer(file);
            currentCacheSize += fileSize; // 更新当前缓存大小
        }

        // 读取文件方法
        public void get(String fileName) {
            if (!cache.containsKey(fileName)) return; // 如果文件不存在，不作操作

            // 获取文件信息，更新访问次数和最近访问时间
            File file = cache.get(fileName);
            minHeap.remove(file); // 从优先队列中移除
            file.accessCount++; // 增加访问次数
            file.lastAccessTime = ++time; // 更新最近访问时间
            minHeap.offer(file); // 重新添加到优先队列
        }

        // 获取当前缓存文件名列表方法
        public List<String> getCurrentCache() {
            List<String> files = new ArrayList<>(cache.keySet()); // 获取所有文件名
            Collections.sort(files); // 按字典顺序排序
            return files;
        }
    }

    public static void main(String[] args) {
        // 创建扫描器读取输入
        Scanner scanner = new Scanner(System.in);
        // 读取缓存最大值
        int maxCacheSize = scanner.nextInt();
        // 读取操作数量
        int operationsCount = scanner.nextInt();
        scanner.nextLine(); // 清除行结束符

        // 初始化文件缓存系统
        FileCacheSystem cacheSystem = new FileCacheSystem(maxCacheSize);

        // 循环处理所有操作
        for (int i = 0; i < operationsCount; i++) {
            // 读取操作指令
            String[] input = scanner.nextLine().split(" ");
            String operation = input[0]; // 操作类型
            String fileName = input[1]; // 文件名

            // 如果是存储文件操作
            if ("put".equals(operation)) {
                int fileSize = Integer.parseInt(input[2]); // 文件大小
                cacheSystem.put(fileName, fileSize); // 存储文件
            } else if ("get".equals(operation)) { // 如果是读取文件操作
                cacheSystem.get(fileName); // 读取文件
            }
        }

        // 获取当前缓存中的文件名列表
        List<String> currentCache = cacheSystem.getCurrentCache();
        // 如果列表为空，输出NONE
        if (currentCache.isEmpty()) {
            System.out.println("NONE");
        } else { // 否则，输出文件名列表，用逗号分隔
            System.out.println(String.join(",", currentCache));
        }
    }
}