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

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

这是一个创建于 2588 天前的主题，其中的信息可能已经有所发展或是发生改变。

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

# 500w
a = [...] 

# 5000w
b = [...]

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

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

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

第 1 条附言 · 2017-10-28 10:43:41 +08:00

感谢各位大佬指点，放上解决方案方便后来同学

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 大佬的代码

差集

set

内存

遍历

24 条回复 • 2017-11-21 22:42:24 +08:00

kristingna

2017-10-27 20:57:25 +08:00

你可以试试 Spark

yuyang

2017-10-27 21:01:51 +08:00 via Android

先外部排序，然后比较

qwertyegg

2017-10-27 21:28:31 +08:00

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

qwertyegg

2017-10-27 21:29:14 +08:00

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

qwertyegg

2017-10-27 21:30:58 +08:00

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

buliugu

2017-10-27 21:37:03 +08:00

bitmap

Xs0ul

2017-10-27 21:39:20 +08:00

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

geelaw

2017-10-27 21:49:24 +08:00

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

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

neosfung

2017-10-27 21:55:47 +08:00 via iPhone

Trie 树

owenliang

2017-10-27 22:34:17 +08:00

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

CRVV

2017-10-27 23:44:38 +08:00

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

2017-10-28 01:47:36 +08:00

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

swulling

2017-10-28 01:49:45 +08:00 via iPhone

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

kaneg

2017-10-28 09:19:04 +08:00 via iPhone

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

clino

2017-10-28 10:41:10 +08:00 via Android

我也和楼上一样想用 sqlite

herozhang

2017-10-28 11:24:12 +08:00 via iPhone

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

clino

2017-10-28 16:42:37 +08:00

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

zhicheng

2017-10-28 16:58:36 +08:00

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

ioven

2017-10-28 17:40:08 +08:00

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

stanjia

2017-10-29 16:24:58 +08:00

省心法本机安个 hadoop

clino

2017-10-30 10:28:02 +08:00

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

ioven

2017-10-30 21:50:37 +08:00

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

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

shamashii

2017-11-21 22:42:24 +08:00

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