高峰在线人数:登录登出日志一遍扫描线,算出峰值和持续时长

真实验证:扫描线 vs 暴力按秒计数,交叉核对

用真实 Python 实现了两种算法:一种是扫描线(下面演示用的这套),另一种是笨办法——把一天 86400 秒摊成数组,每条记录把自己覆盖的每一秒都 +1,最后扫一遍找最大值。同一份数据分别跑两遍:

sweep_result = sweep_peak(small_records)
brute_result = brute_force_peak(small_records, 0, 10000)
print(sweep_result, brute_result, sweep_result == brute_result)

两种算法算出来的"峰值=3、持续 1550 秒"完全一致。暴力法只适合小数据集验证正确性(按秒摊开来,数据量一大内存和时间都扛不住),真正拿来用的是扫描线这一套,复杂度是排序的 O(n log n),不用管一天有多少秒。

真实验证:退出事件必须排在登录事件前面

如果 A 在第 1000 秒整退出,B 恰好在第 1000 秒整登录,这一秒到底算不算"两人同时在线"?构造了一个真实用例验证:

records = [("A", 500, 1000), ("B", 1000, 1500), ("C", 0, 2000)]
correct = sweep_peak(records, logout_before_login=True)
wrong   = sweep_peak(records, logout_before_login=False)

把登录事件排在退出事件前面,会把"A 还没走、B 已经来了"这个根本不存在的瞬间也算成 3 人在线——峰值凭空多算 1,而且这个虚假峰值的持续时长是 0(因为它只是排序造成的一个瞬间假象,不是真实状态)。正确做法是同一秒里先处理完所有退出、再处理登录。

真实验证:30 万条模拟记录,算法真实耗时

N = 300_000  # 真实生成的模拟登录登出记录条数
peak, duration = sweep_peak(records)

30 万条记录、真实排序 + 扫描一遍,600 毫秒出头——数据量再大,瓶颈也主要在排序这一步,不需要额外的分桶或者近似算法。如果数据量大到内存都放不下呢?外部排序这篇本机真实实现了"分块落盘 + 多路归并"的完整方案,还接上这里的扫描线算法验证了整条流水线。"持续时长"具体是按什么规则累加、什么时候清零重算,这篇用真实构造的用例专门拆开讲清楚了。如果拿不到真实的事件时间、只能用日志写入时间代替呢?这篇真实验证了这么做什么时候安全、什么时候会系统性地把峰值算高。