Duplicate-preserving collection intersection

Question

Python sets are magical things. Mutable, deduplicating data stores with handy operator overloads for &, ^ and |.

Specifically among the others, sets overload the & operator to do mutual membership tests like so:

>>> set("aasd") & set("aabc")
{'a'}

This is endlessly handy, but the huge downside of sets is they do not allow duplicate entries because they're hash tables, so for instance a fuzzy-finder will be a little too fuzzy.

What to do? Why, spin my own, of course!

def membertester(a, b):
    """a slow (iterative) dupe-preserving sorting subset tester,
    for mutual membership tests (like set overloads &)"""
    c = []
    a, b = sorted(list(a)), sorted(list(b))
    (l, maxl, s, minl) = {
        True:  (a, len(a), b, len(b)),
        False: (b, len(b), a, len(a))
    }[ len(a) >= len(b) ]

    for i in range(maxl):
        try:
            if s.count(l[i]) >= l.count(l[i]):
                c.append(a[i])

        except IndexError:
            pass
    return c

How it works, because it might be a little cryptic:

1. Retrieve the longer and shorter of the two sorted lists, and their lengths, using a switch statement.
2. For each item in the longer range, take note of the item if the number of occurences of the same item in the short list is greater than or equal to the number of occurences of the item in the longer list.

Used as above:

>>> membertest("aasd", "aabc")
['a', 'a']

Success!

How can I improve it? Is there a faster or more efficient way, or perhaps a less flimsy algorithm?

---

Assertions that should pass:

assert membertest("a" * 6, '') == []
assert membertest("abdeg", "rrertabasdddhjkdeg") == ['a', 'b', 'd', 'e', 'g']
assert membertest("abddeg", "rrertabasdddhjkdeg") == ['a', 'b', 'd', 'd', 'e', 'g']

An inconsistency I don't understand, but which is definitely a bug:

>>> is_subset('10', '122')
['0']
>>> is_subset("ab", "acc")
['a']

I don't understand this in the slightest.

I wrote this function specifically for use with A-Za-z, so numbers in strings was an oversight I didn't consider.

The other bugs noted in @alexwchan's great answer are definitely not intentional.

Answer 1

This is a carry-on from alexwlchan's answer, since he fixed some bugs.

As far as I understand, this is wrong:

membertester("aac", "acc")
#>>> ['a']

membertester("acc", "aac")
#>>> ['c']

You should get ['a', 'c'] in both cases. This is because you should be doing

if shorter.count(item) > common.count(item):

instead of >= longer.count(item). This is still very slow, though, and you should speed it up by caching the count operations:

from collections import Counter

def membertester(list_a, list_b):
    """a slow (iterative) dupe-preserving sorting subset tester,
    for mutual membership tests (like set overloads &)"""
    common = []
    shorter, longer = sorted([list_a, list_b], key=len)

    shorter_counts = Counter(shorter)
    common_counts = Counter()

    for item in longer:
        if shorter_counts[item] > common_counts[item]:
            common.append(item)
            common_counts[item] += 1

    return common

But Counter actually expresses things much nicer than you are right now:

from collections import Counter

def membertester(list_a, list_b):
    """a fast dupe-preserving sorting subset tester,
    for mutual membership tests (like set overloads &)"""

    shared = Counter(list_a) & Counter(list_b)
    return list(shared.elements())

Though there is good reason for dropping the final conversion to list

def membertester(list_a, list_b):
    """..."""
    return (Counter(list_a) & Counter(list_b)).elements()

or just working on Counters in the first place

membertester = Counter.__and__

Note also that the name really needs changing. Try

multiset_intersection = Counter.__and__

---

Why do I say that serializing to a list is ill-advised?

Modern Python should as much as possible try to provide lazy iterators instead of concrete storage; you can see this in Python 3's move to lazy map, filter and others. This is mostly because lazy computations are more efficient in the scheme of things - if you ever decide at one point you only want to iterate a result, or if you want to map the result before actually generating your result, or you actually decide elsewhere you want a bytearray or whatever, a lazy output is better.

But it's true even when you don't care at all about performance. Providing an iterator as output gives the abstract claim of "I'm providing these elements". Something like

for x in red_objects(...): ...

is easily understood in that red_objects is producing those objects that are red. The actual storage is unimportant. Something like

reds = red_objects(...)
reds.insert(1, 2)

