
单个文本文件,大小 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 loading 2016-04-18 22:12:54 +08:00 使用 SQLite 内存模式比你使用 txt 快很多,而且数据库去重很方便。 |
2 decaywood 如果要自己造轮子,一般解决方案是 hash 取余到多个文件,分别去重然后进行归并,这样就不存在内存耗尽问题了 |
3 binux 2016-04-18 23:21:45 +08:00 缓存 lines 的意义何在? 把 md5 分组意义何在? x in set 是 O(1) 的 |
4 sicklife 2016-04-18 23:29:08 +08:00 redis |
5 yzongyue 2016-04-18 23:31:58 +08:00 md5s = {} 这个字典会越来越大, 这个问题要不要试试 hadoop ? |
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))) |
7 glasslion 2016-04-19 00:13:36 +08:00 md5 做 hash 有何意义? 第一个版本一个晚上没跑完,第二个版本 md5 前三位 只用了 18 分钟是否说明第一个的瓶颈是在 算 md5 上? string 直接塞 set 不行吗? |
8 Gn 2016-04-19 00:20:44 +08:00 4000 万条 md5 ,最少需要 32*4000*10^4/10^9 = 1.28 GB python 的 set 是 hash set ,虽然估计是动态的,但你分了 4000 个,空洞肯定少不了,用完 5 GB 内存应该不难吧。 其实我的话就直接外部排序,归并的时候顺便去重,不算太慢。 hash 查重的话短了容易冲突,长了算得太慢。 string 直接放 set 里内存不够吧。 |
9 cha1 2016-04-19 00:30:54 +08:00 直接用 Linux 命令解决就好了 $ wc -l testfile 352235592 testfile $ sort.exe -u testfile 跑了三分钟,占用内存 1G 多。 CPU 是 i5-4200U ,内存为 8G DDR3 1600 。 |
10 kslr 2016-04-19 01:22:57 +08:00 via Android 布隆过滤器 |
11 9hills 2016-04-19 02:54:03 +08:00 via iPad awk 一行搞定,而且很快,。。。 |
12 cdwyd OP |
13 cdwyd OP @glasslion 可能是我描述不清楚导致了误会, md5 是其中的一个字段,作为去重依据。分组的问题是我之前不清楚 x in set 是 O(1) 的,想着分组能快一些。 |
14 cdwyd OP @Gn 感谢解释了内存占用问题。是我的描述不清楚,这是个 csv 文件, md5 字段是已经存在的,用它来去重,并没有把整行的 str 放到 set ,只放了完整的 md5. |
16 cwyd OP @SlipStupig 没看懂这个,去找找资料 |
18 Zzzzzzzzz 2016-04-19 08:39:11 +08:00 pandas 有现成的 drop_duplicates |
19 nevin47 2016-04-19 08:54:43 +08:00 虽然有很多轮子用了, LZ 自己这个轮子也挺有意思的。我觉得应该是 md5s = {}这个字典占用太大了吧 另外这种数据随便一个数据库就能解决的,搞文本确实有点得不偿失 |
21 ytmsdy 2016-04-19 10:10:38 +08:00 先把这 11G 的文本导入到数据库,然后再在数据库里面做去重复的操作。你这么一边插入,一边查询效率很低的。 |
22 SlipStupig 2016-04-19 10:48:06 +08:00 @cdwyd mmap 读取文件,然后用 set 去重, mmap 申请的不是 buff 而是内存分页,只要你是 64 位系统就能突破限制 |
23 hitmanx 2016-04-19 10:50:17 +08:00 @decaywood 没太明白,请问具体怎么操作,比如归并时是否排序呢?如果排序就要 O(nlgn)( lz 的方法只要 O(n));如果不排序,最后归并的时候依然是 2 个或多个大文件,依然很占内存。 |
25 hwsdien 2016-04-19 11:47:59 +08:00 我们用 Hadoop 每天对 200G 的文件去重 |
26 0xccff 2016-04-19 13:21:28 +08:00 我去过重,之前有个 1200 万条 url ,感觉个人电脑如果不用算法,直接比较的话,太费时了,后来就用了布隆过滤器,不过有误伤的,但通过参数可以控制,对内存的占用还好。 |
27 necomancer 2016-04-19 13:30:29 +08:00 要不要去看看神器 sort 和 uniq 的代码?楼主看明白了求带^_^ |
28 mathgl 2016-04-19 13:45:22 +08:00 sqlite |
29 hicdn 2016-04-19 14:11:40 +08:00 awk -F'|' '!a[$4]++' files.txt > new.txt |
30 6david9 2016-04-19 17:17:38 +08:00 布隆过滤器? |
31 neoblackcap 2016-04-19 23:16:11 +08:00 去重首先想到 Bloom Filter, 当然 6000 万的数据,我觉得用个数据库也可以简单解决,最多就是时间长一些。 |
32 ksupertu 2016-04-20 02:29:50 +08:00 kettle 、 pandas 都有去重模块,还支持几乎所有数据格式及数据库连接,做一个愉快的调包侠就行了啊,自己写的效率肯定没人做量化的人写出来的效率高 |
33 KIDJourney 2016-04-20 20:38:33 +08:00 为何要用 md5 ? |
34 cdwyd OP @KIDJourney md5 是已存在的列 |