Cómo implementar hashing flotante con igualdad aproximada

15

Digamos que tenemos la siguiente clase de Python (el problema existe en Java igual que con equalsy hashCode)

class Temperature:
    def __init__(self, degrees):
        self.degrees = degrees

¿Dónde degreesestá la temperatura en Kelvin como flotador? Ahora, me gustaría implementar pruebas de igualdad y hashing de Temperatureuna manera que

  • compara flotadores hasta una diferencia de épsilon en lugar de pruebas de igualdad directa,
  • y honra el contrato que a == bimplica hash(a) == hash(b).
def __eq__(self, other):
    return abs(self.degrees - other.degrees) < EPSILON

def __hash__(self):
    return # What goes here?

La documentación de Python habla un poco sobre los números hash para asegurar eso, hash(2) == hash(2.0)pero este no es exactamente el mismo problema.

¿Estoy incluso en el camino correcto? Y si es así, ¿cuál es la forma estándar de implementar hashing en esta situación?

Actualización : ahora entiendo que este tipo de prueba de igualdad para flotadores elimina la transitividad de ==y equals. Pero, ¿cómo va eso junto con el "conocimiento común" de que los flotadores no deben compararse directamente? Si implementa un operador de igualdad comparando flotantes, las herramientas de análisis estático se quejarán. ¿Tienen razón para hacerlo?

Marta
fuente
99
¿Por qué la pregunta tiene la etiqueta de Java?
Laiv
8
Acerca de su actualización: Diría que los hash flotantes son generalmente cuestionables. Trate de evitar el uso de flotadores como claves o como elementos establecidos.
J. Fabian Meier
66
@Neil: Al mismo tiempo, ¿el redondeo no suena como números enteros? Con eso quiero decir: si puede redondear a, digamos, milésimas de grado, entonces simplemente podría usar una representación de punto fijo, un número entero que expresa la temperatura en milésimas de grado. Para facilitar su uso, puede tener un getter / setter que se convierta de forma transparente de / a flotadores si desea ...
Matthieu M.
44
Kelvins ya no son grados. Los grados también son ambiguos. ¿Por qué no solo llamarlo kelvin?
Solomon Ucko
55
Python tiene un soporte de punto fijo más o menos excelente , tal vez eso sea algo para ti.
Jonas Schäfer

Respuestas:

41

Implemente pruebas de igualdad y hash para temperatura de una manera que compare flotantes hasta una diferencia de épsilon en lugar de pruebas de igualdad directas,

La igualdad difusa viola los requisitos que Java impone al equalsmétodo, a saber, la transitividad , es decir, si x == yy y == zluego x == z. Pero si hace una igualdad difusa con, por ejemplo, un épsilon de 0.1, entonces 0.1 == 0.2y 0.2 == 0.3, pero 0.1 == 0.3no se cumple.

Si bien Python no documenta dicho requisito, las implicaciones de tener una igualdad no transitiva hacen que sea una muy mala idea; El razonamiento acerca de estos tipos induce dolor de cabeza.

Así que te recomiendo que no hagas eso.

O proporcione igualdad exacta y base su hash en eso de la manera obvia, y proporcione un método separado para hacer la coincidencia difusa, o vaya con el enfoque de clase de equivalencia sugerido por Kain. Aunque en el último caso, le recomiendo que fije su valor a un miembro representativo de la clase de equivalencia en el constructor, y luego vaya con simple igualdad exacta y hashing para el resto; Es mucho más fácil razonar sobre los tipos de esta manera.

(Pero si hace eso, también podría usar una representación de punto fijo en lugar de punto flotante, es decir, usar un número entero para contar milésimas de grado, o cualquier precisión que requiera).

