Compute list difference

Simple code that gives you the difference with multiple items if you want that:

a=[1,2,3,3,4]
b=[2,4]
tmp = copy.deepcopy(a)
for k in b:
    if k in tmp:
        tmp.remove(k)
print(tmp)

There are 3 options for doing this, two of which are acceptable and one of which should not be done.

The 3 options, at a high level, are:

1. Subtract two sets (best sometimes)
2. Check if each list item exists in a set (best most of time)
3. Check if each list item exists in a list (do not do)

Option 3) should never be chosen over option 2). Depending on the needs of your application, you may prefer option 1) or 2), while 2) is likely the preferred approach in most use cases. 2) is very similar to the performance of 1) since both have O(m + n) time complexity. By contrast, 2) has marginal benefits in space complexity over 1) and maintains both the order of the original list and any duplications in the original list.

If you want to remove duplications and do not care about the order, then 1) is likely the best fit for you.

import time

def fun1(l1, l2):
    # Order and duplications in l1 are both lost, O(m) + O(n)
    return set(l1) - set(l2)

def fun2(l1, l2):
    # Order and duplications in l1 are both preserved, O(m) + O(n)
    l2_set = set(l2)
    return [item for item in l1 if item not in l2_set]

def fun3(l1, l2):
    # Order and duplications in l1 are both preserved, O(m * n)
    # Don't do
    return [item for item in l1 if item not in l2]

A = list(range(7500))
B = list(range(5000, 10000))

loops = 100

start = time.time()
for _ in range(loops):
    fun1(A, B)
print(f"fun1 time: {time.time() - start}")

start = time.time()
for _ in range(loops):
    fun2(A, B)
print(f"fun2 time: {time.time() - start}")

start = time.time()
for _ in range(loops):
    fun3(A, B)
print(f"fun3 time: {time.time() - start}")

fun1 time: 0.03749704360961914
fun2 time: 0.04109621047973633
fun3 time: 32.55076885223389

Adding an answer to take care of the case where we want a strict difference with repetitions, i.e., there are repetitions in the first list that we want to keep in the result. e.g. to get,

[1, 1, 1, 2] - [1, 1] --> [1, 2]

We could use an additional counter to have an elegant difference function.

from collections import Counter

def diff(first, second):
    secondCntr = Counter(second)
    second = set(second)
    res = []
    for i in first:
        if i not in second:
            res.append(i)
        elif i in secondCntr:
            if secondCntr[i] > 0:
                secondCntr[i] -= 1
            else:
                res.append(i)        
    return res

I don't see a solution in this thread that preserves duplication in A. When an element of A matches with an element of B, this element has to be removed in B so that when the same element occurs again in A, it has to appear in the difference if this element appears only once in B.

def diff(first, second):
   l2 = list(second)
   l3 = []
   for el in first:
      if el in l2:
         l2.remove(el)
      else:
         l3 += [el]
   return l3

l1 = [1, 2, 1, 3, 4]
l2 = [1, 2, 3, 3]
diff(l1, l2)
>>> [1, 4]