P2580. 文件缓存系统

解题思路

题意理解

系统设计的大模拟题，关键还是在于读懂题意。用人话捋一遍题目。

文件缓存系统可以认为是一个池子。 对这个文件池子我们可以做两件事情：

• 往池子里扔文件，对应操作 put fileName fileSize，其中 fileName 是文件名字，fileSize 是文件大小。
• 查看池子里已有的文件，对应操作 get fileName，其中 fileName 是文件名字。

池子具有一个容量上限值，当放入一个新文件的空间不足时，需要删除掉若干之前放入的文件，来腾出空间放这个最新的文件。 删除文件具有优先级：

1. 优先删除之前访问次数最少的文件，也就是 get fileName 调用次数最少的那个。 2. 如果访问次数相同，则删除最近一次访问时间最早的那个文件。

不断删除文件，直到最后有足够空间放入新文件。

题目问的是，经过若干次操作之后，池子里还剩下哪些文件。

数据结构设计

每次插入或访问文件 fileName 的时候，我们都要修改这个文件的访问次数以及访问时间。 所以我们需要通过 fileName 的信息，来获取先前信息。 很容易想到这种快速查找以及修改，需要用到哈希表来实现。

可以以文件名字 fileName 作为 key，访问次数、最近访问时间、文件大小所构成的三元组 [getCount, lastGetTime, fileSize] 作为 value，构建哈希表。

例如，在执行了以下语句：

之后，表示系统缓存的哈希表形如：

那么对每一次插入和访问文件操作，都可以操作哈希表来表示文件缓存系统的变化了。

每行输入均为带空格的一个字符串。我们对其根据空格进行切割，再做后续判断和对应操作，即：

插入操作

当 ops[0] == "put" 时，对应插入操作。ops 是一个三元组，插入的文件名和文件大小可以通过 ops 得到：

当以下两种情况出现时，可以直接跳过该插入操作：

• 文件名 fileName 已经存在于哈希表 dic 中，即之前已经插入过同名文件。
• 文件大小 fileSize 超过了缓存最大值，即就算把整个缓存系统都清空，都无法插入该文件。

在将文件加入缓存系统之前，我们还需要判断缓存系统是否包含足够的空间来存储该文件。 如果空间不足，则需要删除若干文件，直至空间足够。

因为不知道需要删除多少文件，所以需要在一个 while 循环 中持续地进行删除操作，循环不变量为 maxSize - curSize < fileSize。 maxSize - curSize 表示剩余空间，如果剩余空间小于文件大小，则需要不断删除。

对应的代码为：

删除完毕后，可以进行插入操作，同时需要更新当前缓存系统的空间 curSize，即：

综上，插入操作对应的代码为：

访问操作

当 ops[0] == "get" 时，对应访问操作。ops 是一个二元组，访问的文件名可以通过 ops 得到：

然后需要判断访问的文件名 fileName 是否在之前已经存在于缓存系统中，即是否位于哈希表 dic 中。若：

• 不存在，则直接跳过。
• 存在，则 fileName 的访问次数 +1，且更新访问时间。

综上，访问操作对应的代码为：

复杂度分析 设操作总数为 N，某一时刻缓存中的文件数为 k（k 不超过已执行的 put 次数，也不超过 N）。get 操作只做一次哈希查找和两次字段更新，O(1)。put 操作中，判重和判超容量都是 O(1)，真正的开销在腾空间的 while 循环：每删除一个文件都要用 min 对整个哈希表扫一遍，按「访问次数最少、其次最近访问时间最早」找出待删文件，单次删除代价 O(k)。不过每个文件最多被插入一次、也最多被删除一次，全程删除的总次数不超过 put 的总次数，因此删除部分的总代价上界是 O(N·k)，最坏情况（文件都很小、反复触发淘汰）为 O(N²)。收尾对剩余文件名排序为 O(k log k)。整体时间复杂度 O(N²)，瓶颈在删除时对哈希表的线性扫描；空间复杂度 O(N)，即哈希表中至多同时保存的文件条目。若要进一步优化，可用按（访问次数，访问时间）组织的有序结构把「找牺牲者」降到 O(log k)，但在本题的数据规模下线性扫描已经足够。