8
\$\begingroup\$

I have two lists that I want to join on a condition. Unlike in a relational algebra join, if more than one element of each list can be matched, only one should be selected, and shouldn't then be reused. Also, if any of the elements of the first list don't match any of the second list, the process should fail.

Example:

# inputs
list1 = [{'amount': 124, 'name': 'john'},
         {'amount': 456, 'name': 'jack'},
         {'amount': 456, 'name': 'jill'},
         {'amount': 666, 'name': 'manuel'}]
list2 = [{'amount': 124, 'color': 'red'},
         {'amount': 456, 'color': 'yellow'},
         {'amount': 456, 'color': 'on fire'},
         {'amount': 666, 'color': 'purple'}]
keyfunc = lambda e: e['amount']

# expected result
[({'amount': 124, 'name': 'john'}, {'amount': 124, 'color': 'red'}),
 ({'amount': 456, 'name': 'jack'}, {'amount': 456, 'color': 'yellow'}),
 ({'amount': 456, 'name': 'jill'}, {'amount': 456, 'color': 'on fire'}),
 ({'amount': 666, 'name': 'manuel'}, {'amount': 666, 'color': 'purple'})]

I've written a working implementation in Python, but it seems clunky, unclear and inefficient:

def match(al, bl, key):
    bl = list(bl)
    for a in al:
        found = False
        for i, b in enumerate(bl):
            if key(a) == key(b):
                found = True
                yield (a, b)
                del bl[i]
                break
        if not found:
            raise Exception("Not found: %s" % a)

result = list(match(list1, list2, key=keyfunc)
\$\endgroup\$
  • \$\begingroup\$ Is there a specific reason to keep the dictionaries separated? I mean, could the return value be like [{'amount': 124, 'name': 'john', 'color': 'red'}, {'amount': 456, 'name': 'jack', 'color': 'yellow'}, …]? \$\endgroup\$ – 409_Conflict Feb 13 '18 at 10:05
  • \$\begingroup\$ @MathiasEttinger I wanted to keep the match() function generic; the entries may not necessarily be dictionaries, or the caller may want to merge them differently (e.g. only copying a subset of the keys from one to the other). \$\endgroup\$ – André Paramés Feb 13 '18 at 10:18
  • \$\begingroup\$ Is list2 allowed to have unused elements? \$\endgroup\$ – Eric Duminil Feb 13 '18 at 21:59
  • \$\begingroup\$ @EricDuminil yes \$\endgroup\$ – André Paramés Feb 14 '18 at 9:46
3
\$\begingroup\$

I think you could simplify your code a bit by considering the second list to be a dictionary mapping the key to list of values with the same key. This would avoid doing a linear search over the second list for each element of the first list, and also lends itself to less code:

from collections import defaultdict

def match(al, bl, key):
    table = defaultdict(list)
    for b in bl:
        table[key(b)].append(b)
    return [(a, table[key(a)].pop(0)) for a in al]

The function will raise an IndexError exception in case the key does not reference a matching element in bl.

\$\endgroup\$
  • \$\begingroup\$ What's slightly "meh" with this proposal in my opinion is that the list comprehension relies on a side effect of pop, namely that it removes the selected element from the list. \$\endgroup\$ – Frerich Raabe Feb 13 '18 at 20:12
  • \$\begingroup\$ That's nice and concise. I'd say that pop's main job is to remove an element, it really isn't surprising at all IMHO. Your method doesn't detect if b has unused elements. I'm not sure if that's a bug or a feature. I'll ask OP. \$\endgroup\$ – Eric Duminil Feb 13 '18 at 21:58
  • \$\begingroup\$ @EricDuminil To me, a list comprehension is a declarative construct (as opposed to an imperative for loop) much like in Haskell (from which Python derived list comprehensions). In this mathematical sense, the value to which each element in the input sequence is mapped does not depend on other values (resp. the order in which they are processed). This independence among the elements is broken by the pop call (due to which you depend on a very specific order in which the list comprehension processes the elements in al). \$\endgroup\$ – Frerich Raabe Feb 14 '18 at 7:28
  • \$\begingroup\$ @EricDuminil As for detecting unused elements in bl, this could be tested after the list comprehension by checking if any(not x for x in table.values()) holds. \$\endgroup\$ – Frerich Raabe Feb 14 '18 at 7:33
  • \$\begingroup\$ No need to, according to OP, your behaviour is a feature and not a bug ;) Well done! \$\endgroup\$ – Eric Duminil Feb 14 '18 at 9:53
13
\$\begingroup\$

Theory

It might not be clear at first, but you're basically describing a bipartite graph.

enter image description here

You're interested in finding the maximum matching and if it's perfect.

NetworkX is a great Python library for graphs, and the maximum_matching function is already implemented. It uses the Hopcroft-Karp algorithm and runs in \$O(n^{2.5})\$ where \$n\$ is the number of nodes.

You only have to preprocess your lists into a graph and let networkx do its job.

Code

Here's a slightly modified version of a previous answer on Stack Overflow:

import networkx as nx
import matplotlib.pyplot as plt

def has_a_perfect_match(list1, list2):
    if len(list1) != len(list2):
        return False

    g = nx.Graph()

    l = [('l', d['name'],  d['amount']) for d in list1]
    r = [('r', d['color'], d['amount']) for d in list2]

    g.add_nodes_from(l, bipartite=0)
    g.add_nodes_from(r, bipartite=1)

    edges = [(a,b) for a in l for b in r if a[2] == b[2]]
    g.add_edges_from(edges)

    pos = {}
    pos.update((node, (1, index)) for index, node in enumerate(l))
    pos.update((node, (2, index)) for index, node in enumerate(r))

    m = nx.bipartite.maximum_matching(g, l)
    colors = ['blue' if m.get(a) == b else 'gray' for a,b in edges]

    nx.draw_networkx(g,
                     pos=pos,
                     arrows=False,
                     labels = {n:"%s\n%d" % (n[1], n[2]) for n in g.nodes()},
                     edge_color=colors)
    plt.axis('off')
    plt.show()

    return len(m) // 2 == len(list1)

