内存受限环境下大通话记录文件的最近N个去重号码查询方案

问题背景 #

我们有一个超大的通话历史文件，每行存储一个被叫电话号码，文件按通话发生时间升序排列（越靠后的行对应越新的通话）。需要实现一个函数满足：

• 跳过最近的M条记录
• 从剩余记录中提取最近出现的最多N个不同号码（逻辑等价于：遍历所有记录时，若号码已在列表则移至开头，否则插入开头；最终取列表中第M到M+N的条目）
• 限制条件：文件无法全量载入内存，所有不同号码的集合也装不下内存，不能写入临时文件，N是较小值，M可等于文件总行数。

解决方案 #

核心思路是反向遍历文件，同时维护一个大小不超过N的候选集合，全程内存占用固定为O(N)，完美适配内存受限场景。具体步骤如下：

• 步骤1：跳过最近M条记录
  从文件末尾开始反向读取，先读取并丢弃前M行（对应原文件的最后M条最新记录）。

• 步骤2：维护候选集合
  继续反向读取剩余行，同时维护一个字典candidates（键为电话号码，值为该号码在反向遍历中的位置pos——pos从1开始计数，值越小代表原文件中出现时间越晚），字典大小始终不超过N：

  • 若当前号码已在candidates中：仅当当前pos小于字典中存储的pos时更新（说明该号码在此处的出现时间比之前记录的更晚），否则直接跳过。
  • 若当前号码不在candidates中：
    • 若字典未满（大小<N）：直接将号码加入字典，pos设为当前反向遍历的位置。
    • 若字典已满：找到字典中pos最大的号码（即该号码在有效范围内最后出现时间最早），如果当前号码的pos小于这个最大值（说明当前号码的最后出现时间比该候选晚），则替换掉这个候选；否则跳过当前号码。

• 步骤3：生成结果
  遍历完成后，将candidates中的号码按pos从小到大排序（对应原文件中最后出现时间从新到旧），得到的就是目标结果。

方案优势 #

• 内存占用严格可控：字典最多存储N个号码，完全适配N为较小值的要求，无论文件规模多大、不同号码数量多少，都不会出现内存溢出。
• 逻辑精准匹配需求：反向遍历筛选出的是有效范围内最后出现时间最晚的N个不同号码，和原伪代码最终要提取的结果完全等价——原伪代码的列表顺序本质就是号码最后出现时间从新到旧，跳过M条后取前N个的逻辑，和本方案的筛选结果一致。

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