Pitón. Identidad en conjuntos de objetos. Y hashing

¿Cómo se utilizan __hash__ y __eq__ en la identificación en conjuntos? Por ejemplo, algún código que debería ayudar a resolver algunos rompecabezas de dominó:

class foo(object): def __init__(self, one, two): self.one = one self.two = two def __eq__(self,other): if (self.one == other.one) and (self.two == other.two): return True if (self.two == other.one) and (self.one == other.two): return True return False def __hash__(self): return hash(self.one + self.two) s = set() for i in range(7): for j in range(7): s.add(foo(i,j)) len(s) // returns 28 Why? 

Si uso solo __eq __ () len (s) es igual a 49. Está bien porque como entiendo los objetos (1-2 y 2-1 por ejemplo) no son lo mismo, pero representan el mismo dominó. Así que he añadido la función hash.
Ahora funciona de la manera que quiero, pero no entendí una cosa: el hash de 1-3 y 2-2 debería ser el mismo, así que deberían contar como el mismo objeto y no deberían agregarse al conjunto. ¡Pero lo hacen! Estoy atascado.

La igualdad para fines de __eq__ / conjunto depende de la igualdad como se define por __eq__ . Sin embargo, se requiere que los objetos que comparan igual tengan el mismo valor hash, y es por eso que necesita __hash__ . Vea esta pregunta para una discusión similar.

El hash en sí mismo no determina si dos objetos cuentan como iguales en los diccionarios. El hash es como un “atajo” que solo funciona de una manera: si dos objetos tienen hashes diferentes, definitivamente no son iguales; pero si tienen el mismo hash, todavía podrían no ser iguales.

En tu ejemplo, __hash__ y __eq__ para hacer cosas diferentes. El hash depende solo de la sum de los números en el dominó, pero la igualdad depende de ambos números individuales (en orden). Esto es legal, ya que sigue siendo el caso de que dominós iguales tienen hashes iguales. Sin embargo, como dije anteriormente, no significa que los dominós de igual sum se considerarán iguales. Algunos dominós desiguales todavía tendrán hashes iguales. Pero la igualdad todavía está determinada por __eq__ , y __eq__ aún mira ambos números, en orden, de modo que eso es lo que determina si son iguales.

Me parece que lo más apropiado en su caso es definir __hash__ y __eq__ para depender del par ordenado , es decir, primero compare el mayor de los dos números, luego compare el menor. Esto significará que 2-1 y 1-2 se considerarán iguales.

El hash es solo una sugerencia para ayudar a Python a organizar los objetos. Cuando se busca algún objeto foo en un conjunto, todavía tiene que verificar cada objeto en el conjunto con el mismo hash que foo .

Es como tener una estantería para cada letra del alfabeto. Digamos que desea agregar un nuevo libro a su colección, solo si todavía no tiene una copia del mismo; Primero irías a la estantería por la letra apropiada. Pero luego tienes que mirar cada libro en el estante y compararlo con el que tienes en la mano, para ver si es lo mismo. No descartarías el nuevo libro solo porque ya hay algo en el estante.

Si desea utilizar algún otro valor para filtrar “duplicados”, utilice un dict que asigne el valor total del dominó al primer dominó que vio. No subvierta el comportamiento Python incorporado para que signifique algo completamente diferente. (Como has descubierto, de todos modos no funciona en este caso).

El requisito para las funciones hash es que si x == y para dos valores, entonces hash(x) == hash(y) . Lo contrario no tiene por qué ser cierto.

Puede ver fácilmente por qué este es el caso considerando el hashing de cadenas. Digamos que el hash(str) devuelve un número de 32 bits, y tenemos cadenas de hash de más de 4 caracteres (es decir, contienen más de 32 bits). Hay más cadenas posibles que valores de hash posibles, por lo que algunas cadenas no iguales deben compartir el mismo hash (esta es una aplicación del principio de casillero ).

Los conjuntos de Python se implementan como tablas hash. Al verificar si un objeto es miembro del conjunto, llamará a su función hash y usará el resultado para elegir un grupo, y luego usará el operador de igualdad para ver si coincide con alguno de los elementos del grupo.

Con su implementación, los dominós 2-2 y 1-3 terminarán en el cubo de hash, pero no se comparan igual. Por lo tanto, los dos se pueden agregar al conjunto.

