Utilisation de la `` == opérateur dictionnaires circulairement définis

Question

Python permet dictionnaires à comparer avec ==

import copy 

child = {'name': 'child'} 
parent_1 = {'name': 'parent', 'child': child} 
parent_2 = copy.deepcopy(parent_1) 
print(parent_1 == parent_2) 

Prints True, comme vous attendez. Python permet également aux dictionnaires de se référer les uns aux autres circulairement.

child = {'name': 'child'} 
parent_1 = {'name': 'parent', 'child': child} 
child['parent'] = parent_1 # Create the circular reference 

Cependant, en essayant d'utiliser l'opérateur == sur les dictionnaires de références circulaires soulève une erreur.

parent_2 = copy.deepcopy(parent_1) 
print(parent_1 == parent_2) 

Retours

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 

Comment puis-je vérifier deux dictionnaires avec des références circulaires pour l'égalité?

Answer 1

Vous devez définir ce que vous voulez dire par égal. Normalement, "égal" pour les dictionnaires signifie "toutes les paires clé/valeur sont les" égales ". Si un dictionnaire a une référence à lui-même, cette définition de l'égalité peut conduire à une définition récursive, c'est-à-dire a == b ss a == b.

Prenez cet exemple simple:

a = {}; a['item'] = a 
b = {}; b['item'] = b 

sont-a et b égaux? Afin de savoir que, vous devez d'abord savoir si a et b sont égaux ...

Vous pouvez créer un equal spécial qui ressemble à ceci:

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 

Answer 2

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) 

Si vous utilisez copy.copy au lieu de copy.deepcopy, il fonctionne sans erreur.

The difference between shallow and deep copying is only relevant for compound objects (objects that contain other objects, like lists or class instances):

• A shallow copy constructs a new compound object and then (to the extent possible) inserts references into it to the objects found in the original.

• A deep copy constructs a new compound object and then, recursively, inserts copies into it of the objects found in the original.

https://docs.python.org/2/library/copy.html

Il est peut-être un problème de stockage, que l'utilisation deepcopy() force récursion réelle, alors que la copie() peut simplement vérifier les références

Answer 3

Vous devez écrire votre propre procédure de comparaison qui prend quatre arguments, deux choses à comparer, et deux piles de dictionnaires/listes (une pour chaque chose étant comparée).

Si l'une ou l'autre chose comparée est contenue dans la pile correspondante, renvoyez vrai si elles sont toutes deux dans leur propre pile dans la même position, et false sinon.

Sinon, s'il s'agit de dictionnaires, assurez-vous qu'ils ont les mêmes ensembles de clés (sinon revenez faux), et recursez sur chaque valeur, en ajoutant les dictionnaires aux deux piles. S'il s'agit de listes, assurez-vous qu'elles ont la même longueur (ou renvoyez false) et récurssez sur chaque paire de membres, en ajoutant les listes aux deux piles. Pour commencer, appelez la procédure récursive avec les objets comparés et deux piles vides.Vous pouvez envelopper ceci dans une autre procédure qui prend seulement deux 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 

Exemple d'utilisation:

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

Answer 4

Il me vint alors que je faisais quelque chose d'autre que les poignées de module pickle dictionnaires récursives et autres. Dans cet esprit cela pourrait fonctionner pour vous:

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