求 a 与 b 的差集,内存限制 1G
# 500w
a = [...]
# 5000w
b = [...]
# 记录为 10 - 100 不等字符串
不知是不是关键词不对,搜索到的方案都是 set、numpy,或 set(b) 遍历 a,内存实在扛不住啊
求指点,速度慢些也可以接受
感谢各位大佬指点,放上解决方案方便后来同学
shell 版
sort -u -o a.txt a.txt
sort -u -o b.txt b.txt
comm -23 a.txt b.txt > results.txt
先排序,后求差集
python sqlite 版
import sqlite3
conn = sqlite3.connect('test.db')
c = conn.cursor()
c.execute('CREATE TABLE IF NOT EXISTS a (v TEXT)')
c.execute('CREATE TABLE IF NOT EXISTS b (v TEXT)')
with open(r'a.txt', 'r') as f_in:
for n, i in enumerate(f_in):
c.execute('INSERT INTO a VALUES (?)', (i.strip(), ))
with open(r'b.txt', 'r') as f_in:
for n, i in enumerate(f_in):
c.execute('INSERT INTO b VALUES (?)', (i.strip(), ))
c.execute('CREATE INDEX bv ON b(v)')
c.execute('SELECT v FROM a WHERE v NOT IN (SELECT v FROM b)')
for i in c:
print(i)
感谢 @CRVV 大佬的代码
1
kristingna 2017-10-27 20:57:25 +08:00
你可以试试 Spark
|
2
yuyang 2017-10-27 21:01:51 +08:00 via Android
先外部排序,然后比较
|
3
qwertyegg 2017-10-27 21:28:31 +08:00
100 个 char 的 String 占内存 240byte,最大占用 240 byte * 50M = 1200MB,你的记录只要不是极端的情况下,1GB 内存轻松放进去呀
|
6
buliugu 2017-10-27 21:37:03 +08:00 1
bitmap
|
7
Xs0ul 2017-10-27 21:39:20 +08:00
把 a b 都按首字母拆开成一堆小文件,a b 每对首字母相同的做差,再把结果合并起来。
|
8
geelaw 2017-10-27 21:49:24 +08:00
似乎光是 a、b 本身的大小已经远远超过 1GB 了。
你是希望附加空间在 1GB 之内吗? |
9
neosfung 2017-10-27 21:55:47 +08:00 via iPhone
Trie 树
|
10
owenliang 2017-10-27 22:34:17 +08:00 1
1,数据集本身就大于内存,所以数据集肯定在磁盘。
2,内存无法排序所有数据,所以必须外排序。 3,一旦 2 个文件有序,那么就可以 2 路归并。 |
11
CRVV 2017-10-27 23:44:38 +08:00 1
大概试了一下,在我的机器上,含生成随机数据一共大约 400 秒,其中建索引 80 秒,查询 60 秒。
内存占用不超过 20 M,数据库文件 6.4 G import sqlite3 import string import random conn = sqlite3.connect('test.db') c = conn.cursor() c.execute('CREATE TABLE IF NOT EXISTS a (v TEXT)') c.execute('CREATE TABLE IF NOT EXISTS b (v TEXT)') letters = string.ascii_letters + string.digits for _ in range(5_000_000): ____random_string = ''.join((random.choice(letters) for _ in range(random.randint(10, 100)))) ____c.execute('INSERT INTO a VALUES (?)', (random_string, )) for _ in range(50_000_000 // 4_500_000): ____c.execute('INSERT INTO b SELECT * FROM a LIMIT 4500000') c.execute('CREATE INDEX bv ON b(v)') c.execute('SELECT v FROM a WHERE v NOT IN (SELECT v FROM b)') count = 0 for _ in c: ____count += 1 print(count) conn.commit() conn.close() |
12
NoAnyLove 2017-10-28 01:47:36 +08:00
如果记录的长度比较均匀的话,那么按照长度分组之后再来做运算不知道内存够不够
|
13
swulling 2017-10-28 01:49:45 +08:00 via iPhone
内存够用 hash 表,比如 b 减 a,就用 hash 表
内存不够,比如 a 减 b,那就用 B 树 |
14
kaneg 2017-10-28 09:19:04 +08:00 via iPhone
把小份数据读到内存,大的在文件中逐条读,求二者的交集,结果必然不大于之前的记录,然后分别求之前两份原始数据的差集,最后合并两份差集即可。
|
15
clino 2017-10-28 10:41:10 +08:00 via Android
我也和楼上一样想用 sqlite
|
16
herozhang 2017-10-28 11:24:12 +08:00 via iPhone
把 swap 分区设大一点,就可以了,哈哈哈
|
17
clino 2017-10-28 16:42:37 +08:00
楼主能不能说下 shell 和 python sqlite 版运行时间分别是多少?
|
18
zhicheng 2017-10-28 16:58:36 +08:00
如果不是完全随机数,可以压缩一下。只要能把小的那个塞进内存就行了。
|
19
ioven OP @clino 用测试数据来看,sqlite 大概是 shell 两倍时间、空间占用,但 sqlite 处理更加灵活,这点差距完全可以接受
|
20
stanjia 2017-10-29 16:24:58 +08:00
省心法本机安个 hadoop
|
23
shamashii 2017-11-21 22:36:24 +08:00
生成 110s,比较 120s,实验时感觉坑点竟然在于生成随机字符串效率,求改进
``` import timeit def main(): import h5py, cyrandom allchr = "".join((chr(i) for i in range(33,127))) pspool = [[cyrandom.choice(allchr) for _ in range(cyrandom.randint(10, 100))] for x in range(100000)] chunkl = [] for _ in range(5000000): b1 = cyrandom.choice(pspool) cyrandom.shuffle(b1) chunkl.append(''.join(b1).encode('utf-8')) f = h5py.File('h5.h5','w') for k in range(50000000//5000000): l = [str(k).encode('utf-8')] # cyrandom.shuffle(chunkl) print(k) f.create_dataset(str(k), data=chunkl+l,) del chunkl f.close() def query(): import h5py f = h5py.File('h5.h5','a') wbw = set(f['0'].value) count = [] for k in f.keys(): print(k) for x in f[k].value: if x not in wbw: count.append(x) print(count) f.close() print(timeit.timeit(main, number=1)) print(timeit.timeit(query, number=1)) ``` |
24
shamashii 2017-11-21 22:42:24 +08:00
|