Digamos que temos a seguinte classe Python (o problema existe em Java da mesma forma com equals
e hashCode
)
class Temperature:
def __init__(self, degrees):
self.degrees = degrees
onde degrees
está a temperatura em Kelvin como um flutuador. Agora, eu gostaria de implementar testes de igualdade e hash de Temperature
uma maneira que
- compara flutuações até uma diferença de épsilon em vez de testes diretos de igualdade,
- e honra o contrato que
a == b
implicahash(a) == hash(b)
.
def __eq__(self, other):
return abs(self.degrees - other.degrees) < EPSILON
def __hash__(self):
return # What goes here?
A documentação do Python fala um pouco sobre números de hash para garantir isso, hash(2) == hash(2.0)
mas esse não é o mesmo problema.
Estou no caminho certo? E se sim, qual é a maneira padrão de implementar o hash nessa situação?
Atualização : Agora entendo que esse tipo de teste de igualdade para carros alegóricos elimina a transitividade de ==
e equals
. Mas como isso se combina com o "conhecimento comum" que flutua não deve ser comparado diretamente? Se você implementar um operador de igualdade comparando flutuadores, as ferramentas de análise estática irão reclamar. Eles estão certos em fazer isso?
fonte
kelvin
?Respostas:
A igualdade difusa viola os requisitos que o Java impõe ao
equals
método, a saber , transitividade , ou seja, sex == y
ey == z
, entãox == z
. Mas se você fizer uma igualdade difusa com, por exemplo, um epsilon de 0,1, então0.1 == 0.2
e0.2 == 0.3
, mas0.1 == 0.3
não se mantém.Embora o Python não documente esse requisito, as implicações de se ter uma igualdade não transitiva fazem dele uma péssima idéia; raciocinar sobre esses tipos é indutor de dor de cabeça.
Então, eu recomendo fortemente que você não faça isso.
Forneça a igualdade exata e baseie seu hash nisso da maneira óbvia, e forneça um método separado para fazer a correspondência difusa ou siga a abordagem da classe de equivalência sugerida por Kain. Embora, no último caso, recomendo que você fixe seu valor em um membro representativo da classe de equivalência no construtor e, em seguida, siga com igualdade exata simples e hash para o resto; é muito mais fácil argumentar sobre os tipos dessa maneira.
(Mas, se você fizer isso, poderá usar uma representação de ponto fixo em vez de ponto flutuante, ou seja, usar um número inteiro para contar milésimos de grau ou a precisão que precisar.)
fonte
==
deve "infectar" os==
tipos que os contêm. Ou seja, se eles seguirem seu conselho de fornecer uma igualdade exata, sua ferramenta de análise estática deverá ser configurada para avisar quando a igualdade é usadaTemperature
. É a única coisa que você pode fazer, realmente.float approximation
campo no qual não participe==
. Além disso, a ferramenta de análise estática já emitirá um aviso dentro da==
implementação de classes quando um dos membros que está sendo comparado é umfloat
tipo.float
campo que não participe==
, não configure sua ferramenta para avisá-la==
. Se a classe o fizer, presumivelmente marcá-la==
como "muito exata" fará com que a ferramenta ignore esse tipo de erro na implementação. Por exemplo, em Java, se@Deprecated void foo()
, entãovoid bar() { foo(); }
é um aviso, mas@Deprecated void bar() { foo(); }
não é. Talvez muitas ferramentas não suportem isso, mas algumas podem.Boa sorte
Você não conseguirá isso sem ser estúpido com hashes ou sacrificar o epsilon.
Exemplo:
Suponha que cada ponto tenha hash em seu próprio valor de hash exclusivo.
Como os números de ponto flutuante são seqüenciais, haverá até k números antes de um determinado valor de ponto flutuante e até k números após um determinado valor de ponto flutuante que esteja dentro de algum épsilon do ponto especificado.
Para cada dois pontos dentro do épsilon um do outro que não compartilham o mesmo valor de hash.
Existem alguns casos em que isso não se aplica:
No entanto,> = 99% do intervalo de ponto flutuante será hash para um valor único para qualquer valor de epsilon que inclua pelo menos um valor de ponto flutuante acima ou abaixo de algum valor de ponto flutuante.
Resultado
Ou> = 99% de toda a faixa de ponto flutuante hashes para um único valor comprometendo seriamente a intenção de um valor de hash (e qualquer dispositivo / contêiner que dependa de um hash de baixa colisão razoavelmente distribuído).
Ou o epsilon é tal que apenas as correspondências exatas são permitidas.
Granular
Obviamente, você poderia optar por uma abordagem granular.
Sob essa abordagem, você define intervalos exatos para uma resolução específica. ou seja:
Cada balde possui um hash exclusivo e qualquer ponto flutuante no balde é igual a qualquer outro flutuador no mesmo balde.
Infelizmente, ainda é possível que dois carros alegóricos estejam a uma distância de epsilon e tenham dois hashes separados.
fonte
Você pode modelar sua temperatura como um número inteiro sob o capô. A temperatura tem um limite inferior natural (-273,15 Celsius). Portanto, duplo (-273.15 é igual a 0 para o número inteiro subjacente). O segundo elemento que você precisa é a granularidade do seu mapeamento. Você já está usando essa granularidade implicitamente; é o seu EPSILON.
Basta dividir sua temperatura por EPSILON e usar a palavra, agora seu hash e seu igual se comportarão em sincronia. No Python 3, o número inteiro é ilimitado, o EPSILON pode ser menor, se você preferir.
CUIDADO Se você alterar o valor do EPSILON e serializar o objeto, ele não será compatível!
fonte
A implementação de uma tabela de hash de ponto flutuante que pode encontrar coisas "aproximadamente iguais" a uma determinada chave exigirá o uso de algumas abordagens ou uma combinação delas:
Arredonde cada valor para um incremento que seja um pouco maior que o intervalo "difuso" antes de armazená-lo na tabela de hash e, ao tentar encontrar um valor, verifique na tabela de hash os valores arredondados acima e abaixo do valor desejado.
Armazene cada item na tabela de hash usando chaves que estão acima e abaixo do valor que está sendo procurado.
Observe que o uso de qualquer abordagem provavelmente exigirá que as entradas da tabela de hash não identifiquem itens, mas sim listas, pois provavelmente haverá vários itens associados a cada chave. A primeira abordagem acima minimizará o tamanho necessário da tabela de hash, mas cada pesquisa por um item que não esteja na tabela exigirá duas pesquisas de tabela de hash. A segunda abordagem poderá identificar rapidamente que os itens não estão na tabela, mas geralmente exigirá que a tabela contenha duas vezes mais entradas do que seria necessário. Se alguém está tentando encontrar objetos no espaço 2D, pode ser útil usar uma abordagem para a direção X e outra para a direção Y, de modo que, em vez de ter cada item armazenado uma vez, mas exigindo quatro operações de consulta para cada pesquisa, ou seja capaz de usar uma pesquisa para encontrar um item, mas ter que armazenar cada item quatro vezes,
fonte
É claro que você pode definir “quase igual” excluindo, digamos, os últimos oito bits da mantissa e comparando ou fazendo hash. O problema é que os números muito próximos um do outro podem ser diferentes.
Há alguma confusão aqui: se dois números de ponto flutuante comparam iguais, eles são iguais. Para verificar se são iguais, use "==". Às vezes você não deseja verificar a igualdade, mas quando o faz, "==" é o caminho a percorrer.
fonte
Esta não é uma resposta, mas um comentário estendido que pode ser útil.
Eu tenho trabalhado em um problema semelhante ao usar o MPFR (baseado no GNU MP). A abordagem "bucket", conforme descrita por @ Kain0_0, parece dar resultados aceitáveis, mas esteja ciente das limitações destacadas nessa resposta.
Eu queria acrescentar que, dependendo do que você está tentando fazer, o uso de um sistema de álgebra computacional "exato" ( emptor ), como o Mathematica, pode ajudar a complementar ou verificar um programa numérico inexato. Isso permitirá que você calcule os resultados sem se preocupar com o arredondamento, por exemplo,
7*√2 - 5*√2
renderá em2
vez de2.00000001
ou similar. Obviamente, isso introduzirá complicações adicionais que podem ou não valer a pena.fonte