如何使用 python 有效地找到两个大文件的交集？

Question

我有两个大文件。它们的内容如下所示：

134430513
125296589
151963957
125296589

该文件包含未排序的 id 列表。某些 id 可能会在单个文件中出现多次。

现在我想找到两个文件的交集部分。这就是两个文件中都出现的 id。

我只是将这两个文件读入 2 组，s1 和 s2。并通过 s1.intersection(s2) 获取交集。但它消耗大量内存并且看起来很慢。

那么有没有更好的或Python式的方法来做到这一点？如果文件包含太多 id，无法读取到内存有限的 set 中，我该怎么办？

编辑：我使用生成器将文件读入 2 组：

def id_gen(path):
    for line in open(path):
        tmp = line.split()
        yield int(tmp[0])

c1 = id_gen(path)
s1 = set(c1)

所有 id 都是数字。最大id可能是5000000000。如果使用bitarray，会消耗更多内存。

Answer 1

其他人已经展示了更惯用的方法
Python，但如果数据量确实太大，可以
使用系统实用程序排序并消除重复项，然后
使用 File 是一个返回一行的迭代器这一事实
一次，执行如下操作：

import os
os.system('sort -u -n s1.num > s1.ns')
os.system('sort -u -n s2.num > s2.ns')
i1 = open('s1.ns', 'r')
i2 = open('s2.ns', 'r')
try:
    d1 = i1.next()
    d2 = i2.next()
    while True:
        if (d1 < d2):
            d1 = i1.next()
        elif (d2 < d1):
            d2 = i2.next()
        else:
            print d1,
            d1 = i1.next()
            d2 = i2.next()
except StopIteration:
    pass

这可以避免一次有多于一行（对于每个文件）
在内存中（并且系统排序应该比任何东西都快）
Python 可以做到，因为它针对这一任务进行了优化）。

Answer 2

set(open(file1)) & set(open(file2))

这相当于使用intersection，是最Pythonic的方式。 您也许可以通过这样做来加快速度

set(int(x) for x in open(file1)) & set(int(x) for x in open(file2))

从那时起，您将存储和比较整数而不是字符串， 。当然，只有当所有 id 都是数字时，这才有效。

如果仍然不够快，您可以转向稍微更命令式的风格：

# heuristic: set smaller_file and larger_file by checking the file size
a = set(int(x) for x in open(smaller_file))
# note: we're storing strings in r
r = set(x for x in open(larger_file) if int(x) in a)

如果保证两个文件不包含重复项，您还可以使用列表来加快速度：

a = set(int(x) for x in open(smaller_file))
r = [x for x in open(larger_file) if int(x) in a]

一定要衡量各种解决方案，并检查您是否'实际上并不等待磁盘或网络输入。

Answer 3

因此，该算法不一定与 python 相关，而是通用的（如果您无法表示内存中集合中的所有 id）。如果整数的范围有限，一种方法是使用大的位数组。现在，您读取第一个文件并将 bitarray 中的整数设置为存在。
现在，您读取第二个文件，并输出 bitarray 中也存在的所有数字。

如果这还不够，您可以使用多次扫描来分割范围。即在第一遍中，您只考虑小于 0x200000000 (1GB bitarray) 的整数。
然后，您重置 bitarray 并再次读取文件，仅考虑从 0x200000000 到 0x400000000 的整数（并在之前减去 0x200000000处理整数）。

通过这种方式，您可以以合理的运行时间处理大量数据。

单次扫描的示例为：

import bitarray
r = bitarray.bitarray(5000000000)

for line in open(file1):
    r[int(line)] = True

for line in open(file2):
    if r[int(line)]:
        print line

Answer 4

据我所知，Python 没有有效的方法来做到这一点，特别是当你处理大量数据时。

我喜欢 rumpel< /a> 的解决方案。但请注意 bitarray 是 C 扩展。

我会使用 shell 命令来处理这个问题。您可以预处理文件以节省时间和space：

sort -u file1 file1.sorted
sort -u file2 file2.sorted

然后您可以使用 diff 来找出相似之处：

diff --changed-group-format='' --unchanged-group-format='%=' file1.sorted file2.sorted

当然，可以将所有内容组合到单个命令中，而无需创建中间文件。

更新

根据Can的建议，comm 是更合适的命令：

sort -u file1 file1.sorted
sort -u file2 file2.sorted
comm -12 file1.sorted file2.sorted

Answer 5

您不需要同时创建 s1 和 s2。首先从第一个文件中读取行，将每行转换为整数（节省内存），然后将其放入 s1 中。然后，对于第二个文件中的每一行，将其转换为整数，并检查该值是否在 s1 中。

这样，您就可以节省存储字符串和拥有两组字符串的内存。

Answer 6

对于大于内存的数据，您可以将数据文件分成10个文件，每个文件包含相同的最低数字。

所以s1.txt中所有以0结尾的id都将保存在s1_0.txt中。

然后使用set()求s1_0.txt和s2_0.txt、s1_1.txt和s2_1.txt的交集，...

Answer 7

我遇到了同样的错误，我有两个文件，一个为 1GB，另一个为 1.5GB，当我尝试将其存储在集合中时，出现 OutOfMemory Heap Size 错误。

因此，我根据这些文件的最后两位数字将这些文件分成 100 个小文件，因此 temp1_00 包含第一个文件的最后两位数字为 00 的 id，而 temp2_00 包含第二个文件的最后两位数字为 00 的 id ，然后我使用 set 计算所有 100 个文件的交集并将其相加。

算法
加载Set中的一个文件，然后一一遍历第二个文件内容并检查Set中的内容，如果找到则增加计数，并记住始终将小文件存储在Set中以节省内存。

进一步优化：
我正在处理的任务只需要一些近似值，因此我刚刚计算了 temp1_00 和 temp2_00 并将结果乘以 100 以获得近似结果。对于这个大型数据集，我可以承受的误差约为 0-5%。
如果您需要更准确的结果，则可以计算 10 个文件并将结果乘以 10。

统计数据：

• 实际大小（获取所有 100 个文件）： 82,595,165（313 秒） )
• 大约大小（需要 10 个文件）： 82,574,530 （ 31 秒）
• 大约大小（仅取 1 个文件）：85,892,000（5 秒）