What would be a clean and efficient way to find object structural similarity in python? [closed]

Question

Consider few python objects containing simple types like strings/unicode , integers, lists,dicts.

a = { 'name': 'John'}
b = {'name':'Mathew'}
c = {'name':345}

Here a is structurally similar to b, but not to c, as the value in c is an integer.

More complex example:

a = { 'candidates': [ {'name':'John','age':23},{'name':'Matt','age':23}],'class':{'num':4,'year':2005}}

b = { 'candidates': [ {'name':'Mary','age':33},{'name':'Skipper','age':24}],'class':{'num':14,'year':2006}}

Though a and b have different values, they have same types of values at same keys, which holds true for nested values too.

What would be a good method to find that two such python objects are similar ? Assuming the lists will have uniform types of elements.

One idea I have in mind is to recursively compare type of members of objects.

I want to know if there are easier hacks or python modules that do this ?

Answer 1

One solutions is indeed a recursive one where you compare types:

def compare(v1, v2):
    if not type(v1) == type(v2):
        return False

    if isinstance(v1, dict):
        return compare(sorted(v1.items()), sorted(v2.items()))

    elif isinstance(v1, (list, tuple)):
        if not len(v1) == len(v2):
            return False
        return all(compare(a, b) for a, b in zip(v1, v2))

    return True

This function will work in all the cases you posted. It will however always return False if any of the lists vary in length between structures. Here are some results:

>>> compare({'name':'Mathew'}, {'name':'John'})
True
>>> compare({'name':'Mathew'}, {'name':2})
False
>>> compare([1, 1], [2, 2])
True
>>> compare([1, 2], [1])
False
>>> compare([1, "a"], [2, "b"])
True

If you wanted the fourth one to pass you could separate out the list clause and only compare the first item, this also assumes empty lists has the correct type:

elif isinstance(v1, list):

    if (not v1) or (not v2):
        return True

    return compare(v1[0], v2[0])

You have to be really careful when doing this sort of thing in a language that is as dynamic as python. Its easy to get "wrong" results if your input varies slightly from the structure you expect. For example if the structures contains sets they will only be compared on types, not content.