如何高效查找任意3分钟区间内访问量最高的资源

核心优化逻辑 #

常规方案的性能瓶颈在于通用比较排序的O(n log n)时间复杂度，我们可以利用本题给定的*秒级时间戳取值范围固定为0~86399（当日24小时总秒数）*的特性，用桶排序替代通用比较排序，将整体时间复杂度压低到线性O(n)，已经达到该问题的理论时间下界（至少需要遍历所有记录一次）。

具体执行步骤 #

• 初始化三类数据结构
  • 时间桶数组：固定长度86400，每个位置对应当日的某一秒，每个数组元素为哈希表，存储该秒下各个资源的访问次数，初始全为空
  • 窗口计数器：哈希表，实时存储当前3分钟滑动窗口内各个资源的总访问量
  • 全局峰值记录：存储当前统计到的单资源3分钟窗口最高访问量，以及对应的资源路径
• 单遍遍历原始记录完成排序（时间复杂度O(n)，n为总记录数）
  对每条[时间戳, 资源路径]的原始记录，直接找到时间戳对应的数组下标，将该位置哈希表中对应资源的计数+1。这一步不需要任何比较操作，直接完成所有记录的按时间排序。
• 滑动窗口遍历时间桶统计峰值（时间复杂度O(1)，86400为固定常量，和输入规模无关）
  维护窗口左边界初始为0，右边界从0到86399逐秒遍历：
  1. 将当前右边界对应时间桶内的所有资源访问次数，累加到窗口计数器中，每完成一个资源的累加就和全局峰值对比，若超过则更新峰值记录
  2. 检查当前窗口时间跨度右边界 - 左边界是否≥180（3分钟对应秒数），如果是则将左边界对应时间桶内的所有资源计数从窗口计数器中扣减，左边界右移，直到窗口跨度小于180

方案优势说明 #

对比常规先排序后统计的方案，该方案在记录数超过1万时性能提升就会非常明显，百万级以上记录的场景下性能可以提升数倍到数十倍。空间上固定大小的时间桶仅占用几十KB内存，完全可以忽略。

能不能在排序的同时同步完成统计？
因为原始记录是完全乱序的，单遍遍历原始记录时无法判断后续是否有更早的时间戳属于同一个3分钟窗口，因此必须先完成按时间的排序再做窗口统计。但本方案中的桶排序已经是该场景下的最优排序方式，排序过程本身已经是线性时间，没有进一步优化的空间。

内容的提问来源于stack exchange，提问作者sakurashinken