As a bonus, it displays a diagram with the graph and maximum matching:

list1 = [{'amount': 124, 'name': 'john'},
         {'amount': 456, 'name': 'jack'},
         {'amount': 456, 'name': 'jill'},
         {'amount': 666, 'name': 'manuel'}]
list2 = [{'amount': 124, 'color': 'red'},
         {'amount': 456, 'color': 'yellow'},
         {'amount': 456, 'color': 'on fire'},
         {'amount': 666, 'color': 'purple'}]

print(has_a_perfect_match(list1, list2))
# True

enter image description here

list1 = [{'amount': 124, 'name': 'john'},
         {'amount': 456, 'name': 'jack'},
         {'amount': 457, 'name': 'jill'},
         {'amount': 666, 'name': 'manuel'}]
list2 = [{'amount': 124, 'color': 'red'},
         {'amount': 458, 'color': 'yellow'},
         {'amount': 456, 'color': 'on fire'},
         {'amount': 666, 'color': 'purple'}]

print(has_a_perfect_match(list1, list2))
# False

enter image description here

Notes

The desired matching is in m and has a slightly different format than what you mentioned:

{('l', 'jack', 456): ('r', 'yellow', 456), ('l', 'jill', 456): ('r', 'on fire', 456), ('l', 'john', 124): ('r', 'red', 124), ('l', 'manuel', 666): ('r', 'purple', 666), ('r', 'red', 124): ('l', 'john', 124), ('r', 'yellow', 456): ('l', 'jack', 456), ('r', 'purple', 666): ('l', 'manuel', 666), ('r', 'on fire', 456): ('l', 'jill', 456)}

It does have enough information, though.

Note that the edge generation isn't optimal (it's \$O(n^{2})\$ and could be \$O(n)\$ with dicts) but it's concise and still faster than the matching algorithm. Feel free to modify it!

Optimization

@Peilonrayz' answer has a better performance because your problem is easier than the general matching problem : there are no connections between nodes with distinct ids, so a greedy algorithm works fine.

Actually, it's possible to check in 2 lines if the lists match. With a Counter, you just need to check if the distribution (e.g. Counter({124: 1, 456: 2, 666: 1})) is the same for both lists:

from collections import Counter
Counter(map(key, list1)) == Counter(map(key, list2))
# True
\$\endgroup\$
  • \$\begingroup\$ Thanks! While my case is in fact simple and easier, I appreciate knowing the theory of the problem; it'll help me more when I come across similar problems in the future. \$\endgroup\$ – André Paramés Feb 13 '18 at 15:36
8
\$\begingroup\$

I think you should split your code into two functions.

  1. You should add some code to group your object lists together. I'd call this group_by.
  2. Take the first from each match, and error in the match function.

To perform the first function, I'd use collections.defaultdict, so that you only generate the keys that you need. This also has the benefit of having \$O(kn)\$ performance, rather than \$O(n^k)\$. Where \$n\$ is the amount of objects in each list, and \$k\$ are the amount of lists.

After this you can check if there are enough items to yield correctly. This is two checks, 1 that there are items in the first group. Then you check that there are the same amount of items in both groups. After this, you can use zip to group together items in pairs.

import collections


def group_by(lists, key):
    amount = range(len(lists))
    d = collections.defaultdict(lambda:tuple([[] for _ in amount]))
    for i, objects in enumerate(lists):
        for obj in objects:
            d[key(obj)][i].append(obj)
    return d


def match(al, bl, key):
    for key, groups in group_by((al, bl), key).items():
        if groups[0] and len(groups[0]) != len(groups[1]):
            raise ValueError("Missing value for {!r}".format(key))
        yield from zip(*groups)

The type of exception that should be raised is debatable, however it shouldn't be Exception.

  • If you think the error is predominantly due to missing values, then using ValueError would probably be best.
  • If you think the error is because it requires there to be a common key, then KeyError or LookupError may be better.
  • Alternately if you're planning on making an entire rational algebra Python library, create your own exceptions.
\$\endgroup\$
  • \$\begingroup\$ Darn it, too fast, I was thinking about something alike. I wonder, though, how missing entries are handled when considering PEP 479 and adding a from __future__ import generator_stop? \$\endgroup\$ – 409_Conflict Feb 13 '18 at 10:30
  • \$\begingroup\$ I don't want to take only the first item from each group; I just don't want to reuse items in different matches. I can understand the group_by, but I don't see how match here accomplishes the expected result. \$\endgroup\$ – André Paramés Feb 13 '18 at 10:40
  • \$\begingroup\$ @MathiasEttinger That's a good question, there was a bug I failed to notice without that enabled. Generators stop when they encounter StopIteration, I thought it passed through. With the future it fails on the iter rather than the raise now. Thanks, :) \$\endgroup\$ – Peilonrayz Feb 13 '18 at 10:41
  • \$\begingroup\$ @Peilonrayz only one for each match, not in total. Please look at the expected result in the example. Feel free to suggest any improvements on the text of the question as well :) \$\endgroup\$ – André Paramés Feb 13 '18 at 10:43
  • \$\begingroup\$ @Peilonrayz Yes, that's what I thought. I took advantage of this behaviour in the past… Now I feel a bit sad, somehow, as you won't be able to rely on a generator to "swallow" a StopIteration. \$\endgroup\$ – 409_Conflict Feb 13 '18 at 10:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.