Merge two (or more) lists of dictionaries pairing using a specific key-CodePudding

I have a set of different lists of dictionaries (actually obtained reading Excel worksheets) and I need to do an "inner join" on them:

each list is equivalent to a database table (each dict is a record)
each record has a specific key guaranteed unique in the list (column is "index")
I need to produce another list of dictionaries where each dictionary has a given "index" and all other key/value found in all lists where "index" match

To exemplify:

a = [{'idx': 1, 'foo': 'xx1', 'bar': 'yy1'},
     {'idx': 0, 'foo': 'xx0', 'bar': 'yy0'},
     {'idx': 2, 'foo': 'xx2', 'bar': 'yy2'}]
b = [{'idx': 0, 'fie': 'zz0', 'fom': 'kk0'},
     {'idx': 3, 'fie': 'zz3', 'fom': 'kk3'},
     {'idx': 1, 'fie': 'zz1', 'fom': 'kk1'}]

and I want yo have:

c = [{'idx': 0, 'foo': 'xx0', 'bar': 'yy0', 'fie': 'zz0', 'fom': 'kk0'},
     {'idx': 1, 'foo': 'xx1', 'bar': 'yy1', 'fie': 'zz1', 'fom': 'kk1'},
     {'idx': 2, 'foo': 'xx2', 'bar': 'yy2'},
     {'idx': 3, 'fie': 'zz3', 'fom': 'kk3'}]

of course problem is various list may have different length and not be sorted nicely.

Is there an easy way to do this or should I do nested loops explicitly searching for the matching record?

This actually works, but I'm VERY unsure it's the "most pythonic way":

a = [{'idx': 0, 'foo': 'xx0', 'bar': 'yy0'},
     {'idx': 1, 'foo': 'xx1', 'bar': 'yy1'},
     {'idx': 2, 'foo': 'xx2', 'bar': 'yy2'}]
b = [{'idx': 0, 'fie': 'zz0', 'fom': 'kk0'},
     {'idx': 1, 'fie': 'zz1', 'fom': 'kk1'},
     {'idx': 3, 'fie': 'zz3', 'fom': 'kk3'}]

c = [{'idx': 0, 'foo': 'xx0', 'bar': 'yy0', 'fie': 'zz0', 'fom': 'kk0'},
     {'idx': 1, 'foo': 'xx1', 'bar': 'yy1', 'fie': 'zz1', 'fom': 'kk1'},
     {'idx': 2, 'foo': 'xx2', 'bar': 'yy2'},
     {'idx': 3, 'fie': 'zz3', 'fom': 'kk3'}]

li = [a, b]
t = [{z['idx']: z for z in w} for w in li]
r = {}
for k in t:
    for j in k:
        if j in r:
            r[j].update(k[j])
        else:
            r[j] = k[j]
r = [t for t in r.values()]

print(r)

[{'idx': 0, 'foo': 'xx0', 'bar': 'yy0', 'fie': 'zz0', 'fom': 'kk0'}, {'idx': 1, 'foo': 'xx1', 'bar': 'yy1', 'fie': 'zz1', 'fom': 'kk1'}, {'idx': 2, 'foo': 'xx2', 'bar': 'yy2'}, {'idx': 3, 'fie': 'zz3', 'fom': 'kk3'}]

Can someone come up with something better?

CodePudding user response：

I'm not sure if this is more efficient than your solution:

from operator import itemgetter
from itertools import chain, groupby

a = [{'idx': 1, 'foo': 'xx1', 'bar': 'yy1'},
     {'idx': 0, 'foo': 'xx0', 'bar': 'yy0'},
     {'idx': 2, 'foo': 'xx2', 'bar': 'yy2'}]
b = [{'idx': 0, 'fie': 'zz0', 'fom': 'kk0'},
     {'idx': 3, 'fie': 'zz3', 'fom': 'kk3'},
     {'idx': 1, 'fie': 'zz1', 'fom': 'kk1'}]

c = sorted(a   b, key=itemgetter('idx'))
c = [
    dict(chain(*(record.items() for record in group)))
    for _, group in groupby(c, key=itemgetter('idx'))
]

Result:

