V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
推荐学习书目
Learn Python the Hard Way
Python Sites
PyPI - Python Package Index
http://diveintopython.org/toc/index.html
Pocoo
值得关注的项目
PyPy
Celery
Jinja2
Read the Docs
gevent
pyenv
virtualenv
Stackless Python
Beautiful Soup
结巴中文分词
Green Unicorn
Sentry
Shovel
Pyflakes
pytest
Python 编程
pep8 Checker
Styles
PEP 8
Google Python Style Guide
Code Style from The Hitchhiker's Guide
cdwyd
V2EX  ›  Python

分享大量数据去重的方法,顺便问下 python 内存占用问题

  •  1
     
  •   cdwyd · 2016-04-18 22:01:48 +08:00 · 14360 次点击
    这是一个创建于 2900 天前的主题,其中的信息可能已经有所发展或是发生改变。

    单个文本文件,大小 11G ,数据总量 6000 万左右,去重后约 4000 万,去重的依据是 md5 值列。

    首先尝试的方法是:建立 md5 的唯一索引, load data infile 语句导入,跑了一个晚上没跑完。 后来取 md5 的前三位进行判断,把不重复的数据写到新的文本文件,去掉唯一索引,再次用 load data infile 语句导入,共计( 10 + 8 = 18 分钟)。

    代码大致如下,问题是,这段代码运行后会把 6G 内存全部用完(系统 1G , python 占用 5G ),想问下怎么会占用这么多内存?

    import time
    
    start_time = time.time()
    lines = []
    
    
    md5s = {}
    for x in 'abcdef1234567890':
        for y in 'abcdef1234567890':
            for z in 'abcdef1234567890':
                md5s[x + y + z] = set()
    
    with open('files.txt', 'r', encoding = 'utf-8') as f:
        for i, line in enumerate(f):
            try:
                if i % 10000 == 0:
                    print(i)
                md5 = line.split('|')[3]
                key = md5[:3]
                if md5 not in md5s[key]:
                    md5s[key].add(md5)
                    lines.append(line)
                    if len(lines) > 10000:
                        with open('new.txt', 'a', encoding = 'utf-8') as f:
                            f.write(''.join(lines))
                        lines = []
            except Exception as e:
                print(e)
                print(line)
    
    with open('new.txt', 'a', encoding = 'utf-8') as f:
        f.write(''.join(lines))
    lines = []
    
    print((time.time() - start_time) / 60)
    
    第 1 条附言  ·  2016-04-19 08:02:18 +08:00
    统一感谢大家的回复,另外可能我没描述清楚,要去重的文本文件是一个多字段的 csv 文件,其中 md5 字段作为去重依据。
    第 2 条附言  ·  2016-04-19 08:41:00 +08:00
    @binux 已经测试 md5 分组没有意义, x in set 是 O(1),不分组速度更快 7 分钟左右,内存占用也少一些,代码就不再贴了去掉分组相关的部分就可以。
    看来是该好好补补数据结构了。
    34 条回复    2016-04-20 21:43:29 +08:00
    loading
        1
    loading  
       2016-04-18 22:12:54 +08:00   ❤️ 1
    使用 SQLite 内存模式比你使用 txt 快很多,而且数据库去重很方便。
    decaywood
        2
    decaywood  
       2016-04-18 22:30:04 +08:00   ❤️ 1
    如果要自己造轮子,一般解决方案是 hash 取余到多个文件,分别去重然后进行归并,这样就不存在内存耗尽问题了
    binux
        3
    binux  
       2016-04-18 23:21:45 +08:00
    缓存 lines 的意义何在?
    把 md5 分组意义何在? x in set 是 O(1) 的
    sicklife
        4
    sicklife  
       2016-04-18 23:29:08 +08:00   ❤️ 1
    redis
    yzongyue
        5
    yzongyue  
       2016-04-18 23:31:58 +08:00   ❤️ 1
    md5s = {} 这个字典会越来越大, 这个问题要不要试试 hadoop ?
    SlipStupig
        6
    SlipStupig  
       2016-04-18 23:40:00 +08:00
    费这个力气干嘛,有更简单解决访问方案啊!
    with open('ufiles.txt', 'r') as f:
    with contextlib.closing(mmap.mmap(f.fileno(), 0, access=mmap.ACCESS_READ)as m:
    with open(‘ object.txt ’, 'wb') as new_file:
    new_file.wirtelines(list(set(list)))
    glasslion
        7
    glasslion  
       2016-04-19 00:13:36 +08:00
    md5 做 hash 有何意义? 第一个版本一个晚上没跑完,第二个版本 md5 前三位 只用了 18 分钟是否说明第一个的瓶颈是在 算 md5 上? string 直接塞 set 不行吗?
    Gn
        8
    Gn  
       2016-04-19 00:20:44 +08:00   ❤️ 1
    4000 万条 md5 ,最少需要 32*4000*10^4/10^9 = 1.28 GB
    python 的 set 是 hash set ,虽然估计是动态的,但你分了 4000 个,空洞肯定少不了,用完 5 GB 内存应该不难吧。

    其实我的话就直接外部排序,归并的时候顺便去重,不算太慢。 hash 查重的话短了容易冲突,长了算得太慢。 string 直接放 set 里内存不够吧。
    zqhong
        9
    zqhong  
       2016-04-19 00:30:54 +08:00   ❤️ 1
    直接用 Linux 命令解决就好了

    $ wc -l testfile
    352235592 testfile

    $ sort.exe -u testfile

    跑了三分钟,占用内存 1G 多。 CPU 是 i5-4200U ,内存为 8G DDR3 1600 。
    kslr
        10
    kslr  
       2016-04-19 01:22:57 +08:00 via Android
    布隆过滤器
    9hills
        11
    9hills  
       2016-04-19 02:54:03 +08:00 via iPad   ❤️ 1
    awk 一行搞定,而且很快,。。。
    cdwyd
        12
    cdwyd  
    OP
       2016-04-19 08:05:05 +08:00
    @binux
    缓存 lines 是为了减少文件打开关闭次数,一定数量后统一写入。
    不知道 in set 是 O(1) 的,感谢指出,我去试试不分组的速度。
    cdwyd
        13
    cdwyd  
    OP
       2016-04-19 08:06:39 +08:00
    @glasslion
    可能是我描述不清楚导致了误会, md5 是其中的一个字段,作为去重依据。分组的问题是我之前不清楚 x in set 是 O(1) 的,想着分组能快一些。
    cdwyd
        14
    cdwyd  
    OP
       2016-04-19 08:10:11 +08:00
    @Gn
    感谢解释了内存占用问题。是我的描述不清楚,这是个 csv 文件, md5 字段是已经存在的,用它来去重,并没有把整行的 str 放到 set ,只放了完整的 md5.
    cdwyd
        15
    cdwyd  
    OP
       2016-04-19 08:12:18 +08:00
    @zqhong
    @9hills
    详细说下
    cdwyd
        16
    cdwyd  
    OP
       2016-04-19 08:13:05 +08:00
    @SlipStupig
    没看懂这个,去找找资料
    crowds
        17
    crowds  
       2016-04-19 08:27:27 +08:00 via Android
    @9hills 已笑哭。。。
    其实 sort+uniq 就可以了吧
    Zzzzzzzzz
        18
    Zzzzzzzzz  
       2016-04-19 08:39:11 +08:00
    pandas 有现成的 drop_duplicates
    nevin47
        19
    nevin47  
       2016-04-19 08:54:43 +08:00
    虽然有很多轮子用了, LZ 自己这个轮子也挺有意思的。我觉得应该是 md5s = {}这个字典占用太大了吧

    另外这种数据随便一个数据库就能解决的,搞文本确实有点得不偿失
    Gn
        20
    Gn  
       2016-04-19 09:35:22 +08:00
    @cdwyd 恩,我说 string 直接放 set 里是回复楼上的,算的是 md5 的占用。
    ytmsdy
        21
    ytmsdy  
       2016-04-19 10:10:38 +08:00
    先把这 11G 的文本导入到数据库,然后再在数据库里面做去重复的操作。你这么一边插入,一边查询效率很低的。
    SlipStupig
        22
    SlipStupig  
       2016-04-19 10:48:06 +08:00
    @cdwyd mmap 读取文件,然后用 set 去重, mmap 申请的不是 buff 而是内存分页,只要你是 64 位系统就能突破限制
    hitmanx
        23
    hitmanx  
       2016-04-19 10:50:17 +08:00
    @decaywood 没太明白,请问具体怎么操作,比如归并时是否排序呢?如果排序就要 O(nlgn)( lz 的方法只要 O(n));如果不排序,最后归并的时候依然是 2 个或多个大文件,依然很占内存。
    hitmanx
        24
    hitmanx  
       2016-04-19 11:18:16 +08:00
    @decaywood 请忽略上一条信息= =,明白你的意思了~~
    hwsdien
        25
    hwsdien  
       2016-04-19 11:47:59 +08:00
    我们用 Hadoop 每天对 200G 的文件去重
    0xccff
        26
    0xccff  
       2016-04-19 13:21:28 +08:00
    我去过重,之前有个 1200 万条 url ,感觉个人电脑如果不用算法,直接比较的话,太费时了,后来就用了布隆过滤器,不过有误伤的,但通过参数可以控制,对内存的占用还好。
    necomancer
        27
    necomancer  
       2016-04-19 13:30:29 +08:00
    要不要去看看神器 sort 和 uniq 的代码?楼主看明白了求带^_^
    mathgl
        28
    mathgl  
       2016-04-19 13:45:22 +08:00
    sqlite
    hicdn
        29
    hicdn  
       2016-04-19 14:11:40 +08:00
    awk -F'|' '!a[$4]++' files.txt > new.txt
    6david9
        30
    6david9  
       2016-04-19 17:17:38 +08:00
    布隆过滤器?
    neoblackcap
        31
    neoblackcap  
       2016-04-19 23:16:11 +08:00
    去重首先想到 Bloom Filter,
    当然 6000 万的数据,我觉得用个数据库也可以简单解决,最多就是时间长一些。
    ksupertu
        32
    ksupertu  
       2016-04-20 02:29:50 +08:00
    kettle 、 pandas 都有去重模块,还支持几乎所有数据格式及数据库连接,做一个愉快的调包侠就行了啊,自己写的效率肯定没人做量化的人写出来的效率高
    KIDJourney
        33
    KIDJourney  
       2016-04-20 20:38:33 +08:00
    为何要用 md5 ?
    cdwyd
        34
    cdwyd  
    OP
       2016-04-20 21:43:29 +08:00 via Android
    @KIDJourney
    md5 是已存在的列
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   3189 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 38ms · UTC 12:18 · PVG 20:18 · LAX 05:18 · JFK 08:18
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.