Как наиболее эффективно рассчитать разницу строк из двух файлов?

У меня есть два списка в 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. У меня 78.514.022 элементов в моем list_b.txt и 78.616.777 в моем списке list_a.txt. Я не знаю стоимость этого выражения: if a not in arq_b. Но если я выполню этот код, я думаю, что не закончу в этом году.

Мой компьютер имеет 8 ГБ, и я выделяю 15 ГБ для подкачки, чтобы не взорвать мою оперативную память.

У меня вопрос, есть ли другой способ сделать эту операцию более эффективной (быстрее)?

list_a - это ордината, а list_b нет.
Каждый элемент имеет этот размер: images/00000cd9fc6ae2fe9ec4bbdb2bf27318f2babc00.png
Порядок не имеет значения, я хочу знать профицит.

Ответ 1

Вы можете создать один набор содержимого первого файла, а затем просто использовать 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 внутри. Не большой выигрыш в производительности (см. Разницу производительности в зависимости от типа аргумента), но он короче.

Ответ 2

Попробуйте использовать наборы:

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)

Сложность вычитания двух множеств составляет O (n) в размере множества a.

Ответ 3

Расширить комментарий @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.

Ответ 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).