Using the `==` operator in circular dictionaries
Python allows you to compare dictionaries with ==
import copy
child = {'name': 'child'}
parent_1 = {'name': 'parent', 'child': child}
parent_2 = copy.deepcopy(parent_1)
print(parent_1 == parent_2)
Print True
as you would expect.
Python also allows dictionaries to reference each other in a circular fashion.
child = {'name': 'child'}
parent_1 = {'name': 'parent', 'child': child}
child['parent'] = parent_1 # Create the circular reference
However, attempting to use the operator ==
in circularly referenced dictionaries raises an error.
parent_2 = copy.deepcopy(parent_1) print(parent_1 == parent_2)
Returns
C:\Python34\python.exe -i C:/Users/anon/.PyCharm40/config/scratches/scratch_5
Traceback (most recent call last):
File "C:/Users/anon/.PyCharm40/config/scratches/scratch_5", line 11, in <module>
print(parent_1 == parent_2)
RuntimeError: maximum recursion depth exceeded in comparison
How can I check two dictionaries with circular references for equality?
source to share
You need to define what you mean by equal. Typically “equal” for dictionaries means “all key / value pairs are“ equal. ”If the dictionary has a reference to itself, this definition of equality can result in a recursive definition, ie a == b
iff a == b
.
Let's take this simple example:
a = {}; a['item'] = a
b = {}; b['item'] = b
Are the values a
and b
are equal? To know this, you first need to know if a
and are b
equal ...
You can create a custom equal
one that looks something like this:
def equal(a, b, special=[]):
if not isinstance(a, dict) or not isinstance(b, dict):
return a == b
special = special + [a, b]
set_keys = set(a.keys())
if set_keys != set(b.keys()):
return False
for key in set_keys:
if any(a[key] is i for i in special):
continue
elif any(b[key] is i for i in special):
continue
elif not equal(a[key], b[key], special):
return False
return True
source to share
import copy
child = {'name': 'child'}
parent_1 = {'name': 'parent', 'child': child}
child['parent'] = parent_1 # Create the circular reference
parent_2 = copy.copy(parent_1)
print(parent_1 == parent_2)
If you use copy.copy
instead copy.deepcopy
, it starts without error.
The difference between shallow copy and deep copy only matters for compound objects (objects that contain other objects, such as lists or classes):
• Shallow copy creates a new compound object and then (as far as possible) inserts references into it to the objects found in the original.
• A deep copy creates a new compound object and then recursively inserts copies of the objects found in the original into it.
https://docs.python.org/2/library/copy.html
Possibly a storage issue that using deepcopy () is forcibly recursive, whereas copy () can just check references
source to share
You need to write your own comparison routine that includes four arguments, two things to compare, and two dictionary / list stacks (one for each thing).
If the thing being matched is contained on the matching stack, return true if they are both at the same position on their stack, and false otherwise.
Otherwise, if they are dictionaries, make sure they have the same keyset (otherwise return false) and recurse on each value, adding the dictionaries to the two stacks.
If they are lists, make sure they are the same length (or return false) and iterate over each pair of members, adding the lists on two stacks.
To get it started, call a recursive procedure with comparable things and two empty stacks. You can wrap this in another procedure that only takes two arguments.
def my_compare(a, b):
return my_compare_helper(a, b, [], [])
def my_index(thing, stack):
for i in range(len(stack)):
if thing is stack[i]:
return i
return -1
def my_compare_helper(a, b, a_stack, b_stack):
a_loc = my_index(a, a_stack)
b_loc = my_index(b, b_stack)
if a_loc != -1 or b_loc != -1:
return a_loc == b_loc
a_stack = [a] + a_stack
b_stack = [b] + b_stack
if isinstance(a, list):
if not isinstance(b, list) or len(a) != len(b):
return False
for a_thing, b_thing in zip(a, b):
if not my_compare_helper(a_thing, b_thing, a_stack, b_stack):
return False
return True
if isinstance(a, dict):
if not isinstance(b, dict):
return False
a_keys = sorted(a.keys())
b_keys = sorted(b.keys())
if a_keys != b_keys: # Keys can't be recursive.
return False
for key in a_keys:
if not my_compare_helper(a[key], b[key], a_stack, b_stack):
return False
return True
return a == b
Sample usage:
>>> a = [1, 2, {}]
>>> a[1] = a
>>> a[2]['x'] = a
>>> b = [1, 2, {}]
>>> b[1] = b
>>> b[2]['x'] = b
>>> my_compare(a, b)
True
>>>
source to share
It occurred to me while I was doing something else that the pickle module handles recursive dictionaries and the like. With that in mind, this might work for you:
import copy
import cPickle
a = {}
a['self'] = a
a['list'] = [a, a, 0]
b = copy.deepcopy(a)
print(cPickle.dumps(a) == cPickle.dumps(b))
# True
b['self'] = copy.deepcopy(b)
print(cPickle.dumps(a) == cPickle.dumps(b))
# False
source to share