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

Question

我有两个大文件，它们的内容如下：

134430513 125296589 151963957 125296589

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

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

我将这两个文件读入2个集合s1和s2中，并通过s1.intersection(s2)获取交集。但这样会消耗很多内存并且似乎很慢。

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

编辑：我使用生成器将文件读入了两个集合中：

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，它会消耗更多的内存。

- amazingjxq

---

请问您能否给我们一些想法：（1）每个文件的最大条目数是多少；（2）其中所有ID都是数字。 - NPE

@aix（1）最大数字可能达到5000000000。我尝试使用位数组，但有些ID太大了。（2）所有ID都是数字。 - amazingjxq

50亿条目！那么值域呢？ - Nam Nguyen

@aix 文件中的最大条目数可能达到2000万。值域为（0，5000000000）。 - amazingjxq

很可能是生成器导致程序运行缓慢。通常情况下，在Python中做的越少，Python程序就会越快：列表推导和内置函数是用C实现的，因此它们可能快上一个数量级。 - Fred Foo

Answer 1

其他人已经展示了在Python中更为惯用的方法，但如果数据量真的太大，您可以使用系统实用程序进行排序和去重，然后利用文件是一个一次返回一行的迭代器这一事实，执行以下操作：

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的任何操作都要更快，因为它经过了针对这一任务的优化。

- James Kanze

---

使用sort -n排序和比较字符串是否有效？s1："4"，"7"，"30"；s2："4"，"8"，"30"。关于前导零（leading zeroes）呢-不是一个id吗？所有的id都是相同长度的吗？ - greybeard

使用sort -n命令和比较字符串的方式有效吗？s1: "4", "7", "30"; s2: "4", "8", "30" 那么前导零呢 - 不是一个id吗？所有的id长度都相同吗？ - undefined

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]

一定要对多种解决方案进行测量，并检查是否不是在等待磁盘或网络输入。

- Fred Foo

---

r = set(int(x) for x in open(file2) if int(x) in a) 可能也可以。不过我还没有测试过。 - Nam Nguyen

@Nam：我刚刚想到了这个，而且它有效。这样，如果文件确实包含集合，OP甚至可以使用列表。 - Fred Foo

你在结尾处漏掉了int()。 - Nam Nguyen

@Nam：谢谢。我把调用移到了 int，因为对于 r 来说它并不是必需的，我想。 - Fred Foo

Answer 3

因此，如果您无法在内存中表示所有ID，则算法不一定与Python绑定，而是通用的。如果整数范围有限，则可以使用大型bitarray的方法。现在，您可以读取第一个文件并将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

- rumpel

---

位数组和一般的位操作都不是很符合Python的风格。根据我的经验，如果我在使用Python时开始考虑位操作，那么这可能意味着我选择了错误的编程语言来解决手头的问题（或者我的方法完全不适用于该问题）。 - penelope

当然，但就效率而言，你可能无法避免。由于bitarray是一个Python对象，因此您可以像使用其他对象一样使用它。实际上，您不必关心它如何处理数据。当然，生成器和集合更符合Python的风格，但这也不错（请参见我刚添加的示例）。 - rumpel

Answer 4

据我所知，使用Python没有一种高效的方法来处理大量数据，特别是当你需要处理海量数据时。

我喜欢rumpel的解决方案。但请注意bitarray是一个C扩展库。

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

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

- muhuk

---

有一个更好的工具叫做comm。首先对两个文件进行排序，然后使用comm -12 file1 file2命令可以给出它们之间的差异。 - Can Burak Çilingir

Answer 5

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

通过这种方式，您将节省存储字符串和两个集合占用的内存。

- Nam Nguyen

Answer 6

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

因此，以0结尾的s1.txt中的所有ID将保存在s1_0.txt中。

然后使用set()查找s1_0.txt和s2_0.txt、s1_1.txt和s2_1.txt等的交集。

- HYRY

Answer 7

我遇到了相同的错误，我有两个文件，一个大约1GB，另一个大约1.5GB，当我尝试将其存储在集合中时，出现了内存溢出堆大小错误。

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

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

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

统计信息：

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

- vishal singh