在 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 加载下一个块，依此类推。然后在 FileA 块检查 FileB 中的所有元素之后，然后从 FileA 加载下一批，然后继续。但这会产生 O(n^2) 或二次时间复杂度，并且对于包含大量条目的非常大的文件来说效率不高。

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

Answer 1

您可以组合 itertools.groupby (doc) and 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

Answer 2

如果你想逐行读取文件，因为你没有那么多内存，你需要一个线性解决方案，如果你的文件是基于行的，你可以用 iter 来做到这一点，否则见 this :

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

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] If you want both the result for aNotB and bNotA you can uncomment those two lines.

与 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 3

基于文件读取的简单解决方案（假设每一行都有一个数字）：

results = []
with open('file1.csv') as file1, open('file2.csv') as file2:
        var1 = file1.readline()
        var2 = file2.readline()
        while var1:
            while var1 and var2:
                if int(var1) < int(var2):
                    results.append(int(var1))
                    var1 = file1.readline()
                elif int(var1) > int(var2):
                    var2 = file2.readline()
                elif int(var1) == int(var2):
                    var1 = file1.readline()
                    var2 = file2.readline()
            if var1:
                results.append(int(var1))
                var1 = file1.readline()
print(results)
output = [2, 5, 7, 9]

Answer 4

随着文件的排序，您可以一次遍历每一行，如果文件 A 的行少于文件 B 的行，那么您就知道 A 不在 B 中，因此您只增加文件 A然后再次检查。如果 A 中的行大于 B 中的行，那么您知道 B 不在 A 中，因此您只增加文件 B。如果 A 和 B 相等，那么您知道行在两者中，因此增加两个文件。虽然在您最初的问题中您说您对 A 而不是 B 中的条目感兴趣，但这个答案将扩展它并给出 B 中的条目而不是 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 5

这类似于经典的 Knuth 排序和搜索。不妨考虑阅读stack question, on-line lecture notes pdf, and Wikipedia。堆栈问题提到了一些我同意的事情，那就是使用 unix sort 命令。始终，始终使用您自己的数据进行测试，以确保选择的方法对您的数据最有效，因为其中一些算法依赖于数据。

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

Find all the numbers in one file that are not in another file in python

python

arrays

file

out-of-memory