Find the (asymmetric) set-difference of two lists

Question

I want to define a function which compute the difference of two lists as multi-sets. For example, [1,2,2,3]-[1,2,3,4]=[2]. I defined the following in python.

def SetDifferenceListDifference(A,B): # A-B, can have duplicate elements
    r=[]
    r1=list(set(A))
    for i in r1:
        t1=A.count(i)-B.count(i)
        #print(t1)
        for j in range(1,t1+1):
            r.append(i)
    return r

Is there a faster way in python to do this? Thank you very much.

Answer 1

Some style issues:

• Function names should be snake_case, not PascalCase.
• Function arguments should be lower case.
• The operators need more space.
• There's no documentation comment to explain what the function does, or to show examples.

---

This looks like it could be greatly simplified using the Standard Library's collections.Counter:

Here's how you would use Counter to perform the same operation, complete with unit tests:

from collections import Counter

def subtract_multiset(a, b):
    '''
    Return a copy of a with the elements of b removed.

    >>> subtract_multiset([], [0, 1])
    []
    >>> subtract_multiset(["x", "x", "y"], [])
    ['x', 'x', 'y']
    >>> subtract_multiset(["ham", "spam", "eggs", "spam", "spam"], ["spam", "spam"])
    ['ham', 'spam', 'eggs']
    >>> subtract_multiset([0, 0, 1, 1], [0, 1, 1, 1])
    [0]
    >>> subtract_multiset([1, 2, 2, 3], [1, 2, 3, 4])
    [2]
    '''

    diff = Counter(a) - Counter(b)
    return list(diff.elements())


if __name__ == '__main__':
    import doctest
    doctest.testmod()

This scales better as we increase the length of the lists:

• The question code calls list.count() on both A and B inside the loop, which executes for every element in the set r1. So it scales as O(N²) where N is the total number of elements, assuming the number of unique elements in A is proportional to the size of A.

• Constructing the counters looks at each element once, with a log N lookup (pretty similar to constructing the set in the original implementation). But after that, the counter subtraction and listing of elements has smaller impact, so overall performance tends to O(N log N).

Answer 2

I agree with all styling suggestions made by Toby. However, the OP asked for ways to make his implementation faster. Using Counter is indeed nice, but it's considerably slower than the OP's original approach. By making some slight adjustments to the original it can be made even faster.

My suggestion:

def set_difference_opt(a: list[Any], b: list[Any]) -> list[Any]:
    """Return elements of 'a' that are not in 'b'."""
    diffs = []
    for v in set(a):
        diff = a.count(v) - b.count(v)
        diffs.extend([v] * diff)
    return diffs

Benchmark:

print(timeit.timeit(lambda: set_difference(s1, s2)))
print(timeit.timeit(lambda: set_difference_opt(s1, s2)))
print(timeit.timeit(lambda: subtract_multiset(s1, s2)))

Original approach:
0.7215887490019668
Original optimized:
0.5921416310011409
Using collections:
2.7791459890140686

Edit

That's only the case when both inputs are small though. Here's the results for two arrays with random integers between 1 and 10 of size 100:

Original approach:
13.11639182100771
Original optimized:
12.332467784988694
Using collections:
7.758293374994537

So most likely, using Counter is what you'll want.

Answer 3

On top the existing reviews, here are few more points mostly about style.

Use descriptive names

It's good to give descriptive names to variables to help readers understand their purpose. For example:

• r is the difference of the input elements, diff would describe that better
• i is actually a number, num would describe it better
  • Note that i is commonly used as the index variable in a counting loop
• t is the count difference of the number of occurrences, so it could be count_diff
• r1 is ... well it's only used once so you could just inline it in for num in set(A): ...

Do not create unnecessary list

Creating a list here is unnecessary:

r1=list(set(A))
for i in r1:

You can iterate over a set directly:

for num in set(A):

Use simpler form of range

In this loop:

for j in range(1,t1+1):
    r.append(i)

The values of the range are not used, and since the default starting value of range(x) is 0, range(t1) is equivalent to range(1, t1 + 1).

Also, when the variable of a range loop is not used, it's customary in Python to give it the name _:

for _ in range(t1):
    r.append(i)

Use simpler way to create a list of the same character

Instead of:

for j in range(1,t1+1):
    r.append(i)

This is equivalent and shorter:

r.extend([i] * t1)