Como implementar hash flutuante com igualdade aproximada

15

Digamos que temos a seguinte classe Python (o problema existe em Java da mesma forma com equalse hashCode)

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

onde degreesestá a temperatura em Kelvin como um flutuador. Agora, eu gostaria de implementar testes de igualdade e hash de Temperatureuma maneira que

  • compara flutuações até uma diferença de épsilon em vez de testes diretos de igualdade,
  • e honra o 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?

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?

Marta
fonte
9
por que a pergunta tem a tag do Java?
LAIV
8
Sobre a sua atualização: eu diria que o hash floats geralmente é uma coisa questionável. Tente evitar o uso de carros alegóricos como chaves ou como elementos do conjunto.
J. Fabian Meier
6
@ Neil: Ao mesmo tempo, o arredondamento não soa como números inteiros? Com isso quero dizer: se você pode arredondar para, digamos, milésimos de graus, então você poderia simplesmente usar uma representação de ponto fixo - um número inteiro que expressa a temperatura em milésimos de graus. Para facilidade de uso, você poderia ter um getter / setter transparente conversão de / para carros alegóricos se quiser ...
Matthieu M.
4
Kelvins não são mais graus. Os graus também são ambíguos. Por que não chamar kelvin?
Solomon Ucko
5
O Python tem um suporte de ponto fixo mais ou menos excelente , talvez seja algo para você.
Jonas Schäfer

Respostas:

41

implementar testes de igualdade e hash para Temperature de forma a comparar flutuações até uma diferença de epsilon em vez de testes diretos de igualdade,

A igualdade difusa viola os requisitos que o Java impõe ao equalsmétodo, a saber , transitividade , ou seja, se x == ye y == z, então x == z. Mas se você fizer uma igualdade difusa com, por exemplo, um epsilon de 0,1, então 0.1 == 0.2e 0.2 == 0.3, mas 0.1 == 0.3nã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.)

Sebastian Redl
fonte
2
pensamentos interessantes. Então, acumulando milhões de epsilon e com transitividade, você pode concluir que qualquer coisa é igual a qualquer outra coisa :-) Mas essa restrição matemática reconhece a base discreta dos pontos flutuantes, que em muitos casos são aproximações do número que pretendem representar?
Christophe
@Christophe Pergunta interessante. Se você pensar bem, verá que essa abordagem criará uma única classe grande de equivalência com flutuações cuja resolução é maior que epsilon (é centrada em 0, é claro) e deixará as outras flutuações em sua própria classe cada. Mas esse não é o ponto, o problema real é que, se conclui que 2 números são iguais, depende se existe um terceiro comparado e a ordem em que isso é feito.
Ordous
Abordando a edição do @ OP, eu acrescentaria que a incorreta do ponto flutuante ==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 é usada Temperature. É a única coisa que você pode fazer, realmente.
HTNW
@HTNW: Isso seria muito simples. Uma classe de proporção pode ter um float approximationcampo 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 é um floattipo.
MSalters
@MSalters? Presumivelmente, ferramentas de análise estática suficientemente configuráveis ​​podem fazer o que eu sugeri muito bem. Se uma classe tiver um floatcampo 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ão void bar() { foo(); }é um aviso, mas @Deprecated void bar() { foo(); }não é. Talvez muitas ferramentas não suportem isso, mas algumas podem.
HTNW
16

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.

  1. Para cada dois pontos dentro do épsilon um do outro que não compartilham o mesmo valor de hash.

    • Ajuste o esquema de hash para que esses dois pontos tenham o mesmo valor.
  2. Ao induzir para todos esses pares, toda a sequência de números de ponto flutuante entrará em colapso em direção a um único valor.

Existem alguns casos em que isso não se aplica:

  • Infinito positivo / negativo
  • NaN
  • Alguns intervalos des normalizados que podem não ser vinculáveis ​​ao intervalo principal de um dado epsilon.
  • talvez algumas outras instâncias específicas de formato

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:

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

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.

Kain0_0
fonte
2
Concordo que a abordagem granular aqui provavelmente seria a melhor, se isso atender aos requisitos da OP. Embora eu tenha medo de que o OP tenha requisitos de tipo de +/- 0,1%, o que significa que não pode ser granular.
295 Neil
4
@DocBrown A parte "impossível" está correta. Se a igualdade baseada em epsilon implicar que os códigos de hash são iguais, você automaticamente terá todos os códigos de hash iguais, para que a função de hash não seja mais útil. A abordagem de buckets pode ser proveitosa, mas você terá números com diferentes códigos de hash arbitrariamente próximos um do outro.
J. Fabian Meier
2
A abordagem do depósito pode ser modificada verificando não apenas o depósito com a chave de hash exata, mas também os dois depósitos vizinhos (ou pelo menos um deles) quanto ao seu conteúdo. Isso elimina o problema desses casos extremos pelo custo de aumentar o tempo de execução em um fator de no máximo dois (quando implementado corretamente). No entanto, isso não altera a ordem geral do tempo de execução.
Doc Brown
Enquanto você estiver certo em espírito, nem tudo entrará em colapso. Com um pequeno epsilon fixo, a maioria dos números será igual a eles mesmos. Obviamente, para aqueles que o epsilon será inútil, novamente, em espírito, você está correto.
Carsten S
1
@CarstenS Sim, minha afirmação de que 99% do intervalo de hashes em um único hash não cobre realmente todo o intervalo de flutuação. Existem muitos valores altos de intervalo que são separados por mais de epsilon que serão hash em seus próprios baldes exclusivos.
precisa saber é o seguinte
7

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!

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

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:

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

  2. 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,

supercat
fonte
0

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

gnasher729
fonte
0

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*√2renderá em 2vez de 2.00000001ou similar. Obviamente, isso introduzirá complicações adicionais que podem ou não valer a pena.

BurnsBA
fonte