检查Python dict是否具有相同的形状和键

Question

对于像x = {'a': 1, 'b': 2}这样的单层dict，问题很容易解决，所以（Pythonic way to check if two dictionaries have the identical set of keys?）但是嵌套dict呢？

例如，y = {'a': {'c': 3}, 'b': {'d': 4}}有键'a'和'b'，但我想将其形状与另一个嵌套的dict结构（如z = {'a': {'c': 5}, 'b': {'d': 6}}）进行比较，后者具有与y相同的形状和键（不同的值很好）。w = {'a': {'c': 3}, 'b': {'e': 4}}有键'a'和'b'，但在下一层上它与y不同，因为w['b']有键'e'，而y['b']有键'd'。

想要一个由两个参数dict_1和dict_2组成的短/简单函数，如果它们具有上述相同的形状和键，则返回True，否则返回False。

Answer 1

要分析当前存在的两个答案，首先让导入timeit：

import timeit

现在我们需要设置代码：

setup = '''
import copy

def getshape(d):
    if isinstance(d, dict):
        return {k:getshape(d[k]) for k in d}
    else:
        # Replace all non-dict values with None.
        return None

def nneo_shape_equal(d1, d2):
    return getshape(d1) == getshape(d2)

def aaron_shape_equal(d1,d2):
    if isinstance(d1, dict) and isinstance(d2, dict):
        return (d1.keys() == d2.keys() and 
                all(aaron_shape_equal(d1[k], d2[k]) for k in d1.keys()))
    else:
        return not (isinstance(d1, dict) or isinstance(d2, dict))

class Vividict(dict):
    def __missing__(self, key):
        value = self[key] = type(self)()
        return value

d = Vividict()

d['foo']['bar']
d['foo']['baz']
d['fizz']['buzz']
d['primary']['secondary']['tertiary']['quaternary']

d0 = copy.deepcopy(d)
d1 = copy.deepcopy(d)
d1['primary']['secondary']['tertiary']['extra']
# d == d0 is True
# d == d1 is now False!
'''

现在让我们测试一下这两个选项，首先使用Python3.3！

>>> timeit.repeat('nneo_shape_equal(d0, d); nneo_shape_equal(d1,d)', setup=setup)
[36.784881490981206, 36.212246977956966, 36.29759863798972]

看起来我的解决方案花费了2/3到3/4的时间，使其速度超过1.25倍。

>>> timeit.repeat('aaron_shape_equal(d0, d); aaron_shape_equal(d1,d)', setup=setup)
[26.838892214931548, 26.61037168605253, 27.170253590098582]

在我自己编译的Python 3.4（alpha）版本上：

>>> timeit.repeat('nneo_shape_equal(d0, d); nneo_shape_equal(d1,d)', setup=setup)
[272.5629618819803, 273.49581588001456, 270.13374400604516]
>>> timeit.repeat('aaron_shape_equal(d0, d); aaron_shape_equal(d1,d)', setup=setup)
[214.87033835891634, 215.69223327597138, 214.85333003790583]

还是差不多的比例。两者之间的时间差很可能是因为我在没有优化的情况下自行编译了3.4。

感谢所有读者！

Answer 2

我喜欢nneonneo的答案，而且应该比较快，但我希望不创建额外的不必要的数据结构（我一直在学习Python中的内存碎片）。这可能快，也可能不快。

（编辑：剧透！）

Faster by a decent enough margin to make it preferable in all cases, see the other analysis answer.

但是，如果要处理很多这样的问题，并且有内存问题，那么最好这样做。

实施

这在Python 3中应该有效，如果将keys转换为viewkeys，可能是2.7，当然不是2.6。它依赖于dict拥有的键的集合视图：

def sameshape(d1, d2):
    if isinstance(d1, dict):
        if isinstance(d2, dict):
            # then we have shapes to check
            return (d1.keys() == d2.keys() and
                    # so the keys are all the same
                    all(sameshape(d1[k], d2[k]) for k in d1.keys()))
                    # thus all values will be tested in the same way.
        else:
            return False # d1 is a dict, but d2 isn't
    else:
        return not isinstance(d2, dict) # if d2 is a dict, False, else True.

编辑更新以减少冗余类型检查，现在更有效。

测试

检查：

print('expect false:')
print(sameshape({'foo':{'bar':{None:None}}}, {'foo':{'bar':{None: {} }}}))
print('expect true:')
print(sameshape({'foo':{'bar':{None:None}}}, {'foo':{'bar':{None:'foo'}}}))
print('expect false:')
print(sameshape({'foo':{'bar':{None:None}}}, {'foo':{'bar':{None:None, 'baz':'foo'}}}))

印刷品：

expect false:
False
expect true:
True
expect false:
False

Answer 3

这将提供两个词典的副本，其中不包含任何非词典值，然后对它们进行比较：

def getshape(d):
    if isinstance(d, dict):
        return {k:getshape(d[k]) for k in d}
    else:
        # Replace all non-dict values with None.
        return None

def shape_equal(d1, d2):
    return getshape(d1) == getshape(d2)