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

大文本超快去重工具

  •  
  •   firebroo ·
    firebroo · 2018-07-28 22:40:37 +08:00 · 5488 次点击
    这是一个创建于 2292 天前的主题,其中的信息可能已经有所发展或是发生改变。

    简介

    地址 https://github.com/firebroo/UnixTools/tree/master/uniq

    可能有造轮子的嫌疑,去重思想就是借鉴的 awk '!a[$0]++{print}',但是极端情况还是有用的,自己测试当文本超大的时候,速度上可以比 awk 高两倍左右,时间在一个量级内当然这不是特别有用的,但是内存差不多也可以节约二倍左右,个人感觉这还是非常有用的,毕竟内存还是毕竟宝贵的,各位顺便看看还有没有可以优化的余地?

    优点

    • 根据需求精简了 hashtable 里的 hash 节点的结构体,hash 节点里面只保存 key 和为了解决 hash 冲突的指针,节约内存;
    • 根据文本行数调整 hashtable.h 的 HASH_TABLE_MAX_SIZE,减少 rehash 次数,有利于加快去重速度;
    第 1 条附言  ·  2018-07-28 23:33:22 +08:00
    把 key 用指针的方式改为了可变长数组,内存比之前可节约文本行数*8 个字节。
    第 2 条附言  ·  2018-07-29 13:51:00 +08:00
    目前 9 千万行 2.7G 完全不重复的数据,去重所需内存 5.2G 左右,而使用 awk 则需要 20G+的内存占用。
    第 3 条附言  ·  2018-07-30 19:40:03 +08:00
    看了下 lua 的内核实现,又加了个 dev 分支,闭散列法解决 hash 碰撞,hashnode 里面使用 int 代替了指针,目前测试来看控制合理,两者内存的使用率差不多。
    10 条回复    2018-07-30 17:57:11 +08:00
    swulling
        1
    swulling  
       2018-07-28 23:03:11 +08:00 via iPad
    awk 的 hash 表内存占用有点高,支持。
    easylee
        2
    easylee  
       2018-07-28 23:12:00 +08:00
    牛,赞一个。
    lihongjie0209
        3
    lihongjie0209  
       2018-07-30 08:53:18 +08:00
    发一个测试文件出来看看
    firebroo
        4
    firebroo  
    OP
       2018-07-30 09:49:27 +08:00
    @lihongjie0209

    ```python
    import random

    def random_str(len):
    seed = "1234567890abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ!@#$%^&*()_+=-"
    ret = ""
    for i in range(20):
    ret += random.choice(seed)
    return ret

    with open("2.log", "w") as f:
    for i in xrange(80000000):
    line = random_str(30) + "\n"
    f.write(line)
    ```

    用 python 生成一个随机文件测试。
    engineer9
        5
    engineer9  
       2018-07-30 10:15:43 +08:00
    用了多长时间呀? 9000 万行
    firebroo
        6
    firebroo  
    OP
       2018-07-30 10:36:03 +08:00
    @engineer9 按照 4#生成的 8 千万行随机数据,我的 Thinkpad i5 上面 1 分 50 秒。
    lihongjie0209
        7
    lihongjie0209  
       2018-07-30 15:17:00 +08:00
    ```
    from datetime import datetime

    print("{} start".format(datetime.now()))

    with open("3.log", "r") as f:
    lines = f.readlines()

    print("{} before: {} line".format(datetime.now(), len(lines)))

    set_lines = set(lines)
    print("{} after: {} line".format(datetime.now(), len(set_lines)))


    ```

    输出:
    ```
    2018-07-30 14:43:24.128476 start
    2018-07-30 14:43:47.338141 before: 80000000 line
    2018-07-30 14:44:04.591483 after: 80000000 line
    ```

    机器配置: I7, 32G, 固态硬盘, 占用内存 8G



    分析:


    ```
    2018-07-30 14:43:24.128476 start
    2018-07-30 14:43:47.338141 before: 80000000 line

    读取文件耗时 23s

    2018-07-30 14:43:47.338141 before: 80000000 line
    2018-07-30 14:44:04.591483 after: 80000000 line

    去重耗时 17s

    ```


    去重这种事情文件越大, IO 的影响越重. 按照你的生成算法,生成的文件有 1.6G, 这么大的文件全部读取本身就很费时间, 在机械硬盘下这种现象更加明显, 文件大, 文件读取的所占的比重越大.

    所以对于这种优化希望还是先 profile 再优化, 楼主能手写 hashtable 我是很佩服了.
    firebroo
        8
    firebroo  
    OP
       2018-07-30 17:38:44 +08:00 via Android
    @lihongjie0209 我说了时间在一个量级意义不大,主要还是内存使用上面。
    s1ma
        9
    s1ma  
       2018-07-30 17:42:10 +08:00
    有点溜
    Sfan
        10
    Sfan  
       2018-07-30 17:57:11 +08:00
    确实有点溜
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   1249 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 23ms · UTC 23:15 · PVG 07:15 · LAX 15:15 · JFK 18:15
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.