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, ], }, ], } 

這是如何運行測試的例子：（字典更新不工作，只是一個存根函數）

 

    import itertools 

    def mergeStuff(default, override): 
     # This doesn't work 
     result = dict(default) 
     result.update(override) 
     return result 

    def main(): 
     for override, answer in itertools.izip(_OVERRIDES, _ANSWERS): 
      result = mergeStuff(_DEFAULT, override) 
      print('ANSWER: %s' % (answer)) 
      print('RESULT: %s\n' % (result)) 

Answer 1

你不能做到這一點的「迭代」，你需要一個遞歸過程是這樣的：

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 

Answer 2

如果你知道一個結構始終是一個子集然後只需迭代超集，然後在O（n）時間內，您可以通過元素檢查它是否存在於子集中，如果不存在，則放在那裏。據我所知，除了手動元素檢查以外，沒有其他的方法可以做到這一點。正如我所說，這並不差，因爲它可以用O（n）的複雜性來完成。

Answer 3

dict.update()是你需要的。但它會覆蓋原始字典，因此如果要保留原始字典，請複製原始字典。

Answer 4

如果你希望你的代碼要快，不要複製像瘋了似的

你真的不需要合併兩個字。你可以鏈接它們。

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/