Pegadinha de matemática intervalar
Pegadinha de matemática intervalar
Bem que eu queria ter lido o livro de matemática intervalar daquela série da UFRGS, mas meu filho pegou primeiro e riscou todo, aí foi para o lixo. Achei que não tinha perdido muita coisa, mas hoje vi a importância do assunto.
Todo programador já topou com o problema da superposição de intervalos. Por exemplo, tenho dois intervalos de data, e preciso testar se eles sobrepõem.
Outro exemplo: comparar intervalos de preços: eu aceito preço A até B, meu fornecedor ofereceu preço C até D. Se existir "terreno comum" entre minha faixa A..B e a faixa C..D dele, temos negócio, senão, nada feito.
Mais um caso: testar igualdade de números de ponto flutuante. Também é outra pegadinha que todo programador já caiu: você faz 0,1 + 0,2 e a comparação com 0,3 resulta Falso — porque o resultado, para o computador, foi 0,29999999999.
Um jeito de evitar este problema é usar inteiros escalonados. Num sistema contábil, o correto é armazenar os valores em centavos, não em reais. O SQL oferece o tipo DECIMAL pelo messmo motivo: representação exata de números decimais.
Mas, quando somos obrigados a usar ponto flutuante, precisamos estipular uma tolerância ("epsilon"). Se os números se sobrepõem nas suas respectivas faixas de tolerância, são considerados "iguais":
x = 0.3 y = 0.1 + 0.2 epsilon = 10**-10 # tolerância A = x - epsilon B = x + epsilon C = x - epsilon D = x + epsilon # Se a faixa A..B sobrepõe C..D, então podemos # considerar que x e y são "iguais".
Na verdade, podemos usar uma técnica bem mais simples ao comparar números:
abs(valor) < epsilon // para verificar se é zero abs(valor1 - valor2) < epsilon // para verificar se são iguais
Mas comparar intervalos dá um pouco mais de trabalho.
A vida inteirinha eu testei superposição da seguinte forma:
(A >= C and A <= D) or (B >= C and B <= D)
A lógica é simples: verifico se o "meu" preço mais baixo (A) está no intervalo do fornecedor (C..D). Se estiver, obviamente há superposição. Se não, verifico então se meu preço mais alto (B) está entre C e D. Se nenhum dos extremos A e B está no intervalo C..D, não pode haver superposição.
Um programador mais naïve e mais paranóico faria também o teste contrário: ver se C ou D estão na faixa A..B, resultando numa expressão muito mais comprida:
[(A >= C and A <= D) or (B >= C and B <= D)] or [(C >= A and C <= B) or (D >= A and D <= B)]
Parece óbvio que não é necessário adicionar este contra-teste, afinal se A..B sobrepõe C..D, o contrário é automaticamente verdadeiro, né?
Bem, hoje fui brincar com um código que testava igualdade de ponto flutuante, aí pesquisa daqui, pesquisa dali, e descobri que eu também estava errado a vida inteira. O teste a seguir é suficiente para detectar sobreposição:
A <= D and B >= C
Vivendo e aprendendo.
Para me redimir um pouco, notei que a fórmula ideal, com 2 comparações, pressupõe intervalos "em ordem" ou seja, A < B e C < D. Se algum intervalo estiver fora de ordem, esta fórmula não funciona; mas a "minha" fórmula com 4 comparações ainda funciona se o intervalo A..B estiver desordenado.
Provavelmente, quando precisei de semelhante fórmula pela primeira vez, tive de lidar com intervalos fora de ordem, e acabei me fixando na versão de 4 comparações.
A fórmula com oito comparações parece imune a intervalos fora de ordem, mas não é. Se os dois intervalos estiverem invertidos, ela falha. Ela ainda funciona se apenas um dos intervalos estiver invertido (não importa qual). Sendo assim, o melhor é ordenar os intervalos e usar a fórmula com duas comparações.
É fácil constatar intuitivamente que as fórmulas com quatro ou oito comparações estão corretas. Resta agora provar que a fórmula com apenas duas comparações é equivalente às outras, e portanto também correta.
A chave está nas relações de implicância: se A >= C, forçosamente B >= C. Ou na mão contrária: B < C implica em A < C. Isto permite reescrever expressões sem alterar seu resultado. Por exemplo:
A >= C é equivalente a (A >= C and B >= C) C >= A é equivalente a (C >= A and D >= A)
e assim por diante. Trabalhar a fórmula de 8 comparações foi, curiosamente, mais simples:
# Transforma cada comparação numa letra
(A >= C and A <= D) or (B >= C and B <= D) or
a b c d
[(C >= A and C <= B) or (D >= A and D <= B)]
!a c b !d
[ab + cd] + [!ac + b!d]
# Relações de implicância
a=>ac
!a=>!ab
d=>bd
!d=>!dc
# Usa as regras de implicância
[acb+cbd] + [!abc+bc!d]
# Simplifica
abc+bcd+!abc+bc!d
bc(a+!a)+bc(d+!d)
bc
A expressão com 4 comparações foi osso mais duro de roer, não consegui simplificar diretamente. O caminho que encontrei foi:
Trocar (A,B) por (C,D) evidencia que os dois lados da fórmula de 8 comparações (com 4 comparações cada) são equivalentes e redundantes. ab+cd + !ac+b!d = ab+cd = !ac+b!d = bc