在一个文件中查找不在python中另一个文件中的所有数字

Question

有两个文件，分别是FileA和FileB，我们需要找到FileA中所有的编号，而FileB中没有这些编号。FileA中的所有数字均已排序，FileB中的所有数字均已排序。例如，

输入：

FileA = [1, 2, 3, 4, 5, ...]
FileB = [1, 3, 4, 6, ...]

输出：

[2, 5, ...]

内存非常有限，甚至无法一次将一个完整的文件加载到内存中。同样需要线性或更短的时间复杂度。

因此，如果文件足够小以适合内存，我们可以加载它们并将其内容初始化为两个集合，然后取一个集合差，以便以O（1）或恒定时间复杂度解决问题。

set(contentsofFileA)-set(contentsofFileB)

但是由于文件太大，它们将无法完全加载到内存中，因此这是不可能的。

同样，另一种方法是在批处理中使用蛮力方法。因此，我们从FileA加载数据块或一批，然后从FileB加载数据块，然后比较它，然后再从FileB加载下一个数据块，依此类推。然后，在对FileB中的所有元素进行FileA块检查之后，再从FileA加载下一批，然后继续进行。但这会产生O（n ^ 2）或二次时间复杂度，对于具有大条目的超大文件而言效率不高。

需要以线性或更短的时间复杂度来解决该问题，并且不将整个文件加载到内存中。有什么帮助吗？

Answer 1

如果你想逐行读取文件行，因为你没有那么多的内存，您可以根据需要与国际热核实验堆，如果你的文件是基于线做线性解决方案，否则看这个：

首先，您可以在终端中执行此操作以生成一些测试文件：

seq 0 3 100 > 3k.txt
seq 0 2 100 > 2k.txt

然后运行以下代码：

i1 = iter(open("3k.txt"))
i2 = iter(open("2k.txt"))
a = int(next(i1))
b = int(next(i2))
aNotB = []
# bNotA = []
while True:
    try:
        if a < b:
            aNotB += [a]
            a = int(next(i1, None))
        elif a > b:
            # bNotA += [a]
            b = int(next(i2, None))
        elif a == b:
            a = int(next(i1, None))
            b = int(next(i2, None))
    except TypeError:
        if not b:
            aNotB += list(i1)
            break
        else:
            # bNotA += list(i1)
            break
print(aNotB)

输出：

[3、9、15、21、27、33、39、45、51、57、63、69、75、81、87、93、99]如果要同时获取aNotB和bNotA的结果，则可以取消注释这两个线。

时间与Andrej Kesely的答案进行比较：

$ seq 0 3 1000000 > 3k.txt
$ seq 0 2 1000000 > 2k.txt
$ time python manual_iter.py        
python manual_iter.py  0.38s user 0.00s system 99% cpu 0.387 total
$ time python heapq_groupby.py        
python heapq_groupby.py  1.11s user 0.00s system 99% cpu 1.116 total

Answer 2

在对文件进行排序时，您可以一次遍历每一行，如果文件A的行少于文件B的行，则您知道A不在B中，因此只能递增文件A并再次检查。如果A中的行大于B中的行，则您知道B不在A中，因此仅增加文件B。如果A和B相等，则您知道这两个行都在，因此请增加两个文件。在最初的问题中，您说过您对A中的条目感兴趣，但对B中的条目不感兴趣，此答案将扩展该范围，并为B中的条目提供A而不是A。这扩展了灵活性，但仍然允许您仅打印A中的条目而不是B 。

def strip_read(file):
    return file.readline().rstrip()

in_a_not_b = []
in_b_not_a = []
with open("fileA") as A:
    with open("fileB") as B:
        Aline = strip_read(A)
        Bline = strip_read(B)
        while Aline or Bline:
            if Aline < Bline and Aline:
                in_a_not_b.append(Aline)
                Aline = strip_read(A)
            elif Aline > Bline and Bline:
                in_b_not_a.append(Bline)
                Bline = strip_read(B)
            else:
                Aline = strip_read(A)
                Bline = strip_read(B)

print("in A not in B", in_a_not_b, "\nin B not in A", in_b_not_a)

我的样本文件的输出

in A not in B ['2', '5', '7'] 
in B not in A ['6']

Answer 3

您可以结合使用itertools.groupby（doc）和heapq.merge（doc）来进行迭代FileA和FileB延迟（只要对文件进行排序就可以了！）

FileA = [1, 1, 2, 3, 4, 5]
FileB = [1, 3, 4, 6]

from itertools import groupby
from heapq import merge

gen_a = ((v, 'FileA') for v in FileA)
gen_b = ((v, 'FileB') for v in FileB)

for v, g in groupby(merge(gen_a, gen_b, key=lambda k: int(k[0])), lambda k: int(k[0])):
    if any(v[1] == 'FileB' for v in g):
        continue
    print(v)

印刷品：

2
5

编辑（从文件读取）：

from itertools import groupby
from heapq import merge

gen_a = ((int(v.strip()), 1) for v in open('3k.txt'))
gen_b = ((int(v.strip()), 2) for v in open('2k.txt'))

for v, g in groupby(merge(gen_a, gen_b, key=lambda k: k[0]), lambda k: k[0]):
    if any(v[1] == 2 for v in g):
        continue
    print(v)

基准测试：

生成包含10_000_000个项目的文件：

seq 0 3 10000000 > 3k.txt
seq 0 2 10000000 > 2k.txt

该脚本大约需要10秒才能完成：

real    0m10,656s
user    0m10,557s
sys 0m0,076s