大文本按行去重（2G 左右文件）有什么好的解决方案吗？

V2EX = way to explore

V2EX 是一个关于分享和探索的地方

现在注册

已注册用户请登录

这是一个创建于 1466 天前的主题，其中的信息可能已经有所发展或是发生改变。

速度可以稍慢一点，但也不能太慢（一两个小时跑不完那种不使用 Spark 之类的计算引擎麻烦大佬们给小弟个解决方案

Spark

小弟

方案

文本

36 条回复 • 2020-11-11 20:57:52 +08:00

aloxaf

2020-11-10 14:52:20 +08:00

2G 算啥大文本，不要求保持原始顺序的话直接 `sort -u` 就行了。

skypyb

2020-11-10 14:57:05 +08:00

可以接受一点点误差的话
布隆过滤器

loliordie

2020-11-10 14:59:51 +08:00 via Android

随便挑个语言 load 到内存里 o(n)复杂度迭代一次就完事了

会用 pandas 用 pandas 不会就用 python 的 set 来实现处理速度基本等同于 io 的速度

liangfengmark

2020-11-10 15:00:41 +08:00

python set

sl19981007

2020-11-10 15:04:21 +08:00

@loliordie 好吧，我没说清楚，我们同时间可能会有多个这种去重的任务。

way2explore2

2020-11-10 15:05:31 +08:00

@loliordie 正解，2g 直接内存

2020-11-10 15:06:15 +08:00

直接 sort -u，磁盘速度够的话，一分钟完事

icyalala

2020-11-10 15:06:30 +08:00

2G 直接哈希表都能搞定，甚至直接 awk 一行命令：
awk '!a[$0]++' input.txt > output.txt

t6attack

2020-11-10 15:12:34 +08:00

<?php
ini_set('memory_limit',-1);
$array = file('源文件.txt');
$array = array_unique($array);
file_put_contents('输出文件.txt',implode($array,""));
?>
我一直用的方法。也就上面有人说的，直接内存处理。

loliordie

2020-11-10 15:13:18 +08:00 via Android

@sl19981007 取决于你的 tradeoff 是空间复杂度优先还是时间复杂度优先

如果是要多个任务同时处理时间复杂度优先内存够大直接搞个 celery 之类的多线程库就行了内存不够大就锁队列只允许 n 个任务同时运行

更简单一点可以输入多个路径挨个处理连多线程库都不用上就是同时只能有一个任务正在运行但你这个需求最大瓶颈在于硬盘 io 所以多个并行或者串行影响都不大

mengzhuo

2020-11-10 15:14:04 +08:00

才 2G，直接上哈希表干就完了

一堆超大文件倒是可以试试我的 nabhash
http://nabhash.org/

aladdindingding

2020-11-10 15:54:01 +08:00

linux 命令就行 sort | unique

MOONLIGHTT

2020-11-10 16:44:18 +08:00

别自己写，用 linux 的内建命令

knightdf

2020-11-10 17:14:29 +08:00

2G 而已，sort 都挺快的

hotpot6147

2020-11-10 17:33:26 +08:00

2g 的文本直接 load 进内存，然后 hash 去重就可以了。

如果 pc 机内存不够可以对每行数据进行 hash 后取模分布在 n 个文件中，然后再将这 n 个文件分别 load 进内存去重

BBCCBB

2020-11-10 17:35:11 +08:00

我感觉这种都是先遍历, 按文本 hash 拆分成足够小的文件, 然后在内存足够的情况下去处理每个小文件, 最后 merge 起来就完成了你说的需求了..

一般都是按 hash 拆分, 然后处理每个小文件, 最后再合并.

BBCCBB

2020-11-10 17:35:44 +08:00

不过这是针对超大文件的, 你这个 2G 真的可以试试直接 load 到内存.

Xusually

2020-11-10 17:37:15 +08:00

我开个脑洞，存数据库里。单行内容做主键，不停按行 insert，emmm......

gainsurier

2020-11-10 17:38:02 +08:00

emeditor，十几秒搞定

aec4d

2020-11-10 18:11:08 +08:00

瓶颈是磁盘 IO, 针对选一个 hash https://github.com/rust-lang/hashbrown,按行读取,如果 hash 值已存在则跳过,猜测十秒能完成吧

janxin

2020-11-10 18:43:52 +08:00

这数据量直接 load 到内存里怎么玩都行

NCE

2020-11-10 19:54:15 +08:00

这应该是个面试题

winglight2016

2020-11-10 20:08:26 +08:00

@NCE 的确，我在金山面试 android 时有被问过类似问题

nowgoo

2020-11-10 20:47:44 +08:00

linux 环境 sort/awk，windows 环境 editplus/emeditor

rainfd

2020-11-10 21:37:16 +08:00

sort | unique

m30102

2020-11-10 23:11:25 +08:00

LinekdHashSet 行不？

Mohanson

2020-11-10 23:39:52 +08:00

任意"去重"或"排序"的面试题答"字典树"绝对得分的.

fewok

2020-11-11 00:20:34 +08:00

@loliordie o(n)复杂度怕是搞不定吧

loliordie

2020-11-11 05:13:36 +08:00 via Android

@fewok 为何搞不定不就是 n 次查哈希表的操作么?

mogami18

2020-11-11 06:06:52 +08:00

我還以為是 2T

oneoyn

2020-11-11 09:15:40 +08:00 via Android

2G 我的 cpu 可以秒开

fewok

2020-11-11 10:08:54 +08:00

@loliordie 建哈希表或者查哈希表就不算复杂度嘛？

newmlp

2020-11-11 10:43:22 +08:00

2g 而已，全部读到内存就完事了

vincent7245

2020-11-11 11:47:25 +08:00

所以你为什么不用 spark 呢 /狗头

loliordie

2020-11-11 12:44:50 +08:00

@fewok 你可能需要理解下 O(n)复杂度的意义, 大 O 计算法考察的是时间规模跟输入规模的关系, 哈希表复杂度为 O(1), 不会影响时间复杂度, 除非你使用了 listnode 这样的结构, 每次查询元素时都会迭代, 随着输入规模的增加查询时间也会增加这样才会导致复杂度从 O(n)变为 O(n^2)

hxy100

2020-11-11 20:57:52 +08:00

Linux 直接上 sort 或者 uniq 命令即可，Windows 下的话直接 Emeditor 打开，点一下去重按钮就完事。