在1G内存下去重40亿个QQ号，假设QQ号为32位整数，可采用以下步骤：

---

解决方案：位图（Bitmap）法

1. 位图初始化

• 位图大小：
  QQ号范围为1到2³²（0到4,294,967,295），需要4,294,967,296个位，即 512MB（4,294,967,296 bits ÷ 8 = 536,870,912字节）。
• 内存分配：
  分配512MB内存作为位图，剩余内存用于数据缓存。

2. 分批次处理数据

• 数据分块：
  40亿个QQ号（约16GB）无法一次性加载到内存，需分批次读取。
  每次读取约 500MB数据（1G内存 - 512MB位图 ≈ 500MB），可缓存约 1.25亿个QQ号（500MB ÷ 4字节/QQ号 = 125,000,000个）。
• 处理逻辑：

  # 伪代码示例
  bitmap = bytearray(512 * 1024 * 1024)  # 512MB位图
  
  with open("qq_numbers.bin", "rb") as f:
      while True:
          # 读取1.25亿个QQ号（500MB）
          chunk = f.read(500 * 1024 * 1024)
          if not chunk:
              break
          # 转换为整数列表
          qq_list = struct.unpack("I" * (len(chunk)//4), chunk)
          # 更新位图
          for qq in qq_list:
              index = qq // 8
              offset = qq % 8
              if not (bitmap[index] & (1 << offset)):
                  bitmap[index] |= (1 << offset)
  
  # 输出去重后的QQ号
  with open("unique_qq.txt", "w") as out:
      for qq in range(0, 2**32):
          index = qq // 8
          offset = qq % 8
          if bitmap[index] & (1 << offset):
              out.write(f"{qq}\n")

3. 去重结果输出

• 遍历位图：
  遍历所有4,294,967,296个可能的QQ号，检查位图中对应位是否为1。
  • 耗时估算：
    若每秒处理100万QQ号，需约1.2小时完成遍历。

---

优化策略

1. 并行处理

   • 多线程读取：分多个线程读取不同数据块，各自更新独立的子位图，最后合并位图。
   • SIMD加速：使用AVX指令集批量处理位操作。

2. 压缩位图

   • 稀疏位图压缩：若QQ号分布稀疏，使用Roaring Bitmap压缩空间（如实际QQ号集中在某区间）。

3. 分布式处理

   • 分片处理：若单机内存不足，将数据按哈希分片到多台机器，各自维护子位图，最终汇总结果。

---

对比其他方案

方案	内存占用	时间复杂度	精确性	实现复杂度
位图（Bitmap）	512MB	O(n)	100%	低
外部排序去重	1GB	O(n log n)	100%	中
布隆过滤器	≈100MB*	O(n)	有误判	中

*布隆过滤器按1%误判率估算。

---

总结

位图法是最优解，优势如下：

1. 内存高效：仅需512MB即可覆盖所有可能的QQ号。
2. 时间复杂度低：线性时间完成去重。
3. 实现简单：无需复杂算法，仅需位操作。

适用场景：

• 数据范围已知且密集（如32位整数）。
• 需精确去重，不能容忍误判。