Sebastian Redl
fuente
2
pensamientos interesantes Entonces, al acumular millones de épsilon y con transitividad, puede concluir que cualquier cosa es igual a cualquier otra cosa :-) Pero, ¿esta restricción matemática reconoce la base discreta de los puntos flotantes, que en muchos casos son aproximaciones del número que pretenden representar?
Christophe
@Christophe Pregunta interesante. Si lo piensa, verá que este enfoque formará una sola clase de equivalencia grande de flotadores cuya resolución es mayor que epsilon (se centra en 0, por supuesto) y dejará los otros flotadores en su propia clase cada uno. Pero ese no es el punto, el verdadero problema es que si concluye que 2 números son iguales depende de si hay un tercero comparado y el orden en que se hace.
Ordous
Al abordar la edición de @ OP, agregaría que la incorrección de la coma flotante ==debería "infectar" los ==tipos que los contienen. Es decir, si siguen su consejo de proporcionar una igualdad exacta, entonces su herramienta de análisis estático debería configurarse para advertir cuándo se usa la igualdad Temperature. Es lo único que puedes hacer, de verdad.
HTNW
@HTNW: Eso sería demasiado simple. Una clase de razón puede tener un float approximationcampo en el que no participa ==. Además, la herramienta de análisis estático ya dará una advertencia dentro de la ==implementación de clases cuando uno de los miembros que se compara es un floattipo.
MSalters
@MSalters? Presumiblemente, las herramientas de análisis estático suficientemente configurables pueden hacer lo que sugerí perfectamente. Si una clase tiene un floatcampo en el que no participa ==, no configure su herramienta para advertir ==sobre esa clase. Si la clase lo hace, entonces, presumiblemente, marcar la clase ==como "demasiado exacta" hará que la herramienta ignore ese tipo de error dentro de la implementación. Por ejemplo, en Java, si @Deprecated void foo(), entonces void bar() { foo(); }es una advertencia, pero @Deprecated void bar() { foo(); }no lo es. Tal vez muchas herramientas no admiten esto, pero algunas podrían.
HTNW
16

Buena suerte

No podrás lograr eso sin ser estúpido con los hashes o sacrificar el épsilon.

Ejemplo:

Suponga que cada punto tiene un valor hash único.

Como los números de coma flotante son secuenciales, habrá hasta k números antes de un valor de coma flotante dado, y hasta k números después de un valor de coma flotante dado que se encuentran dentro de una épsilon del punto dado.

  1. Por cada dos puntos dentro de epsilon entre sí que no comparten el mismo valor hash.

    • Ajuste el esquema de hash para que estos dos puntos tengan el mismo valor.
  2. Induciendo para todos estos pares, la secuencia completa de números de coma flotante colapsará hacia un solo valor.

Hay algunos casos en los que esto no será así:

  • Infinito Positivo / Negativo
  • Yaya
  • Algunos rangos desnormalizados que pueden no estar vinculados al rango principal para un épsilon dado.
  • quizás algunas otras instancias específicas de formato

Sin embargo,> = 99% del rango de coma flotante se dividirá en un solo valor para cualquier valor de épsilon que incluya al menos un valor de coma flotante por encima o por debajo de un valor de coma flotante dado.

Salir

Ya sea> = 99% de hashes de rango de punto flotante completo a un solo valor que comprime seriamente la intención de un valor de hash (y cualquier dispositivo / contenedor que se base en un hash de baja colisión bastante distribuido).

O el épsilon es tal que solo se permiten coincidencias exactas.

Granular

Por supuesto, podría optar por un enfoque granular.

Bajo este enfoque, usted define los cubos exactos hasta una resolución particular. es decir:

[0.001, 0.002)
[0.002, 0.003)
[0.003, 0.004)
...
[122.999, 123.000)
...

Cada cubo tiene un hash único, y cualquier punto flotante dentro del cubo se compara igual a cualquier otro flotante en el mismo cubo.

Desafortunadamente, todavía es posible que dos flotadores estén a una distancia de épsilon y tengan dos hashes separados.

Kain0_0
fuente
2
Estoy de acuerdo en que el enfoque granular aquí probablemente sería el mejor, si eso cumple con los requisitos de OP. Aunque me temo que OP tiene requisitos de tipo de +/- 0.1%, lo que significa que no puede ser granular.
Neil
44
@DocBrown La parte "no posible" es correcta. Si la igualdad basada en epsilon implica que los códigos hash son iguales, entonces automáticamente tiene todos los códigos hash iguales, por lo que la función hash ya no es útil. El enfoque de cubos puede ser fructífero, pero tendrá números con diferentes códigos hash que son arbitrariamente cercanos entre sí.
J. Fabian Meier
2
El enfoque del depósito puede modificarse comprobando no solo el depósito con la clave hash exacta, sino también los dos depósitos vecinos (o al menos uno de ellos) por su contenido. Eso elimina el problema de esos casos extremos por el costo de aumentar el tiempo de ejecución en un factor de como máximo dos (cuando se implementa correctamente). Sin embargo, no cambia el orden general del tiempo de ejecución.
Doc Brown
Mientras tengas razón en el espíritu, no todo colapsará. Con un épsilon pequeño fijo, la mayoría de los números solo serán iguales. Por supuesto, para aquellos, el épsilon será inútil, así que nuevamente, en espíritu, tienes razón.
Carsten S
1
@CarstenS Sí, mi afirmación de que el 99% del rango de hash a un solo hash en realidad no cubre todo el rango flotante. Hay muchos valores de rango alto que están separados por más de épsilon que se dividirán en sus propios cubos únicos.
Kain0_0
7

