Check that Python dicts have same shape and keys

Question

For single layer dicts like x = {'a': 1, 'b': 2} the problem is easy and answered on SO (Pythonic way to check if two dictionaries have the identical set of keys?) but what about nested dicts?

For example, y = {'a': {'c': 3}, 'b': {'d': 4}} has keys 'a' and 'b' but I want to compare its shape to another nested dict structure like z = {'a': {'c': 5}, 'b': {'d': 6}} which has the same shape and keys (different values is fine) as y. w = {'a': {'c': 3}, 'b': {'e': 4}} would have keys 'a' and 'b' but on the next layer in it differs from y because w['b'] has key 'e' while y['b'] has key 'd'.

Want a short/simple function of two arguments dict_1 and dict_2 and return True if they have same shape and key as described above, and False otherwise.

Answer 1

This provides a copy of both dictionaries stripped of any non-dictionary values, then compares them:

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)

Answer 2

I liked nneonneo's answer, and it should be relatively fast, but I want something that didn't create extra unnecessary data structures (I've been learning about memory fragmentation in Python). This may or may not be as fast or faster.

(EDIT: Spoiler!)

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

But if dealing with lots and lots of these and having memory problems, it is likely to be preferable to do it this way.

Implementation

This should work in Python 3, maybe 2.7 if you translate keys to viewkeys, definitely not 2.6. It relies on the set-like view of the keys that dicts have:

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.

Edit updated to reduce redundant type check, now even more efficient.

Testing

To check:

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'}}}))

Prints:

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