我能想到的两种不同的做法。 第一种，在内存不足的情况下，放弃掉内存，直接用 SSD 读写。 在 SSD 上开一个数据库（比如 MySQL 或者 Postgres ），把已经存在的 hash 写到数据库里。 然后流式扫描每一行，取 hash 比对数据库，如果存在 hash 就跳过，不存在就写到结果集里并添加到数据库。 要快速稳妥可以用两种不同的 hash ，比如 xxHash 做一次过滤，SHA1 做二次检验。 第二种，在内存不足的情况下，分批处理。 多次流式扫描每一行，取 hash ，每次只处理 hash 第一个 hex 字符相同的那些数据。 第一次只索引和处理 sha1hash[0] == '0'，第二次只索引和处理'1'，这样可以把内存需求降到 1/16 ，缺点是 hash 计算也会是 16 倍。 稍微优化一下的话，可以在第一次遍历的时候在数据上追加 sha1hash[0]作为分区标记，这样后面 15 次就不会重复计算，缺点是会每行多一两个字节，而且要多写入一次磁盘。
想到个方法，预计耗时：10 小时，准确率：100% 剔除重复行。 ## 简单流程 1. 分块排序。 2. 同时循环每块，删掉非首次出现的重复行。 3. 分别循环每块，按行号顺序，输出未被删掉的行。 ## 详细流程 1. 分块 240GB 文件，每块排序后，写入固态。同时保存每行长度+原始偏移量（约 (240 排）所有分块每一行。非首次出现行，保存该行偏移量，到相应块的删除名单里。 3. 循环每块，排序原始偏移量、删除名单，按序输出（未被删除的）相应行，至最终文件。 ## 耗时计算 1. 顺序读写：9 小时（ 3 次顺序读，2 次顺序写，假设都为 1GB/s ）。 2. 内存字符串排序：< 1 小时（实测轻薄本 i5-8250U ，每秒归并排序 200W 次 335 长度的随机字符串，约 6900W 次比较）。 - 多线程快排/归并：`(每块行数 = (240 << 30) / 335) * log2(每块行数) * 块数 = 6017 亿` 次比较，我的轻薄本 8 线程需 0.3 小时。 - 单线程小根堆：`202e8 * log2(块数 = 6.2 * 1024 / 240 = 26.5) * 2 = 1910 亿` 次比较，需 0.7 小时。
34 楼纠正下数据，实测轻薄本 i5-8250U ，1.5 秒归并排序 320W 个 336 长度的随机字符串，约 6500W 次比较。 - 多线程快排/归并：总计 6017 亿次比较，我的轻薄本 8 线程需 0.5 小时。 - 单线程小根堆：总计 1910 亿次比较，单线程需 1.2 小时。 差不太远。。
@dcsuibian #2 ，@opengps #3 ，@msg7086 #32： 如果数据库，每秒写入 10W 条，总计要 203e8 / 1e5 / 3600 = 56 小时？ @YTMartian #26 ，@dode #27： 就算固态 4K 随机读写有 10W IOPS ，算下来也要 56 小时吧？
@cndenis #14 ，@hbcolorful #17 ，@NotLongNil #30： 用布隆过滤，几十 GB 好像不够。 在线算了下，50 GB + 15 函数，都会有 1 / 25000 概率出错。。 250 GB + 11 函数，算完 203 亿行，才能有 83.8% 的概率，一个不出错？ @phrack #15： 压缩内存，来存 hash ？好像真的可行。。 平均而言，写入 (372 << 30) / 4096 = 1 亿次，就会占满 372 GB 内存页。即，几乎一开始就会启用 zram ？ 我在别处看了看，lz4 每秒能有 200W 次 IO ，算下来要 2.8 小时即可？ 话说，这个和 Bloom Filter 相比，哪个出错概率小呢？
