一、题目
请设计一个文件缓存系统，该文件缓存系统可以指定缓存的最大值（单位为字节）。
文件缓存系统有两种操作：
操作命令为：
- 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 的整数
四、示例
示例一
1
2
3
4
5
6
7
| 输入：
50
1
get file
输出：
NONE
|
示例二
1
2
3
4
5
6
7
8
9
10
11
12
| 输入：
50
6
put a 10
put b 20
get a
get a
get b
put c 30
输出：
a,c
|
五、题解
- 实现 LFU（访问次数+最后访问时间）的缓存系统
- 数据结构用一个 Map + 优先级队列（最小堆）实现，需要注意自定义优先级队列的比较函数
- 最后一次访问时间可以用
逻辑时间，因为只关心访问的先后顺序，不关心具体的时间值
5.1 Java 实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
| package org.stone.study.algo.ex202411;
import java.util.*;
public class FileCaceSystem {
private int maxSize;
private int curSize;
private Map<String, FileObj> cache;
private PriorityQueue<FileObj> pq;
private long time;
public static void main(String[] args) {
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]);
}
}
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));
}
}
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实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
| 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 = {}
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()
|
