小内存如何对两个大型列表求差集？

[ioven]

求 a 与 b 的差集，内存限制 1G

# 500w
a = [...] 

# 5000w
b = [...]

# 记录为 10 - 100 不等字符串

不知是不是关键词不对，搜索到的方案都是 set、numpy，或 set(b) 遍历 a，内存实在扛不住啊

求指点，速度慢些也可以接受

[kristingna]

你可以试试 Spark

[yuyang]

先外部排序，然后比较

[qwertyegg]

100 个 char 的 String 占内存 240byte,最大占用 240 byte * 50M = 1200MB，你的记录只要不是极端的情况下,1GB 内存轻松放进去呀

[qwertyegg]

@qwertyegg 好像算错了，是 12000MB。

[qwertyegg]

@qwertyegg 那也不难，把 b 拆成 10 个，每次从 b 里面读 5M 个记录，做 10 次差集不就可以了。

[buliugu]

bitmap

[Xs0ul]

把 a b 都按首字母拆开成一堆小文件，a b 每对首字母相同的做差，再把结果合并起来。

[geelaw]

似乎光是 a、b 本身的大小已经远远超过 1GB 了。

你是希望附加空间在 1GB 之内吗？

[neosfung]

Trie 树

[owenliang]

1，数据集本身就大于内存，所以数据集肯定在磁盘。
2，内存无法排序所有数据，所以必须外排序。
3，一旦 2 个文件有序，那么就可以 2 路归并。

[CRVV]

大概试了一下，在我的机器上，含生成随机数据一共大约 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()

[NoAnyLove]

如果记录的长度比较均匀的话，那么按照长度分组之后再来做运算不知道内存够不够

[swulling]

内存够用 hash 表，比如 b 减 a，就用 hash 表
内存不够，比如 a 减 b，那就用 B 树

[kaneg]

把小份数据读到内存，大的在文件中逐条读，求二者的交集，结果必然不大于之前的记录，然后分别求之前两份原始数据的差集，最后合并两份差集即可。

[clino]

我也和楼上一样想用 sqlite

[herozhang]

把 swap 分区设大一点，就可以了，哈哈哈

[clino]

楼主能不能说下 shell 和 python sqlite 版运行时间分别是多少?

[zhicheng]

如果不是完全随机数，可以压缩一下。只要能把小的那个塞进内存就行了。

[ioven]

@clino 用测试数据来看，sqlite 大概是 shell 两倍时间、空间占用，但 sqlite 处理更加灵活，这点差距完全可以接受

[stanjia]

省心法本机安个 hadoop