[{'idx': 0, 'foo': 'xx0', 'bar': 'yy0', 'fie': 'zz0', 'fom': 'kk0'},
 {'idx': 1, 'foo': 'xx1', 'bar': 'yy1', 'fie': 'zz1', 'fom': 'kk1'},
 {'idx': 2, 'foo': 'xx2', 'bar': 'yy2'},
 {'idx': 3, 'fie': 'zz3', 'fom': 'kk3'}]

CodePudding user response：

If you are using Python 3.9 you can use the union operator or update() in older versions (added a third shorter list to the example)

a = [{'idx': 0, 'foo': 'xx0', 'bar': 'yy0'}, {'idx': 1, 'foo': 'xx1', 'bar': 'yy1'}, {'idx': 2, 'foo': 'xx2', 'bar': 'yy2'}]
b = [{'idx': 0, 'fie': 'zz0', 'fom': 'kk0'}, {'idx': 1, 'fie': 'zz1', 'fom': 'kk1'}, {'idx': 2, 'fie': 'zz2', 'fom': 'kk2'}]
c = [{'idx': 0, 'ief': 'zz0', 'mof': 'kk0'}, {'idx': 1, 'ief': 'zz1', 'mof': 'kk1'}]

lists = [b, c]

# with union
for lst in lists:
    for i, d in enumerate(lst):
        a[i] = a[i] | d

# with update
for lst in lists:
    for i, d in enumerate(lst):
        a[i].update(d)

print(a)

Edit:

If the dictionaries are not sorted or don't have the same keys you can sort the during the merge and add the missing keys

a = [{'idx': 1, 'foo': 'xx1', 'bar': 'yy1'},
     {'idx': 0, 'foo': 'xx0', 'bar': 'yy0'},
     {'idx': 2, 'foo': 'xx2', 'bar': 'yy2'}]
b = [{'idx': 0, 'fie': 'zz0', 'fom': 'kk0'},
     {'idx': 3, 'fie': 'zz3', 'fom': 'kk3'},
     {'idx': 1, 'fie': 'zz1', 'fom': 'kk1'}]

a.sort(key=lambda x: x['idx'])
lists = [b, c]
for lst in lists:
    lst.sort(key=lambda x: x['idx'])
    for i, d in enumerate(lst):
        if d['idx'] == a[i]['idx']:
            a[i] = a[i] | d
        else:
            a.append(d)
print(a)

Output

[{'idx': 0, 'foo': 'xx0', 'bar': 'yy0', 'fie': 'xx0', 'fom': 'kk0'},
 {'idx': 1, 'foo': 'xx1', 'bar': 'yy1', 'fie': 'xx1', 'fom': 'kk1'},
 {'idx': 2, 'foo': 'xx2', 'bar': 'yy2'},
 {'idx': 3, 'fie': 'zz3', 'fom': 'kk3'}]

CodePudding user response：

This is basically the same as your code, as far as the algorithm. You had the right idea using O(1) dict lookup, and update to merge the dicts.

""" module docstring here """
from itertools import chain
from collections import defaultdict
from pprint import pprint

a = [{'idx': 1, 'foo': 'xx1', 'bar': 'yy1'},
     {'idx': 0, 'foo': 'xx0', 'bar': 'yy0'},
     {'idx': 2, 'foo': 'xx2', 'bar': 'yy2'}]
b = [{'idx': 0, 'fie': 'zz0', 'fom': 'kk0'},
     {'idx': 3, 'fie': 'zz3', 'fom': 'kk3'},
     {'idx': 1, 'fie': 'zz1', 'fom': 'kk1'}]

KEY = 'idx'
merged = defaultdict(dict)
for row in chain(a, b):
    merged[row[KEY]].update(row)

pprint(list(merged.values()))

I tried not to use any single letter variable names (besides the original inputs)
itertools.chain lets you iterate over several iterables as one
defaultdict hides some of that "if it's in there already, do this, otherwise do that"
[x for x in iterable] could be written list(iterable)
The "merged" data structure is more useful. It's a shame to dump it out to an inefficient list, but that was the requirement.
I also ran it through pylint and pep8 tools

Concerns:
This could be handled in a database or pandas, which are designed for this exact function.
What if the rows happen to have a conflict on one of the data fields? You'll never know, as update will just overwrite.