Puedes leer sobre esto en la documentación del modelo de datos de Python, pero la respuesta corta es que puedes reescribir tu función hash como:

 def __hash__(self): return hash(tuple(sorted((self.one, self.two)))) 

Me gusta el sonido de la respuesta proporcionada por Eevee, pero tuve dificultades para imaginar una implementación. Aquí está mi interpretación, explicación e implementación de la respuesta proporcionada por Eevee.

  • Usa la sum de dos valores de dominó como diccionario de la clave.
  • Almacene cualquiera de los valores de dominó como el valor del diccionario.

Por ejemplo, dado el dominó ’12’, la sum es 3 y, por lo tanto, la clave del diccionario será 3. Luego, podemos seleccionar cualquier valor (1 o 2) para almacenar en esa posición (elegiremos el primer valor, 1 ).

 domino_pairs = {} pair = '12' pair_key = sum(map(int, pair)) domino_pairs[pair_key] = int(pair[0]) # Store the first pair's first value. print domino_pairs 

Salidas:

 {3: '1'} 

Aunque solo estamos almacenando un único valor del par de dominó, el otro valor se puede calcular fácilmente a partir de la clave y el valor del diccionario:

 pair = '12' pair_key = sum(map(int, pair)) domino_pairs[pair_key] = int(pair[0]) # Store the first pair's first value. # Retrieve pair from dictionary. print pair_key - domino_pairs[pair_key] # 3-1 = 2 

Salidas:

 2 

Pero, dado que dos pares diferentes pueden tener el mismo total, necesitamos almacenar varios valores en una sola clave. Por lo tanto, almacenamos una lista de valores contra una sola clave (es decir, la sum de dos pares). Poner esto en una función:

 def add_pair(dct, pair): pair_key = sum(map(int, pair)) if pair_key not in dct: dct[pair_key] = [] dct[pair_key].append(int(pair[0])) domino_pairs = {} add_pair(domino_pairs, '22') add_pair(domino_pairs, '04') print domino_pairs 

Salidas:

 {4: [2, 0]} 

Esto tiene sentido. Ambos pares sumn 4, pero el primer valor en cada par difiere, por lo que almacenamos ambos. La implementación hasta el momento permitirá duplicados:

 domino_pairs = {} add_pair(domino_pairs, '40') add_pair(domino_pairs, '04') print domino_pairs 

Salidas

  {4: [4, 0]} 

’40’ y ’04’ son iguales en Dominos, por lo que no necesitamos almacenar ambos. Necesitamos una forma de comprobar si hay duplicados. Para ello definiremos una nueva función, has_pair :

  def has_pair(dct, pair): pair_key = sum(map(int, pair)) if pair_key not in dct: return False return (int(pair[0]) in dct[pair_key] or int(pair[1]) in dct[pair_key]) 

Como de costumbre, obtenemos la sum (nuestra clave de diccionario). Si no está en el diccionario, entonces el par no puede existir. Si está en el diccionario, debemos verificar si alguno de los valores de nuestro par existe en el ‘cubo’ del diccionario. add_pair esta comprobación en add_pair , por lo que no agregamos pares de dominó duplicados:

 def add_pair(dct, pair): pair_key = sum(map(int, pair)) if has_pair(dct, pair): return if pair_key not in dct: dct[pair_key] = [] dct[pair_key].append(int(pair[0])) 

Ahora agregando pares de dominó duplicados funciona correctamente:

 domino_pairs = {} add_pair(domino_pairs, '40') add_pair(domino_pairs, '04') print domino_pairs 

Salidas:

 {4: [4]} 

Por último, una función de impresión muestra cómo almacenar solo la sum de un par de dominó y un solo valor del mismo par, es lo mismo que almacenar el propio par:

 def print_pairs(dct): for total in dct: for a in dct[total]: a = int(a) b = int(total) - int(a) print '(%d, %d)'%(a,b) 

Pruebas:

 domino_pairs = {} add_pair(domino_pairs, '40') add_pair(domino_pairs, '04') add_pair(domino_pairs, '23') add_pair(domino_pairs, '50') print_pairs(domino_pairs) 

Salidas:

 (4, 0) (2, 3) (5, 0)