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

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

标签： pythonarraysfileout-of-memory

Answer 1

如果您想逐行读取文件，因为您没有太多内存并且需要线性解决方案，如果您的文件是基于行的，则可以使用 iter 执行此操作，否则请参见：

首先在您的终端中，您可以这样做来生成一些测试文件：

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