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

163

Arjun Muraleedharan：

有两个文件，分别是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）或二次时间复杂度，对于具有大条目的超大文件而言效率不高。

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

yukashima huksay：

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

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

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

本文收集自互联网，转载请注明来源。

如有侵权，请联系 [email protected] 删除。