Python: detectar duplicados usando un conjunto

Question

Tengo una gran cantidad de objetos que necesito almacenar en la memoria para procesarlos en Python. Específicamente, estoy tratando de eliminar duplicados de un gran conjunto de objetos. Quiero considerar dos objetos "iguales" si una determinada variable de instancia en el objeto es igual. Entonces, asumí que la manera más fácil de hacer esto sería insertar todos mis objetos en un conjunto, y anular el método __hash__ para que tenga el hash de la variable de instancia que me preocupa.

Por lo tanto, como una prueba He intentado lo siguiente:

class Person: 
    def __init__(self, n, a): 
     self.name = n 
     self.age = a 

    def __hash__(self): 
     return hash(self.name) 

    def __str__(self): 
     return "{0}:{1}".format(self.name, self.age) 

myset = set() 
myset.add(Person("foo", 10)) 
myset.add(Person("bar", 20)) 
myset.add(Person("baz", 30)) 
myset.add(Person("foo", 1000)) # try adding a duplicate 

for p in myset: print(p) 

Aquí, defino una clase Person, y cualquiera de los dos casos de Person con el mismo name variables deben ser iguales, independientemente del valor de cualquier otra variable de instancia. Por desgracia, esto da salida:

baz:30 
foo:10 
bar:20 
foo:1000 

Tenga en cuenta que foo aparece dos veces, por lo que este programa no se dio cuenta duplicados. Sin embargo, la expresión hash(Person("foo", 10)) == hash(Person("foo", 1000)) es True. Entonces, ¿por qué esto no detecta correctamente los objetos duplicados Person?

Answer 1

Olvidó tambiéndefine __eq__().

Si una clase no define un método __cmp__() o __eq__() no debería definir una operación __hash__() tampoco; si define __cmp__() o __eq__() pero no __hash__(), sus instancias no serán utilizables en colecciones hash. Si una clase define objetos mutables e implementa un método __cmp__() o __eq__(), no debería implementar __hash__(), ya que las implementaciones de colección hashable requieren que el valor hash de un objeto sea inmutable (si el valor hash del objeto cambia, estará en el cubo hash incorrecto).

Answer 2

La función hash no es suficiente para distinguir el objeto que tiene que implementar la función de comparación (es decir, __eq__).

Answer 3

Un conjunto obviamente tendrá que lidiar con colisiones hash. Si el hash de dos objetos coincide, el conjunto los comparará con el operador == para asegurarse de que son realmente iguales. En su caso, esto solo arrojará True si los dos objetos son el mismo objeto (la implementación estándar para las clases definidas por el usuario).

Resumen de la historia larga: Defina también __eq__() para que funcione.

Answer 4

También necesita el método __ eq __().

Answer 5

Una función hash efectivamente dice "A tal vez es igual a B" o "A no es igual a B (seguro)".

Si dice "quizás sea igual", entonces la igualdad debe verificarse de todos modos para estar seguro, por lo que también debe implementar __eq__.

Sin embargo, definir __hash__ acelerará significativamente haciendo que "A no sea igual B (seguro)" una operación O(1).

La función hash debe sin embargo siempre seguir la "regla hash":

• "regla hash": cosas iguales deben hash en el mismo valor
• (justificación: o bien diríamos "A no es igual a B (con certeza)" cuando ese no es el caso)

Por ejemplo, podría hash todo por def __hash__(self): return 1. Esto seguiría siendo correcto, pero sería ineficiente porque tendría que marcar __eq__ cada vez, lo que puede ser un proceso largo si tiene estructuras de datos grandes y complicadas (por ejemplo, con listas grandes, diccionarios, etc.).

Tenga en cuenta que técnicamente sigue la "regla hash" haciendo esto ignorando la edad en su implementación def __hash__(self): return self.name. Si Bob es una persona de 20 años y Bob es otra persona de 30 años y son personas diferentes (probablemente a menos que se trate de algún tipo de programa de seguimiento de personas a lo largo del tiempo), entonces Harán hash al mismo valor y tendrán que ser comparados con __eq__. Esto está perfectamente bien, pero lo implementaría así:

def __hash__(self): 
    return hash((self.name, self.age)) 

Tenga en cuenta que su camino sigue siendo el correcto. Sin embargo, habría sido un error de codificación usar hash((self.name, self.age)) en un mundo donde Person("Bob", age=20) y Person("Bob", age=30) eran en realidad la misma persona, porque la función hash diría que son diferentes mientras que la función igual no (pero se ignoraría).