是否有用于表示数据增量的标准算法或库？

Question

我有一个 Python 结构相当复杂的字典——多层嵌套值，其中一些是字典，一些是列表。我想以一种易于应用的紧凑方式表示对数据的更改。

对于仅包含字典的值，似乎并不太难 — 您可以制作一个反映主要数据结构的字典，但仅包含其父项的修改键，然后调用略微修改的 .update()检测逻辑删除值，以防您需要完全删除密钥。

但是涉及到列表，它似乎变得更加棘手。看来我需要想出某种需要考虑很多情况的自定义寻址方案——你不能天真地使用列表索引作为键，因为你需要支持，例如在元素 2 和 3 之间插入的同时删除元素 5。

此外，如果列表不限于叶子，则在修改列表元素的同时指定对列表中包含的项目的更改是很棘手的。

是否有一个 Python 库来标准化这样的东西？还是实施起来相对理智的标准 algorithm/approach？

作为参考，这里有一个函数实现了我正在寻找的纯字典数据：

def update(d, u):
    for k, v in u.items():
        if v == 'del':
            del d[k]
        elif isinstance(v, collections.abc.Mapping):
            d[k] = update(d.get(k, {}), v)
        else:
            d[k] = v
    return d

>>> d = {1: 2, 3: {4: 5, 6: 7}}
>>> delta = {3: {4: 'del', 6: 8}, 9: 10}
>>> update(d, delta)
{1: 2, 3: {6: 8}, 9: 10}

Answer 1

从用户的角度来看，我认为列表索引并不像您所说的那么严重。只有在所有操作完成后，索引才会发生变化。在列表操作期间使用旧索引。

从实现的角度来看，我们在处理列表索引时必须格外小心。我们可以做的是通过迭代维护一个“索引增量 i”，而不是修改 l[k]，我们修改 l[k+i].

这里我将使用一个字典作为增量，以列表索引为键，这三个可能的值：

'del' 删除该索引处的项目；
('insert', v) 在此索引之前插入值 v；和
v修改该索引处的值为v。

注意'del'和v是互斥的，但是'insert'是可以累加的：可以在同一个索引处插入多个元素，也可以插入索引和之前的元素删除或修改该索引处的元素。我们希望我们的 dict delta 能够将一个键映射到多个更新；即，将键映射到列表。

from operator import itemgetter

def update(d, u):
    if isinstance(d, dict):
        return update_dict(d, u)
    elif isinstance(d, list):
        return update_list(d, u)

def update_dict(d, u):
    for k, v in u.items():
        if v == 'del':
            del d[k]
        elif isinstance(v, dict):
            d[k] = update(d.get(k, {}), v)
        else:
            d[k] = v
    return d

def update_list(d, u):
    i = 0
    for k, v in sorted(u.items(), key=itemgetter(0)):
        if isinstance(v, list):
            for x in v:
                i = update_list_once(d, i, k, x)
        else:
            i = update_list_once(d, i, k, v)
    return d

def update_list_once(d, i, k, v):
    if v == 'del':
        del d[k+i]
        i -= 1
    elif isinstance(v, tuple) and len(v) == 2 and v[0] == 'insert':
        d.insert(k+i, v[1])
        i += 1
    else:
        if isinstance(v, dict):
            d[k + i] = update(d[k+i], v)
        else:
            d[k+i] = v
    return i

测试：

d = {1: 2, 3: {4: [0, 1, 2, 3, 4, 5], 6: 7}}
delta = {3: {4: {0: 'fizzbuzz', 3: 'fizz', 4: [('insert', 3.5), 4.001], 5: 'buzz'}, 6: 8}, 9: 10}
d = update(d, delta)
print(d)
# {1: 2, 3: {4: ['fizzbuzz', 1, 2, 'fizz', 3.5, 4.001, 'buzz'], 6: 8}, 9: 10}

Answer 2

这是字典 class 的修改版本，允许通过多个键对值进行寻址：

class MultiKeyDict(dict):
    def __setitem__(self, __k, __v):
        super().__setitem__(__k, __v)
        if isinstance(__k, (tuple, list)):
            if not hasattr(self, "extmap"): # This could be done in the __init__ function but I did it here instead to avoid overriding it for simplicity
                self.extmap = {}
            self.extmap.update(dict.fromkeys(__k, __k))

    def __getitem__(self, __k):
        if __k in self.keys():
            return super().__getitem__(__k)
        elif hasattr(self, "extmap"):
            if __k in self.extmap.keys():
                return super().__getitem__(self.extmap.get(__k))
        return super().__getitem__(__k) # Call the super function again to trigger the correct exception

它只存储一次实际值，如果提供的是普通 str 键，或者如果提供的键是元组或列表，则存储在元组键下。额外的键只是保存在另一个字典中，用于重定向到值本身保存在其下的键。

这在技术上是对@Stef 回答的回应，但我还不能 post 回复，因为我刚刚创建了我的 Stack Overflow 帐户，并且最低要求是 50 个信誉点。

是否有用于表示数据增量的标准算法或库？

Is there a standard algorithm or library for representing data deltas?

python

algorithm