Puede modelar su temperatura como un número entero debajo del capó. La temperatura tiene un límite inferior natural (-273,15 grados Celsius). Entonces, doble (-273.15 es igual a 0 para su entero subyacente). El segundo elemento que necesita es la granularidad de su mapeo. Ya está utilizando esta granularidad implícitamente; Es tu EPSILON.

Simplemente divida su temperatura por EPSILON y tome la palabra, ahora su hash y su igual se comportarán en sincronía. En Python 3 el número entero no tiene límites, EPSILON puede ser más pequeño si lo desea.

CUIDADO ¡ Si cambia el valor de EPSILON y ha serializado el objeto, no serán compatibles!

#Pseudo code
class Temperature:
    def __init__(self, degrees):
        #CHECK INVALID VALUES HERE
        #TRANSFORM TO KELVIN HERE
        self.degrees = Math.floor(kelvin/EPSILON)
Alessandro Teruzzi
fuente
1

La implementación de una tabla hash de punto flotante que puede encontrar cosas que son "aproximadamente iguales" a una clave determinada requerirá el uso de un par de enfoques o una combinación de ellos:

  1. Redondee cada valor a un incremento que sea algo mayor que el rango "difuso" antes de almacenarlo en la tabla hash, y cuando intente encontrar un valor, verifique en la tabla hash los valores redondeados por encima y por debajo del valor buscado.

  2. Almacene cada elemento dentro de la tabla hash utilizando las teclas que están por encima y por debajo del valor que se busca.

Tenga en cuenta que el uso de cualquiera de los enfoques probablemente requerirá que las entradas de la tabla hash no identifiquen elementos, sino listas, ya que es probable que haya múltiples elementos asociados con cada clave. El primer enfoque anterior minimizará el tamaño requerido de la tabla hash, pero cada búsqueda de un elemento que no esté en la tabla requerirá dos búsquedas en la tabla hash. El segundo enfoque podrá identificar rápidamente que los elementos no están en la tabla, pero generalmente requerirá que la tabla contenga aproximadamente el doble de entradas que de lo contrario se requerirían. Si uno está tratando de encontrar objetos en el espacio 2D, puede ser útil usar un enfoque para la dirección X y otro para la dirección Y, de modo que en lugar de tener cada elemento almacenado una vez pero requiriendo cuatro operaciones de consulta para cada búsqueda, o capaz de usar una búsqueda para encontrar un artículo pero tener que almacenar cada artículo cuatro veces,

Super gato
fuente
0

Por supuesto, puede definir "casi igual" eliminando digamos los últimos ocho bits de la mantisa y luego comparando o haciendo hash. El problema es que los números muy cercanos entre sí pueden ser diferentes.

Aquí hay cierta confusión: si dos números de coma flotante se comparan iguales, son iguales. Para verificar si son iguales, use “==“. A veces no desea verificar la igualdad, pero cuando lo hace, "==" es el camino a seguir.

gnasher729
fuente
0

Esta no es una respuesta, sino un comentario extendido que puede ser útil.

He estado trabajando en un problema similar, mientras usaba MPFR (basado en GNU MP). El enfoque de "cubeta" como lo describe @ Kain0_0 parece dar resultados aceptables, pero tenga en cuenta las limitaciones resaltadas en esa respuesta.

Quería agregar que, dependiendo de lo que intente hacer, usar un sistema de álgebra computacional "exacto" ( advertencia de advertencia ) como Mathematica puede ayudar a complementar o verificar un programa numérico inexacto. Esto le permitirá calcular resultados sin preocuparse por el redondeo, por ejemplo, 7*√2 - 5*√2rendirá en 2lugar de 2.00000001o similar. Por supuesto, esto introducirá complicaciones adicionales que pueden o no valer la pena.

BurnsBA
fuente