Python：合并两个任意数据结构

Question

我希望高效地合并两个（相当任意的）数据结构：一个表示一组默认值，另一个表示覆盖。示例数据如下。（天真地迭代结构是可行的，但速度非常慢。）关于处理这种情况的最佳方法的想法？在

_DEFAULT   = { 'A': 1122, 'B': 1133, 'C': [ 9988, {            'E': [ { 'F': 6666,            },       ], }, ], }

_OVERRIDE1 = {            'B': 1234, 'C': [ 9876, { 'D': 2345, 'E': [ { 'F': 6789, 'G': 9876, }, 1357, ], }, ], }
_ANSWER1   = { 'A': 1122, 'B': 1234, 'C': [ 9876, { 'D': 2345, 'E': [ { 'F': 6789, 'G': 9876, }, 1357, ], }, ], }

_OVERRIDE2 = {                       'C': [ 6543, {            'E': [ {            'G': 9876, },       ], }, ], }
_ANSWER2   = { 'A': 1122, 'B': 1133, 'C': [ 6543, {            'E': [ { 'F': 6666, 'G': 9876, },       ], }, ], }

_OVERRIDE3 = {            'B': 3456, 'C': [ 1357, { 'D': 4567, 'E': [ { 'F': 6677, 'G': 9876, }, 2468, ], }, ], }
_ANSWER3   = { 'A': 1122, 'B': 3456, 'C': [ 1357, { 'D': 4567, 'E': [ { 'F': 6677, 'G': 9876, }, 2468, ], }, ], }

以下是如何运行测试的示例： （字典更新不起作用，只是一个存根函数。）

^{pr2}$

Answer 1

If you want your code to be fast, don't copy like crazy

你不需要合并两个dict。你可以把它们拴起来。在

提供了一个ChainMap类，用于快速链接多个映射，以便将它们视为单个单元。它通常比创建新字典并运行多个update（）调用快得多。

class ChainMap(UserDict.DictMixin):
"""Combine multiple mappings for sequential lookup"""

    def __init__(self, *maps):
        self._maps = maps

    def __getitem__(self, key):
        for mapping in self._maps:
            try:
                return mapping[key]
            except KeyError:
                pass
        raise KeyError(key)

def main():
    for override, answer in itertools.izip( _OVERRIDES, _ANSWERS ):
       result = ChainMap(override, _DEFAULT)

• http://docs.python.org/dev/library/collections#chainmap-objects
• http://code.activestate.com/recipes/305268/

Answer 2

如果你知道一个结构总是另一个结构的子集，那么只要迭代超集，在O（n）时间内，你就可以逐个元素检查它是否存在于子集中，如果不存在，就把它放在那里。据我所知，除了手动逐个检查之外，没有什么神奇的方法可以做到这一点。正如我所说，这并不坏，因为它可以用O（n）复杂度来完成。在

Answer 3

您不能通过“迭代”来实现这一点，您需要这样的递归例程：

def merge(a, b):
    if isinstance(a, dict) and isinstance(b, dict):
        d = dict(a)
        d.update({k: merge(a.get(k, None), b[k]) for k in b})
        return d

    if isinstance(a, list) and isinstance(b, list):
        return [merge(x, y) for x, y in itertools.izip_longest(a, b)]

    return a if b is None else b