python - 根据条件合并两个字典列表

Question

我有两个字典列表，当 USA 和 GOOG 相同时，我需要合并它们。

list1 = 
[{'USA': 'Eastern', 
  'GOOG': '2019', 
  'Up': {'Upfront': 45}, 
  'Right': {'Upfront': 12}}, 

 {'USA': 'Western', 
  'GOOG': '2019', 
  'Up': {'Upfront': 10}, 
  'Right': {'Upfront': 15}}]

list2=
[{'USA': 'Western', 
  'GOOG': '2019', 
  'Down': {'Downback': 35}, 
  'Right': {'Downback': 25}}, 

 {'USA': 'Eastern', 
  'GOOG': '2018', 
  'Down': {'Downback': 15}, 
  'Right': {'Downback': 55}}]

由于 USA 和 GOOG 对 list1 中的第二个元素和 list2 中的第一个元素具有相同的值，所以他们应该合并。预期结果如下——

Result = 
[{'USA': 'Eastern', 
  'GOOG': '2019', 
  'Up': {'Upfront': 45}, 
  'Right': {'Upfront': 12}}, 

 {'USA': 'Western', 
  'GOOG': '2019', 
  'Up': {'Upfront': 10}, 
  'Down': {'Downback': 35}, 
  'Right': {'Upfront': 15, 'Downback': 25}},

 {'USA': 'Eastern', 
  'GOOG': '2018', 
  'Down': {'Downback': 15}, 
  'Right': {'Downback': 55}}]

我们如何为此编写通用代码。我尝试使用 defaultdict , 但不知道如何连接任意数量的其余字典。

我的尝试:

from collections import defaultdict
dics = list1+list2

for dic in dics:
    for key, val in dic.items():
        dd[key].append(val)            

for dic in dics:
    for key, val in dic.items(): 
        dd[key].append(val)

Answer 1

您需要执行两个算法任务:找到 USA 和 GOOGL 具有相同值的记录，然后加入，如果两个记录中存在相同的键，则合并它们的值.

第一种方法的天真方法是使用一个 for 循环来迭代 list1 的值，并且对于每个值，迭代 list2 的所有值 - 两个单独的循环不会削减它，你需要两个 < em>嵌套 for 循环:

for element in list1:
    for other_element in list2:
        if ...:
            ...

虽然这种方法可行，并且适用于小型列表(例如 <1000 条记录)，但它所花费的时间和资源与列表大小的平方成正比 - 也就是说，列表接近 ~1000 个项目，我们正在谈论 100 万次迭代。如果列表本身是 1.000.000 个项目，计算将进行 1 * 10^12 次比较，这在今天的计算机中根本不可行。

因此，一个不错的解决方案是以比较键用作散列的方式重新创建其中一个列表 - 这是通过将列表复制到字典中来完成的，其中键是您要比较的值，然后在第二个列表上迭代一次。由于字典有固定的时间来查找项目，这将使比较次数与您的列表大小成正比。

您任务的第二部分是比较将一条记录复制到结果列表，并更新结果副本上的键，以便合并任何重复的键。为避免在复制第一条记录时出现问题，我们更安全地使用 Python 的 copy.deepcopy，这将确保子词典与原始记录中的对象不同，并保持隔离。

from copy import deepcopy

def merge_lists(list1, list2):
    # create dictionary from list1:
    dict1 = {(record["GOOG"], record["USA"]): record  for record in list1}

    #compare elements in list2 to those on list1:

    result = {}
    for record in list2:
        ckey = record["GOOG"], record["USA"]
        new_record = deepcopy(record)
        if ckey in dict1:
            for key, value in dict1[ckey].items():
                if key in ("GOOG", "USA"):
                    # Do not merge these keys
                    continue
                # Dict's "setdefault" finds a key/value, and if it is missing
                # creates a new one with the second parameter as value
                new_record.setdefault(key, {}).update(value)

        result[ckey] = new_record

    # Add values from list1 that were not matched in list2:
    for key, value in dict1.items():
        if key not in result:
            result[key] = deepcopy(value)

    return list(result.values())