21

I have two lists in python list_a and list_b. The list_a have some images links, and the list_b too. 99% of the items are the same, but i have to know this 1%. The all surplus items are in list_a, that means all items in list_b are in list_a. My initial idea is subtract all items: list_a - list_b = list_c, where the list_c are my surplus items. My code is:

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)

I think the logic is right, if i have some items, the code is run fast. But i dont have 10 items, or 1.000, or even 100.000. I have 78.514.022 items in my list_b.txt and 78.616.777 in my list list_a.txt. I dont't know the cost of this expression: if a not in arq_b. But if i execute this code, i think wont finish in this year.

My pc have 8GB, and i allocate 15gb for swap to not explode my RAM.

My question is, there's another way to make this operation more efficiently(Faster)?

  • The list_a is ordinate but the list_b not.
  • Each item have this size: images/00000cd9fc6ae2fe9ec4bbdb2bf27318f2babc00.png
  • The order doesnt matter, i want know the surplus.
Zobia Kanwal
  • 4,085
  • 4
  • 15
  • 38
Vinicius Morais
  • 565
  • 1
  • 5
  • 22

4 Answers4

14

you can create one set of the first file contents, then just use difference or symmetric_difference depending on what you call a difference

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

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

if list_b.txt contains more items than list_a.txt you want to swap them or use set_a.symmetric_difference(f) instead, depending on what you need.

difference(f) works but still has to construct a new set internally. Not a great performance gain (see set issubset performance difference depending on the argument type), but it's shorter.

Jean-François Fabre
  • 137,073
  • 23
  • 153
  • 219
11

Try using sets:

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)

The complexity of subtracting two sets is O(n) in the size of the set a.

L3viathan
  • 26,748
  • 2
  • 58
  • 81
2

To extend the comment of @L3viathan If order of element is not important set is the rigth way. here a dummy example you can adapt:

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

as you see is pretty straightforward in python.

RomainL.
  • 997
  • 1
  • 10
  • 24
2

In case order matters you can presort the lists together with item indices and then iterate over them together:

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)]

This has time complexity of the sorting algorithm, i.e. O(n*log n).

a_guest
  • 34,165
  • 12
  • 64
  • 118