简易日志轮转
P5493. 简易日志轮转
场次:2026年10月22日-非AI方向 · 来源:CodeFun2000 P5493
题目描述
实现一套轻量日志组件。单文件容量上限为 ,全部文件体积之和不得超过 。
请实现类 :
- :完成初始化。
- :向编号 的模块当前文件整段写入长度为 的一条记录,返回该文件写入后的体积。规则如下:
- 每个模块单独维护文件序列,序号各自从 递增,旧文件可并存;
- 若本次写入会使全体文件体积之和越过 ,就按生成先后去掉最老的文件(跨模块一起看),直到写完后不再越界;
- 该模块若没有可写的当前文件,就开一份新文件当作当前文件;若当前文件再写入会越过 ,先关掉它再开一份新的当作当前文件。
- :按生成先后给出仍在的文件,每项写成 。
- :给出当前全体文件体积之和。
说明:
- 删掉某模块的当前文件后,该模块视为没有当前文件,下次再写会开新序号
- 因超单文件上限而关掉的文件仍占额度,只是不再往里写
约束:累计调用 ;;。
输入格式
每行一次函数调用,首行必为 。
输出格式
每次调用一行:
- 构造输出
- / 输出整数
- 输出二维整型数组,形如
示例
示例 1
输入:
FileLogger(8, 50)
putLog(3, 2)
putLog(3, 3)
putLog(4, 7)
putLog(3, 4)
totalSize()
listFiles()输出:
null
2
5
7
4
16
[[3, 1, 5], [4, 1, 7], [3, 2, 4]]说明:
- 模块 先开 号文件,写入 再写入 ,当前文件变成
- 模块 开 号文件,写入
- 再给模块 写 : 超过单文件 ,关掉 号并新建 号写入
- 全体体积
示例 2
输入:
FileLogger(6, 16)
putLog(1, 5)
putLog(2, 4)
putLog(1, 3)
putLog(2, 5)
totalSize()
listFiles()输出:
null
5
4
3
5
12
[[2, 1, 4], [1, 2, 3], [2, 2, 5]]说明:
- 前三次之后文件是 、、,合计
- 再给模块 写 :合计将变成 ,越过总额 ,按生成先后去掉 ,此时 不再越界
- 模块 的当前文件再写会 越过单文件 ,关掉后新建
示例 3
输入:
FileLogger(5, 20)
putLog(9, 3)
listFiles()
totalSize()输出:
null
3
[[9, 1, 3]]
3说明: 只有一份新文件。
解题思路
接口题先看状态:三张表各回答一个问题
这题没有算法,只有一本要记清楚的账。把「随时可能被问到的问题」列出来,数据结构就自己定下来了:
| 问题 | 谁回答 |
|---|---|
| 最早生成的那份文件是哪个? | 按生成顺序排的队列(先进先出) |
| 模块 现在写的是哪份文件? | 哈希表 current:模块号 → 文件 |
| 模块 下一份文件编号几? | 哈希表 next_seq:模块号 → 序号 |
三处必须指向同一个文件对象。文件用一个小列表 [模块号, 序号, 体积] 表示,队列里放它、current[mid] 里也放它,于是「加了多少字节」只有一份记录:写进去之后,队列那头立刻看得到。若图省事在队列里另存一份体积,淘汰时算出来的总量就会和真实占用对不上。
def __init__(self, file_cap: int, total_cap: int) -> None:
self.file_cap = file_cap # 单份文件上限
self.total_cap = total_cap # 全体文件之和上限
self.total_size = 0
self.files = deque() # 按生成先后排队:[模块号, 序号, 体积]
self.current = {} # 模块号 -> 该模块当前在写的那份文件
self.next_seq = {} # 模块号 -> 下一份文件的序号构造器的参数顺序要照题面抄: 是「先单文件、后总额」,示例 1 的 就是单文件 8 字节、总额 50 字节。按习惯写成「先总额后单文件」的话,这一组样例连第 4 次写入的淘汰判断都会错( 会误触发淘汰)。
淘汰阶段:先腾空间,再决定往哪写
淘汰的判据是「写入之后会不会超标」。既然判的是写入后,腾空间就必须发生在真正加字节之前——否则会撞上一个很隐蔽的局面:文件 是某个模块的当前文件,同时也是队列里最早的一份;先往 里加字节,再回头看总量超标,于是一路从队首删,第一个被删的正是刚刚写完的 。返回值给了一份已经不存在的文件的体积,账面彻底对不上。
所以顺序是固定的:先按 total_size + nbytes > total_cap 反复出队,再去挑选或新建文件。
while self.files and self.total_size + nbytes > self.total_cap:
old = self.files.popleft() # 最早生成的那份
self.total_size -= old[2] # 账要跟着减
if self.current.get(old[0]) is old:
del self.current[old[0]] # 指针失效,下次重开一份while 的条件里带上 self.files 是防御:如果 本身比 还大,怎么删都放不下,靠这个条件退出,不会空转。
淘汰的连带动作:删掉的若是「当前文件」,指针要一起清掉
这是本题唯一真正容易漏的一处。删文件时只把体积从总量里减掉、却把 current[mid] 留在原处,下一次 putLog(mid, ...) 会拿到一个已经不在队列里的文件,接着往里写:接口返回值是它的历史累计体积,而 total_size 与队列里各文件体积之和从此不再相等——之后每一次淘汰判断都建立在错误的账上。
判定用的是对象身份(is),不是 ==:两份不同的文件本来就不该被认成同一份。清掉之后,current 里没有这个模块的条目,建文件那一步自然会走「新开一份」的分支,序号照常递增(题面特意写明:删掉当前文件后,下次再写会开新序号)。
建文件阶段:什么时候开新文件,返回什么
新开的条件是两条之一:该模块没有当前文件(从没写过,或刚被淘汰),或者当前文件再写就超过 。判据用的是严格大于:size + nbytes == fileCap 恰好写满,仍然留在同一份文件里,不算越界。
def putLog(self, mid: int, nbytes: int) -> int:
# ……淘汰那一段见上一节,这里只写选文件、写入与返回……
cur = self.current.get(mid)
if cur is None or cur[2] + nbytes > self.file_cap:
seq = self.next_seq.get(mid, 1) # 第一次开文件时序号是 1
self.next_seq[mid] = seq + 1
cur = [mid, seq, 0]
self.files.append(cur) # 新文件排在队尾,最晚被淘汰
self.current[mid] = cur
cur[2] += nbytes
self.total_size += nbytes
return cur[2] # 返回这份文件写入后的体积next_seq 与 current 是两张不同的表:current 会因为淘汰被清空,序号却要继续往下走——模块 1 的 [1,1] 被删掉之后,下一份是 [1,2] 而不是重新回到 [1,1]。把这两件事混用一张表,淘汰一次就会让序号回退、文件名撞车。
两个查询只是把账本念出来
totalSize() 直接返回 total_size,listFiles() 按队列顺序把每份文件抄成 [mid, idx, sz]。队列本身就是生成顺序,不需要额外排序;抄一份而不是把内部列表直接交出去,是因为那些列表还在被 putLog 原地修改,调用方拿到引用后一旦改动就会污染账本。
def listFiles(self):
return [list(f) for f in self.files]
def totalSize(self):
return self.total_size均摊 O(1):每份文件只入队、出队各一次
每次 putLog 里,队列可能一口气弹出好几项,单次调用的耗时不是常数;但把全部调用合起来看,每份文件只被创建一次、删除一次,总弹出次数不超过创建次数。所以总量是 ,均摊到每次调用是 。
这里对容器的选择有一个实际差别:list.pop(0) 每次都要把后面的元素整体前移,单次淘汰 ( 是在册文件数),最坏总量退成 ;collections.deque 的 popleft() 是 。
完整代码实现
from collections import deque
class FileLogger:
"""日志轮转器:file_cap 是单份文件上限,total_cap 是全体文件之和上限。"""
def __init__(self, file_cap: int, total_cap: int) -> None:
self.file_cap = file_cap
self.total_cap = total_cap
self.total_size = 0
self.files = deque() # 按生成先后排队:[模块号, 序号, 体积]
self.current = {} # 模块号 -> 该模块当前在写的那份文件
self.next_seq = {} # 模块号 -> 下一份文件的序号
def putLog(self, mid: int, nbytes: int) -> int:
# 第 1 步:总量不够就先按生成顺序删掉最早的文件
while self.files and self.total_size + nbytes > self.total_cap:
old = self.files.popleft()
self.total_size -= old[2]
if self.current.get(old[0]) is old:
# 删掉的正是某个模块的当前文件:指针必须清掉,
# 否则下一次会往一份已经不存在的文件里接着写
del self.current[old[0]]
# 第 2 步:没有当前文件,或这份文件装不下,就新开一份
cur = self.current.get(mid)
if cur is None or cur[2] + nbytes > self.file_cap:
seq = self.next_seq.get(mid, 1)
self.next_seq[mid] = seq + 1
cur = [mid, seq, 0]
self.files.append(cur)
self.current[mid] = cur
# 第 3 步:写进当前文件,返回它写入后的体积
cur[2] += nbytes
self.total_size += nbytes
return cur[2]
def listFiles(self):
"""按生成先后返回仍在的文件。"""
return [list(f) for f in self.files]
def totalSize(self):
"""当前全体文件体积之和。"""
return self.total_size示例推演
示例 1:
| 调用 | 淘汰 | 模块的当前文件 | 返回 | 总占用 |
|---|---|---|---|---|
FileLogger(8, 50) | — | — | null | 0 |
putLog(3, 2) | 无() | 无 → 新建 [3,1], | 2 | 2 |
putLog(3, 3) | 无() | [3,1] 有 , → 续写, | 5 | 5 |
putLog(4, 7) | 无() | 无 → 新建 [4,1], | 7 | 12 |
putLog(3, 4) | 无() | [3,1] 有 , → 关掉并新建 [3,2], | 4 | 16 |
totalSize() | — | — | 16 | 16 |
listFiles() | — | — | [[3,1,5], [4,1,7], [3,2,4]] | 16 |
这一组里总额 50 从头到尾都没被逼近,触发切分的只有单文件上限——第 5 行 5+4=9 越过 8,模块 3 换成 2 号文件。listFiles() 的顺序是生成顺序,所以 [3,1,5] 在最前、[3,2,4] 在最后,尽管它们属于同一个模块。
示例 2:
| 调用 | 淘汰 | 模块的当前文件 | 返回 | 总占用 |
|---|---|---|---|---|
FileLogger(6, 16) | — | — | null | 0 |
putLog(1, 5) | 无() | 无 → 新建 [1,1], | 5 | 5 |
putLog(2, 4) | 无() | 无 → 新建 [2,1], | 4 | 9 |
putLog(1, 3) | 无() | [1,1] 有 , → 关掉并新建 [1,2], | 3 | 12 |
putLog(2, 5) | → 删队首 [1,1](),总占用 ; 停 | [2,1] 有 , → 关掉并新建 [2,2], | 5 | 12 |
totalSize() | — | — | 12 | 12 |
listFiles() | — | — | [[2,1,4], [1,2,3], [2,2,5]] | 12 |
第 5 行是同一次调用里发生两件事的样本:先按总额淘汰掉队首的 [1,1],再按单文件上限给模块 2 换一份新文件。淘汰的 [1,1] 不是模块 1 的当前文件(当前是 [1,2]),所以 current 不需要清。
示例 3:
putLog(9, 3):模块 9 没有当前文件,新建 [9,1] 写入 3,返回 3,总占用 3。listFiles() 得到 [[9,1,3]],totalSize() 得到 3。
复杂度分析
| 解法 | 时间复杂度 | 空间复杂度 | 说明 |
|---|---|---|---|
用 list 当队列(pop(0) 删队首) | 总量 | 每次淘汰都要把列表整体前移, 为在册文件数 | |
deque + 两张哈希表(最优) | 总量 ,单次均摊 | 每份文件只创建一次、删除一次,总弹出次数不超过调用次数 |
为调用次数。 的范围由容量与最小写入量决定:最坏情况下每个文件只写 字节,在册文件数可以到 。空间只需要「当前在册的文件」这一份记录,被淘汰的文件对象直接丢弃。
易错点总结
1. 淘汰时忘了把体积从 total_size 里减掉
while 里只写了 self.files.popleft()、漏掉 self.total_size -= old[2],总量就只增不减。在示例 2 的第 5 次调用上:账面总占用应降到 、再写到 ,漏减时仍是 ,于是 继续弹,把 [2,1,4] 与 [1,2,3] 也删光,队列清空才退出;模块 2 仍会新建 [2,2,5]、返回 5,但最后 totalSize() 返回 22、listFiles() 只剩 [[2,2,5]],与官方输出对不上。之后每次调用都会被判成「超标」,totalCap 形同虚设(账面可以超过上限),所有文件被反复删光重开。
2. 删掉了当前文件却不清指针
if self.current.get(old[0]) is old: del ... 这两行缺了,下一次 putLog 会拿到一份已经从队列里删掉的文件继续写。取 :putLog(1, 2) 返回 2、putLog(2, 2) 返回 2(总占用 4),第三次 putLog(1, 2) 时 先淘汰队首 [1,1,2]——它正是模块 1 的当前文件;少了那两行,代码认为 [1,1] 还有 2 字节, 于是续写,返回 4,而正确结果是开新文件 [1,2,2] 后返回 2。表面上只是数值不对,本质上是往一份已经不在账本里的文件写数据,此后 total_size 与各文件体积之和永久失配。
3. 单文件限写成 >= 而不是 >
判断应从 cur[2] + nbytes > self.file_cap 出发:恰好写满不算越界。改成 >= 之后, 下连续两次 putLog(1, 2),第二次会切分出一份新文件、返回 2,而正确行为是留在同一份、返回 4;每一次「刚好填满」的写入都会被切成两份,listFiles() 里的文件数直接翻倍。