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

你可以试试 Spark

先外部排序，然后比较

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

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

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

bitmap

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

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

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

Trie 树

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

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

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

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

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

我也和楼上一样想用 sqlite

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

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

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

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

省心法本机安个 hadoop

@ioven 如果 sqlite 操作都放在一个事务里面,估计时间优化得比较短

@clino 多谢提醒，默认是智能事务，试试手工开启事务看速度有没有提升

生成 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))
```

sigh``
https://pastebin.com/uDna4GK9