Трехсторонний словарь глубокого слияния в Python

Question

Я хотел бы объединить два словаря A и B , зная общее предыдущее состояние C обоих словарей.Мне нужно, чтобы слияние происходило и в подчиненных.В случае реального конфликта мне нужно вызвать исключение.

1 - В следующем примере метод слияния должен понимать, что A и B редактировали разные элементы, и, следовательно, слияние не должно вызывать конфликт

C = {"x": 0, "y": 0}
A = {"x": 1, "y": 0} # Edit x, but not y
B = {"x": 0, "y": 1} # Edit y, but not x
# merge(A, B, C) => {"x": 1, "y": 1}

2 - функция должна иметь возможность обрабатывать новые и удаленные элементы

C = {"x": 0}
A = {"x": 0, "y": 0} # Add y, keep x untouched
B = {}               # Delete x
# merge(A, B, C) => {"y": 0}

3 - функция должна вызывать исключение при возникновении реального конфликта

C = {"x": 0}
A = {"x": 1}         # Edit x 
B = {"x": 2}         # Also edit x
# merge(A, B, C) => raise Exception

C = {"x": 0}
A = {"x": 1}         # Edit x 
B = {}               # Delete x
# merge(A, B, C) => raise Exception

4 - функция должна работать рекурсивно

C = {"deeper": {"x": 0, "y": 0}}
A = {"deeper": {"x": 1, "y": 0}} # Edit deeper["x"], but not deeper["y"]
B = {"deeper": {"x": 0, "y": 1}} # Edit deeper["y"], but not deeper["x"]
# merge(A, B, C) => {"deeper": {"x": 1, "y": 1}}

Каков наилучший подход для реализации такой функции слияния?

Answer 1

Вы можете преобразовать все элементы dict в наборы, использовать пересечение ключей от симметричных разностей в C, чтобы найти конфликты, и использовать объединение пересечения 3 наборов (общие элементы) и различий в C, чтобы получитьслияния.Рекурсивно объединяйте субдикаты, общие для A, B и C, конвертируйте субдикаты в кортежи пар элементов, чтобы их можно было хэшировать и преобразовывать в наборы, а затем конвертируйте их обратно в диктовки после слияния.

РЕДАКТИРОВАТЬ: В случае если значения dict являются не подлежащими изменению объектами, такими как набор, вам придется сериализовать значения (я рекомендую использовать pickle в качестве сериализатора, поскольку он имеет встроенную поддержку Python), прежде чем вы сможете преобразовать элементы dict вустановить и десериализовать их после слияния:

import pickle

def merge(a, b, c):
    # recursively merge sub-dicts that are common to a, b and c
    for k in a.keys() & b.keys() & c.keys():
        if all(isinstance(d.get(k), dict) for d in (a, b, c)):
            a[k] = b[k] = c[k] = merge(a[k], b[k], c[k])
    # convert sub-dicts into tuples of item pairs to allow them to be hashable
    for d in a, b, c:
        for k, v in d.items():
            if isinstance(v, dict):
                d[k] = tuple(v.items())
    # convert all the dict items into sets
    set_a, set_b, set_c = (set((k, pickle.dumps(v)) for k, v in d.items()) for d in (a, b, c))
    # intersect keys from the symmetric set differences to c to find conflicts
    for k in set(k for k, _ in set_a ^ set_c) & set(k for k, _ in set_b ^ set_c):
        # it isn't really a conflict if the new values of a and b are the same
        if a.get(k) != b.get(k) or (k in a) ^ (k in b):
            raise ValueError("Conflict found in key %s" % k)
    # merge the dicts by union'ing the differences to c with the common items
    d = dict(set_a & set_b & set_c | set_a - set_c | set_b - set_c)
    # convert the tuple of items back to dicts for output
    for k, v in d.items():
        v = pickle.loads(v)
        if isinstance(v, tuple):
            d[k] = dict(v)
        else:
            d[k] = v
    return d

, чтобы:

C = {"x": 0, "y": 0}
A = {"x": 1, "y": 0} # Edit x, but not y
B = {"x": 0, "y": 1} # Edit y, but not x
print(merge(A, B, C))
C = {"x": 0}
A = {"x": 0, "y": 0} # Add y, keep x untouched
B = {}               # Delete x
print(merge(A, B, C))
C = {"x": 0}
A = {"x": 1}  # Edit x
B = {"x": 1}  # Edit x with the same value
print(merge(A, B, C))
C = {"deeper": {"x": 0, "y": {3, 4}}}
A = {"deeper": {"x": {1, 2}, "y": {4, 3}}} # Edit deeper["x"], but not deeper["y"]
B = {"deeper": {"x": 0, "y": 1}} # Edit deeper["y"], but not deeper["x"]
print(merge(A, B, C))
C = {"deeper": 1}
A = {"deeper": {"x": 0, "y": 1}} # Edit deeper and turn it into a dict
B = {"deeper": 1, "x": 2} # Add x, keep deeper untouched
print(merge(A, B, C))
C = {"deeper": {"x": 0, "y": 1}}
A = {"deeper": {"x": 0, "y": 1}} # Keep deeper untouched
B = {"deeper": 1} # Turn deeper into a scalar
print(merge(A, B, C))

выдало:

{'x': 1, 'y': 1}
{'y': 0}
{'x': 1}
{'deeper': {'x': {1, 2}, 'y': 1}}
{'deeper': {'x': 0, 'y': 1}, 'x': 2}
{'deeper': 1}

, а:

C = {"x": 0}
A = {"x": 1}         # Edit x
B = {"x": 2}         # Edit x with a different value
print(merge(A, B, C))

повысит:

ValueError: Conflict found in key x

и:

C = {"deeper": {"x": 0, "y": 1}}
A = {"deeper": {"x": 0, "y": 2}} # Edit deeper["y"], but not deeper["x"]
B = {"deeper": 1} # Turn deeper into a scalar
print(merge(A, B, C))

повысит:

ValueError: Conflict found in key deeper

Answer 2

попробуйте функцию, которая рекурсивно проверяет ваши случаи и дает сбой (вызывает ошибку value), если ни один из них не выполняется.

Я полагаю, что это удовлетворит ваши дела

def three_way_merge(Origin, Dict_A, Dict_B):
    newdict = dict()
    for key, value in Origin.items():
        if isinstance(value, dict):  # handle recursion
            newdict[key] = three_way_merge(Origin[key], Dict_A[key], Dict_B[key])
        elif key not in Dict_A.keys() and Dict_B[key] == value:
            pass
        elif key not in Dict_B.keys() and Dict_A[key] == value:
            pass
        elif Dict_A[key] == value and Dict_B[key] == value:
             newdict[key] = value
        elif Dict_A[key] == value and Dict_B[key] != value:
             newdict[key] = Dict_B[key]
        elif Dict_A[key] != value and Dict_B[key] == value:
             newdict[key] = Dict_A[key]
        elif Dict_A[key] == Dict_B[key]:
             newdict[key] = Dict_A[key]
        else: # check for a conflict with this key
            raise ValueError('conflict occured with {} \n {} and {} both changed'.format(key, Dict_A[key], Dict_B[key]))
    newdict.update(add_missing_keys(Dict_A, Origin, Dict_B))
    newdict.update(add_missing_keys(Dict_B, Origin, Dict_A))
    return newdict    

def add_missing_keys (Dict_A, Origin, Dict_B):
    newdict = dict()
    for key, value in Dict_A.items():
        if key not in Origin.keys():
            if key not in Dict_B.keys() or Dict_B[key] == value:
                newdict[key] = value
            else:
                raise ValueError('conflict occured with {} \n {} and {} both changed'.format(key, Dict_A[key], Dict_B[key]))
    return newdict

print(three_way_merge({'x':0, 'y':0}, {'x':1, 'y':0}, {'x':0, 'y':2}))     # returns {'x':1, 'y':2}
print(three_way_merge({'x':0}, {'x':0, 'y':0}, {}))    # returns {'y':0}
print(three_way_merge({'x':0}, {'x':1}, {'x':1}))    # returns {'x':1}
print(three_way_merge({"deeper": {"x": 0, "y": 0}},{"deeper": {"x": 1, "y": 0}},{"deeper": {"x": 0, "y": 2}})) # returns {'deeper': {'x': 1, 'y': 2}}
print(three_way_merge({'x':0}, {'x':1}, {'x':2})) # raises valueerror
print(three_way_merge({'x':0}, {'x':1}, {}))  # raises keyerror