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

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

Answer 1

如果你想逐行读取文件，因为你没有那么多内存并且你需要一个线性解决方案，如果你的文件是基于行的，你可以使用 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