计算两个文件的行差异的最有效方法是什么？

Question

我在 python list_a 和 list_b 中有两个列表。 list_a 有一些图片链接，list_b 也有。 99%的东西是一样的，但我必须知道这1%。所有剩余的项目都在 list_a 中，这意味着 list_b 中的所有项目都在 list_a 中。我最初的想法是减去所有项目： list_a - list_b = list_c，其中list_c是我的剩余物品。我的代码是：

list_a = []
list_b = []
list_c = []

arq_b = open('list_b.txt','r')
for b in arq_b:
    list_b.append(b)

arq_a = open('list_a.txt','r')
for a in arq_a:
    if a not in arq_b:
        list_c.append(a)

arq_c = open('list_c.txt','w')
for c in list_c:
    arq_c.write(c)

我认为逻辑是正确的，如果我有一些项目，代码运行很快。但我没有 10 件商品，或 1.000 件，甚至 100.000 件。我的 list_b.txt 中有 78.514.022 项，列表 list_a.txt 中有 78.616.777 项。我不知道这个表达式的成本：if a not in arq_b。但是如果我执行这段代码，我想今年不会完成。

我的电脑有 8GB，我分配了 15GB 用于交换以防止我的 RAM 爆炸。

我的问题是，还有另一种方法可以使此操作更有效（更快）吗？

list_a 是纵坐标，list_b 不是。
每件商品的尺寸为：images/00000cd9fc6ae2fe9ec4bbdb2bf27318f2babc00.png
顺序无所谓，我想知道剩余的。

Answer 1

尝试使用集合：

with open("list_a.txt") as f:
    set_a = set(f)

with open("list_b.txt") as f:
    set_b = set(f)

set_c = set_a - set_b

with open("list_c.txt","w") as f:
    for c in set_c:
        f.write(c)

两个集合相减的复杂度is O(n) in the size of the set a。

Answer 2

扩展@L3viathan的评论如果元素的顺序不重要，则设置是正确的方法。这里有一个你可以改编的虚拟例子：

l1 = [0,1,2,3,4,5]
l2 = [3,4,5]
setL1 = set(l1)  # transform the list into a set
setL2 = set(l2)
setDiff = setl1 - setl2  # make the difference 
listeDiff = list(setDiff)  # if you want to have your element back in a list

如您所见，在 python 中非常简单明了。

Answer 3

您可以创建一组第一个文件内容，然后根据您所说的不同使用difference或symmetric_difference

with open("list_a.txt") as f:
    set_a = set(f)

with open("list_b.txt") as f:
    diffs = set_a.difference(f)

如果 list_b.txt 包含的项目多于 list_a.txt 您想要交换它们或使用 set_a.symmetric_difference(f) 代替，具体取决于您的需要。

difference(f) 有效，但仍然需要在内部构造一个新的 set。性能提升不大（参见），但它更短。

Answer 4

如果顺序很重要，您可以将列表与项目索引一起预排序，然后一起迭代它们：

list_2 = sorted(list_2)
diff_idx = []
j = 0
for i, x in sorted(enumerate(list_1), key=lambda x: x[1]):
    if x != list_2[j]:
        diff_idx.append(i)
    else:
        j += 1
diff = [list_1[i] for i in sorted(diff_idx)]

这具有排序算法的时间复杂度，即O(n*log n)。

计算两个文件的行差异的最有效方法是什么？

What is the most efficient way to compute the difference of lines from two files?

python

performance

list

python-3.x

difference