V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
sl19981007
V2EX  ›  程序员

大文本按行去重(2G 左右文件)有什么好的解决方案吗?

  •  
  •   sl19981007 · 2020-11-10 14:44:19 +08:00 · 4465 次点击
    这是一个创建于 690 天前的主题,其中的信息可能已经有所发展或是发生改变。

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

    36 条回复    2020-11-11 20:57:52 +08:00
    aloxaf
        1
    aloxaf  
       2020-11-10 14:52:20 +08:00   ❤️ 1
    2G 算啥大文本,不要求保持原始顺序的话直接 `sort -u` 就行了。
    skypyb
        2
    skypyb  
       2020-11-10 14:57:05 +08:00
    可以接受一点点误差的话
    布隆过滤器
    loliordie
        3
    loliordie  
       2020-11-10 14:59:51 +08:00 via Android
    随便挑个语言 load 到内存里 o(n)复杂度迭代一次就完事了

    会用 pandas 用 pandas 不会就用 python 的 set 来实现 处理速度基本等同于 io 的速度
    liangfengmark
        4
    liangfengmark  
       2020-11-10 15:00:41 +08:00
    python set
    sl19981007
        5
    sl19981007  
    OP
       2020-11-10 15:04:21 +08:00
    @loliordie 好吧,我没说清楚,我们同时间可能会有多个这种去重的任务。
    way2explore2
        6
    way2explore2  
       2020-11-10 15:05:31 +08:00   ❤️ 1
    @loliordie 正解,2g 直接内存
    GM
        7
    GM  
       2020-11-10 15:06:15 +08:00
    直接 sort -u,磁盘速度够的话,一分钟完事
    icyalala
        8
    icyalala  
       2020-11-10 15:06:30 +08:00   ❤️ 3
    2G 直接哈希表都能搞定,甚至直接 awk 一行命令:
    awk '!a[$0]++' input.txt > output.txt
    t6attack
        9
    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
        10
    loliordie  
       2020-11-10 15:13:18 +08:00 via Android   ❤️ 1
    @sl19981007 取决于你的 tradeoff 是空间复杂度优先还是时间复杂度优先

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

    更简单一点可以输入多个路径 挨个处理 连多线程库都不用上 就是同时只能有一个任务正在运行 但你这个需求 最大瓶颈在于硬盘 io 所以多个并行或者串行影响都不大
    mengzhuo
        11
    mengzhuo  
       2020-11-10 15:14:04 +08:00   ❤️ 1
    才 2G,直接上哈希表干就完了

    一堆超大文件倒是可以试试我的 nabhash
    http://nabhash.org/
    aladdindingding
        12
    aladdindingding  
       2020-11-10 15:54:01 +08:00
    linux 命令就行 sort | unique
    MOONLIGHTT
        13
    MOONLIGHTT  
       2020-11-10 16:44:18 +08:00
    别自己写,用 linux 的内建命令
    knightdf
        14
    knightdf  
       2020-11-10 17:14:29 +08:00
    2G 而已,sort 都挺快的
    hotpot6147
        15
    hotpot6147  
       2020-11-10 17:33:26 +08:00
    2g 的文本直接 load 进内存,然后 hash 去重就可以了。

    如果 pc 机内存不够可以对每行数据进行 hash 后取模分布在 n 个文件中,然后再将这 n 个文件分别 load 进内存去重
    BBCCBB
        16
    BBCCBB  
       2020-11-10 17:35:11 +08:00
    我感觉这种都是先遍历, 按文本 hash 拆分成足够小的文件, 然后在内存足够的情况下去处理每个小文件, 最后 merge 起来就完成了你说的需求了..


    一般都是按 hash 拆分, 然后处理每个小文件, 最后再合并.
    BBCCBB
        17
    BBCCBB  
       2020-11-10 17:35:44 +08:00
    不过这是针对超大文件的, 你这个 2G 真的可以试试直接 load 到内存.
    Xusually
        18
    Xusually  
       2020-11-10 17:37:15 +08:00
    我开个脑洞,存数据库里。单行内容做主键,不停按行 insert,emmm......
    gainsurier
        19
    gainsurier  
       2020-11-10 17:38:02 +08:00
    emeditor,十几秒搞定
    aec4d
        20
    aec4d  
       2020-11-10 18:11:08 +08:00
    瓶颈是磁盘 IO, 针对选一个 hash https://github.com/rust-lang/hashbrown,按行读取,如果 hash 值已存在则跳过,猜测十秒能完成吧
    janxin
        21
    janxin  
       2020-11-10 18:43:52 +08:00
    这数据量直接 load 到内存里怎么玩都行
    NCE
        22
    NCE  
       2020-11-10 19:54:15 +08:00
    这应该是个面试题
    winglight2016
        23
    winglight2016  
       2020-11-10 20:08:26 +08:00
    @NCE 的确,我在金山面试 android 时有被问过类似问题
    nowgoo
        24
    nowgoo  
       2020-11-10 20:47:44 +08:00
    linux 环境 sort/awk,windows 环境 editplus/emeditor
    rainfd
        25
    rainfd  
       2020-11-10 21:37:16 +08:00
    sort | unique
    m30102
        26
    m30102  
       2020-11-10 23:11:25 +08:00
    LinekdHashSet 行不?
    Mohanson
        27
    Mohanson  
       2020-11-10 23:39:52 +08:00
    任意"去重"或"排序"的面试题答"字典树"绝对得分的.
    fewok
        28
    fewok  
       2020-11-11 00:20:34 +08:00
    @loliordie o(n)复杂度 怕是搞不定吧
    loliordie
        29
    loliordie  
       2020-11-11 05:13:36 +08:00 via Android
    @fewok 为何搞不定 不就是 n 次查哈希表的操作么?
    mogami18
        30
    mogami18  
       2020-11-11 06:06:52 +08:00
    我還以為是 2T
    oneoyn
        31
    oneoyn  
       2020-11-11 09:15:40 +08:00 via Android
    2G 我的 cpu 可以秒开
    fewok
        32
    fewok  
       2020-11-11 10:08:54 +08:00
    @loliordie 建哈希表 或者查哈希表 就不算复杂度嘛?
    newmlp
        33
    newmlp  
       2020-11-11 10:43:22 +08:00
    2g 而已,全部读到内存就完事了
    vincent7245
        34
    vincent7245  
       2020-11-11 11:47:25 +08:00
    所以你为什么不用 spark 呢 /狗头
    loliordie
        35
    loliordie  
       2020-11-11 12:44:50 +08:00
    @fewok 你可能需要理解下 O(n)复杂度的意义, 大 O 计算法考察的是时间规模跟输入规模的关系, 哈希表复杂度为 O(1), 不会影响时间复杂度, 除非你使用了 listnode 这样的结构, 每次查询元素时都会迭代, 随着输入规模的增加查询时间也会增加这样才会导致复杂度从 O(n)变为 O(n^2)
    hxy100
        36
    hxy100  
       2020-11-11 20:57:52 +08:00
    Linux 直接上 sort 或者 uniq 命令即可,Windows 下的话直接 Emeditor 打开,点一下去重按钮就完事。
    关于   ·   帮助文档   ·   API   ·   FAQ   ·   我们的愿景   ·   广告投放   ·   感谢   ·   实用小工具   ·   2320 人在线   最高记录 5497   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 44ms · UTC 14:18 · PVG 22:18 · LAX 07:18 · JFK 10:18
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.