however is making a dependency between the function that isn't actually part of the meaning of the function. It's a vestigial dependency. Not only is this another thing to maintain, but it obscures the intent of the code. Remember the policy that you should initialize variables as close to use-point as reasonable; the same thing applies here. If you want to use the property that isinstance(reds, list), you should try to make that property self-evident in the code at use point:

reds = list(red_objects(...))
reds.insert(1, 2)

Now the meaning of insert is much clearer, the API of red_objects is not over-specified and if you decide you actually want another type instead

reds = tuple(red_objects(...))
reds += ("spam",)

it comes at no extra cost. It also gives more internal flexibility for red_objects to, say, lazily produce values.

Answer 2

A few quick comments:

• As written, the code doesn’t always give the correct answer. Here are some cases I found that give what appear to be incorrect results:

  >>> membertester('00000112', '000000011')
  ['2']
  >>> print membertester('0001', '000/2')
  ['0', '0', '1']
  >>> print membertester('002', '001/')
  ['0', '2']
  >>> print membertester('10', '122')
  ['0']
  

  If I’ve understood the intention of the program correctly, those are all wrong. If they’re correct, you need to do a better job of explaining the program.

• The way you’ve written it is a bit fiddly – some comments interspersed with the program would make it much easier to read. That, and choosing better variable names – characters are cheap, don’t just use single letters.

  For example, how about longer and shorter instead of l and s?

• The construction for assigning (l, maxl, s, minl) is very weird, and it took me several reads to make sure I’d understood it correctly. This is too clever – I’d break it up into multiple statements. A few ways to do simplify it:

  • You don’t use the minl variable, so get rid of it. (If you meant to use it, is that a bug?)
  • The for loop can be replaced by for i, item in enumerate(longer), doing away with the need for the maxl variable.

  • You could assign the two remaining variables in a neater way:

    shorter, longer = sorted([a, b], key=len)
    

    or as an if statement if you wanted to be really explicit.

After a bit of tidying, this is what my version of the function looks like (note that it still has the same bugs as above):

def membertester(list_a, list_b):
    """a slow (iterative) dupe-preserving sorting subset tester,
    for mutual membership tests (like set overloads &)"""
    common = []
    shorter, longer = sorted([list_a, list_b], key=len)

    for idx, item in enumerate(longer):
        try:
            if shorter.count(item) >= longer.count(item):
                common.append(list_a[idx])
        except IndexError:
            pass
    return common

---

Sidebar: how did I find those examples?

I’m not psychic, and I’m not good at spotting obscure bugs. Instead, I used Hypothesis, which is a powerful randomised, property-based testing library. Here’s the property I used:

Every mutual member of two lists must be a member of each list.

Sounds reasonable, right?

And here’s how I expressed that as a test:

from hypothesis import given, strategies as st

@given(st.text(), st.text())
def test_that_mutual_members_are_in_both_lists(list_a, list_b):
    mutual_members = membertester(list_a, list_b)
    for item in mutual_members:
        assert item in list_a
        assert item in list_b

Hypothesis tries hundreds of randomised examples, and checks whether this property holds – it found a bug on the second run. I highly recommend trying it.

---

Sidebar 2: what causes that bug?

Notice that in all of the examples, we have len(b) > len(a). So we have longer = b, shorter = a. As you go through the for loop, you’re iterating over the elements of b, but you’re using a to choose which element gets marked as common. You want to replace

c.append(a[i])

with

c.append(l[i])

With that in mind, you can make the code much cleaner:

def membertester(list_a, list_b):
    """a slow (iterative) dupe-preserving sorting subset tester,
    for mutual membership tests (like set overloads &)"""
    common = []
    shorter, longer = sorted([list_a, list_b], key=len)

    for item in longer:
        if shorter.count(item) >= longer.count(item):
            common.append(item)

    return common

I’ve been unable to find any bugs in this implementation.

Answer 3

You can convert just the second item to a set, this preserves the duplicates as you are taking them from the first list that is not yet a set.

This reduces the time complexity from \$O(N^2)\$ of your solution to \$O(N *logN)\$(that is the time required to sort the list) and simplifies the code.

This code passes all the given test-cases:

def intersection_with_repeats(a, b):
    # As Veedrac noted, caching is needed to avoid O(N^2) time complexity
    b_set = set(b)
    return [i for i in sorted(a) if i in set(b)]

(I also modified the name as membertest did not feel descriptive enough)