一、题目
请设计一个文件缓存系统，该文件缓存系统可以指定缓存的最大值（单位为字节）。
文件缓存系统有两种操作：
- 存储文件（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，最近访问时间更新到最新时间
- 任何两个文件的最近访问时间不会重复
- 文件名不会为空，均为小写字母，最大长度为10
- 缓存空间不足时，不能存放新文件
- 每个文件大小都是大于 0 的整数
四、示例
示例一
输入：
50
1
get file
输出：
NONE
示例二
输入：
50
6
put a 10
put b 20
get a
get a
get b
put c 30
输出：
a,c
五、题解
- 实现 LFU（访问次数+最后访问时间）的缓存系统
- 数据结构用一个 Map + 优先级队列（最小堆）实现，需要注意自定义优先级队列的比较函数
- 最后一次访问时间可以用
逻辑时间，因为只关心访问的先后顺序，不关心具体的时间值
5.1 Java 实现
package org.stone.study.algo.ex202411;
import java.util.*;
public class FileCaceSystem {
private int maxSize; // 缓存最大容量
private int curSize; // 当前缓存已使用大小
private Map<String, FileObj> cache; // 缓存KV
private PriorityQueue<FileObj> pq; //
private long time; // 逻辑时钟计数
public static void main(String[] args) {
/*
50
6
put a 10
put b 20
get a
get a
get b
put c 30
*/
Scanner scanner = new Scanner(System.in);
// 最大缓存容量
int maxSize = Integer.parseInt(scanner.nextLine());
// 操作次数
int n = Integer.parseInt(scanner.nextLine());
FileCaceSystem fileCaceSystem = new FileCaceSystem(maxSize);
for (int i = 0; i < n; i++) {
String line = scanner.nextLine();
String[] arr = line.split(" ");
if("put".equals(arr[0])) {
fileCaceSystem.put(arr[1], Integer.parseInt(arr[2]));
} else if("get".equals(arr[0])){
fileCaceSystem.get(arr[1]);
}
}
// a,c
fileCaceSystem.printCache();
}
public FileCaceSystem(int maxSize) {
this.maxSize = maxSize;
this.curSize = 0;
this.cache = new HashMap<>();
// 自定义小顶堆
this.pq = new PriorityQueue<>((f1, f2) -> {
if(f1.accessCount == f2.accessCount) {
return Long.compare(f1.lastAccessTime, f2.lastAccessTime);
} else {
return f1.accessCount - f2.accessCount;
}
});
}
public FileObj get(String fileName) {
if(!cache.containsKey(fileName)) {
return null;
}
// 出堆，入堆实现重新排序
FileObj file = cache.get(fileName);
pq.remove(file);
file.accessCount = file.accessCount + 1;
file.lastAccessTime = time++;
pq.offer(file);
return file;
}
public void put(String fileName, int fileSize) {
if(fileSize > maxSize) {
return;
}
if(cache.containsKey(fileName)) {
// 存在，则更新访问次数和逻辑时钟
get(fileName);
return;
}
// 空间不够，移除访问次数最少的元素
if(curSize + fileSize > maxSize) {
while(curSize + fileSize > maxSize) {
FileObj file = pq.poll();
curSize -= file.fileSize;
cache.remove(file.fileName);
}
}
// 空间够，新增元素
FileObj file = new FileObj(fileName, fileSize);
file.accessCount = 0;
file.lastAccessTime = time++;
curSize += fileSize;
cache.put(fileName, file);
pq.offer(file);
}
// 打印缓存中的元素，按文件名升序排序
public void printCache() {
if(cache.isEmpty()) {
System.out.println("NONE");
} else {
List<String> keys = new ArrayList<>(cache.keySet());
Collections.sort(keys);
// 打印列表中的元素，以逗号分隔
System.out.println(String.join(",", keys));
}
}
//使用静态内部类，减少冗长的 get/set 方法
static class FileObj {
private String fileName;
private int fileSize;
private int accessCount;
// 逻辑时钟，仅用来比较访问时间
private long lastAccessTime;
public FileObj(String fileName, int fileSize) {
this.fileName = fileName;
this.fileSize = fileSize;
this.accessCount = 0;
this.lastAccessTime = 0;
}
}
}5.2 Python实现
import heapq
class FileObj:
def __init__(self, file_name, file_size):
self.file_name = file_name
self.file_size = file_size
self.access_count = 0
self.last_access_time = 0
# 实现小于比较
def __lt__(self, other):
if self.access_count == other.access_count:
return self.last_access_time < other.last_access_time
return self.access_count < other.access_count
class FileCacheSystem:
def __init__(self, max_cache_size):
self.max_cache_size = max_cache_size
self.cache = {} # 缓存文件的字典，key为文件名，value为文件大小
self.cache_size = 0 # 当前缓存文件的大小
self.pq = [] # 小顶堆，先访问次数升序，再访问时间升序
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.cache_size + file_size > self.max_cache_size:
fileObj = heapq.heappop(self.pq)
del self.cache[fileObj.file_name]
self.cache_size -= fileObj.file_size
# 将文件加入缓存中
file_obj = FileObj(file_name, file_size)
self.cache[file_name] = file_obj
self.cache_size += file_size
heapq.heappush(self.pq, file_obj)
self.time += 1
# 访问缓存中的文件
def get(self, file_name):
if file_name not in self.cache:
# 如果文件不在缓存中，无法访问
return
# 如果文件在缓存中，更新访问次数和最后访问时间
file_obj = self.cache[file_name]
self.pq.remove(file_obj)
file_obj.access_count += 1
file_obj.last_access_time = self.time
self.time += 1
heapq.heappush(self.pq, file_obj)
# 输出缓存中的文件
def print_cache(self):
file_names = list(self.cache.keys())
if len(file_names) == 0:
print('NONE')
else:
file_names.sort()
print(','.join(file_names))
if __name__ == '__main__':
max_cache_size = int(input())
n = int(input())
cache_system = FileCacheSystem(max_cache_size)
for _ in range(n):
operation, file_name, *args = input().split()
if operation == 'put':
file_size = int(args[0])
cache_system.put(file_name, file_size)
elif operation == 'get':
cache_system.get(file_name)
cache_system.print_cache()