left merging list of dictionaries in python with multiple keys, filling in with zeros-CodePudding

I am trying to essentially replace the pd.merge() functionality in script without using pandas.

If I have 2 list of dictionaries (below):

l1 = [{'key1': '2017', 'key2': '20-30', 'val1': 11},
  {'key1': '2017', 'key2': '30-40', 'val1': 22},
  {'key1': '2017', 'key2': '40-50', 'val1': 33},
  {'key1': '2017', 'key2': '50 ', 'val1': 44},
  {'key1': '2018', 'key2': '20-30', 'val1': 55},
  {'key1': '2018', 'key2': '30-40', 'val1': 66},
  {'key1': '2018', 'key2': '40-50', 'val1': 77},
  {'key1': '2018', 'key2': '50 ', 'val1': 88}]


l2 = [{'key1': '2017', 'key2': '20-30', 'val2': 1000},
      {'key1': '2017', 'key2': '40-50', 'val3': 2000},
      {'key1': '2018', 'key2': '50 ', 'val3': 3000}]

And I want to "left merge" using multiple keys to render the following result:

output = [{'key1': '2017', 'key2': '20-30', 'val1': 11, 'val2':1000, 'val3'0:},
      {'key1': '2017', 'key2': '30-40', 'val1': 22, 'val2':0, 'val3':0},
      {'key1': '2017', 'key2': '40-50', 'val1': 33, 'val2':0, 'val3':2000},
      {'key1': '2017', 'key2': '50 ', 'val1': 44, 'val2':0, 'val3':0},
      {'key1': '2018', 'key2': '20-30', 'val1': 55, 'val2':0, 'val3':0},
      {'key1': '2018', 'key2': '30-40', 'val1': 66, 'val2':0, 'val3':0},
      {'key1': '2018', 'key2': '40-50', 'val1': 77, 'val2':0, 'val3':0},
      {'key1': '2018', 'key2': '50 ', 'val1': 88, 'val2':0, 'val3':3000}]

The closest I've gotten is by using this as a reference and the code below, but I am unsure how get it quite right (zeroes included).

l1 = {(d['key1'], d['key2']):d for d in l1}
all = [dict(d, **l1.get((d['key1'], d['key2']), {})) for d in l2]

CodePudding user response：

When working with pandas dataframes, pandas usually knows the number of columns and data types in advance.

Assuming all elements in each list have the same structure (keys in l1 may be different from l2, but all elements in l1 have same keys, and all elements in l2 have same keys, then discovering the default type as well as total number of keys in each of the output dictionaries becomes an O(1) operation. Right now, given that l2 has different keys, you will have to scan the lists i.e. O(n) operation, to find out total number of columns/keys in l2.

Refer to the left_merge function in the code below. It's more verbose but explains what's going on.

l1 = [{'key1': '2017', 'key2': '20-30', 'val1': 11},
  {'key1': '2017', 'key2': '30-40', 'val1': 22},
  {'key1': '2017', 'key2': '40-50', 'val1': 33},
  {'key1': '2017', 'key2': '50 ', 'val1': 44},
  {'key1': '2018', 'key2': '20-30', 'val1': 55},
  {'key1': '2018', 'key2': '30-40', 'val1': 66},
  {'key1': '2018', 'key2': '40-50', 'val1': 77},
  {'key1': '2018', 'key2': '50 ', 'val1': 88}]


l2 = [{'key1': '2017', 'key2': '20-30', 'val2': 1000},
      {'key1': '2017', 'key2': '40-50', 'val3': 2000},
      {'key1': '2018', 'key2': '50 ', 'val3': 3000}]

op_output = [{'key1': '2017', 'key2': '20-30', 'val1': 11, 'val2':1000, 'val3': 0},
      {'key1': '2017', 'key2': '30-40', 'val1': 22, 'val2':0, 'val3':0},
      {'key1': '2017', 'key2': '40-50', 'val1': 33, 'val2':0, 'val3':2000},
      {'key1': '2017', 'key2': '50 ', 'val1': 44, 'val2':0, 'val3':0},
      {'key1': '2018', 'key2': '20-30', 'val1': 55, 'val2':0, 'val3':0},
      {'key1': '2018', 'key2': '30-40', 'val1': 66, 'val2':0, 'val3':0},
      {'key1': '2018', 'key2': '40-50', 'val1': 77, 'val2':0, 'val3':0},
      {'key1': '2018', 'key2': '50 ', 'val1': 88, 'val2':0, 'val3':3000}]


def left_merge(a, b, key):
    # a and b are list of dictionaries
    # key is a callable
    # TODO: bounds checking if a is empty or b is empty

    b_index = {key(i): i for i in b}
    output = []

    # pick one element from a and b so we know the final columns
    merged_item_columns = set()
    merged_item_columns.update(a[0].keys())
    merged_item_columns.update(b[0].keys())

    # UPDATE: Above assumption of picking one element from list a and b
    # does not hold true
    # In OP's question: l2 has some records with val2, some with val3.
    # So it isn't like a dataframe where all columns are known in advance.

    # Discovery requires scanning all elements (sigh)
    # This can be done when creating the index for b atleast.

    b_index = {} # replaces the original b_index computation at the beginning.
    # NOTE: if l1 also has similar characteristics, it will also require a similar scan.
    for i in b:
        b_index[key(i)] = i
        merged_item_columns.update(i.keys())

    # TODO: determine type for each column and choose correct defaults
    # using 0 as default for now.
    merged_item_template = {k:0 for k in merged_item_columns}
    for a_item in a:
        merged_item = merged_item_template.copy()
        merged_item.update(a_item)

        b_item = b_index.get(key(a_item))
        if b_item is not None:
            merged_item.update(b_item)

        output.append(merged_item)

    return output


output = left_merge(l1, l2, key=lambda x:(x['key1'], x['key2']))
print(output)
print(op_output == output)

CodePudding user response：

You can first assign zeros for val2 and val3 and apply the code you got:

l2 = {(d['key1'], d['key2']): d for d in l2}

output = [{**d, **{'val2': 0, 'val3': 0}} for d in l1] # zeros for val2 and val3
output = [{**d, **l2.get((d['key1'], d['key2']), {})} for d in output] # update

Output:

[{'key1': '2017', 'key2': '20-30', 'val1': 11, 'val2': 1000, 'val3': 0},
 {'key1': '2017', 'key2': '30-40', 'val1': 22, 'val2': 0, 'val3': 0},
 {'key1': '2017', 'key2': '40-50', 'val1': 33, 'val2': 0, 'val3': 2000},
 {'key1': '2017', 'key2': '50 ', 'val1': 44, 'val2': 0, 'val3': 0},
 {'key1': '2018', 'key2': '20-30', 'val1': 55, 'val2': 0, 'val3': 0},
 {'key1': '2018', 'key2': '30-40', 'val1': 66, 'val2': 0, 'val3': 0},
 {'key1': '2018', 'key2': '40-50', 'val1': 77, 'val2': 0, 'val3': 0},
 {'key1': '2018', 'key2': '50 ', 'val1': 88, 'val2': 0, 'val3': 3000}]

By the way, for python 3.9 , you can instead use | operator to simplify the code a little bit:

l2 = {(d['key1'], d['key2']): d for d in l2}

output = [d | {'val2': 0, 'val3': 0} for d in l1]
output = [d | l2.get((d['key1'], d['key2']), {}) for d in output]