检查Python字典的形状和键是否相同

Question

对于像 x = {'a': 1, 'b': 2} 这样的单层字典，问题比较简单，已经在StackOverflow上有解答了（如何检查两个字典的键是否完全相同？），但是对于嵌套字典呢？

举个例子，y = {'a': {'c': 3}, 'b': {'d': 4}} 这个字典有键 'a' 和 'b'，但我想把它的结构和另一个嵌套字典 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

这是一个替代的答案，可以使用ANY。这在你只想检查某个特定深度的时候非常有用。

ANY = "ANY"

def shape_equal(d1, d2):
    if isinstance(d1, dict) and isinstance(d2, dict):
        for k in d1:
            if k not in d2:
                return False
            if not shape_equal(d1[k], d2[k]):
                return False
            
        for k in d2:
            if k not in d1:
                return False
        return True
    elif isinstance(d1, dict) and d2 == ANY:
        return True
    elif not isinstance(d1, dict) and not isinstance(d2, dict):
        return True
    else:
        return False

然后进行测试

assert shape_equal({"a": 1, "b": 2}, {"a": 1, "b": 2}) == True
assert shape_equal({"a": 1, "b": {"foo": "bar"}}, {"a": 1, "b": {
    "foo": 33
}}) == True
assert shape_equal({"a": 1, "b": {"foo": "bar"}}, {"a": 1, "b": ANY}) == True
assert shape_equal({"a": 1, "b": 2}, {"a": 1, "b": {"foo": "bar"}}) == False

Answer 2

为了对比目前已有的两个答案，首先我们需要导入 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!
'''

现在我们来测试这两个选项，首先用 Python 3.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（一个测试版）上测试的结果也是差不多：

>>> 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 3

我喜欢nneonneo的回答，它应该比较快，但我想要一种不创建额外不必要数据结构的方法（我最近在学习Python中的内存碎片问题）。这可能会更快，也可能不会。

（编辑：剧透！）

速度提升了不少，所以在所有情况下都更值得选择，具体可以看其他分析的回答。

不过，如果要处理很多这些数据并且遇到内存问题，采用这种方法可能会更好。

实现

这个方法应该可以在Python 3中使用，如果你把keys改成viewkeys，也许在2.7中可以用，但绝对不能在2.6中使用。它依赖于字典的键有类似集合的视图：

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 4

这段话的意思是，它会生成两个字典的副本，并且把那些不是字典的值去掉，然后再进行比较。

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)