Comparação de três vias - Three-way comparison
Na ciência da computação , uma comparação de três vias toma dois valores A e B pertencentes a um tipo com uma ordem total e determina se A <B, A = B ou A> B em uma única operação, de acordo com a lei matemática de tricotomia .
Computação em nível de máquina
Muitos processadores têm conjuntos de instruções que suportam essa operação em tipos primitivos. Algumas máquinas têm números inteiros com sinal com base em um sinal e magnitude ou na representação do complemento de alguém (consulte as representações dos números com sinal ), ambos os quais permitem um zero positivo e um zero negativo diferenciados . Isso não viola a tricotomia, desde que uma ordem total consistente seja adotada: −0 = +0 ou −0 <+0 é válido. Os tipos de ponto flutuante comuns , no entanto, têm uma exceção à tricotomia: há um valor especial "NaN" ( não é um número ), de modo que x <NaN, x > NaN e x = NaN são todos falsos para todos os valores de ponto flutuantex (incluindo o próprio NaN).
Linguagens de alto nível
Capacidades
Em C , as funções strcmpe memcmpexecutam uma comparação de três vias entre strings e buffers de memória, respectivamente. Eles retornam um número negativo quando o primeiro argumento é lexicograficamente menor que o segundo, zero quando os argumentos são iguais e um número positivo caso contrário. Essa convenção de retornar o "sinal da diferença" é estendida a funções de comparação arbitrárias pela função de classificação padrão qsort, que assume uma função de comparação como um argumento e exige que ela a cumpra.
Em C ++ , a revisão C ++ 20 adiciona o " operador de nave " <=>, que de forma semelhante retorna o sinal da diferença e também pode retornar tipos diferentes (conversíveis em inteiros com sinal) dependendo da rigidez da comparação.
Em Perl (apenas para comparações numéricas, o cmpoperador é usado para comparações lexicais de strings), PHP (desde a versão 7), Ruby e Apache Groovy , o "operador de nave espacial" <=>retorna os valores -1, 0 ou 1, dependendo de A <B, A = B ou A> B, respectivamente. As funções Python 2.x cmp(removido no 3.x), OCaml compare e Kotlin compareTo computam a mesma coisa. Na biblioteca padrão Haskell , a função de comparação de três vias compareé definida para todos os tipos da Ord classe ; ele retorna tipo Ordering, cujos valores são LT(menor que), EQ(igual) e GT(maior que):
data Ordering = LT | EQ | GT
Muitas linguagens orientadas a objetos têm um método de comparação de três vias , que realiza uma comparação de três vias entre o objeto e outro determinado objeto. Por exemplo, em Java , qualquer classe que implementa a Comparableinterface tem um compareTométodo que retorna um inteiro negativo, zero ou um inteiro positivo, ou lança um NullPointerException(se um ou ambos os objetos forem null). Da mesma forma, no .NET Framework , qualquer classe que implemente a IComparableinterface possui esse CompareTométodo.
Desde a versão 1.5 do Java, o mesmo pode ser calculado usando o Math.signummétodo estático se a diferença puder ser conhecida sem problemas computacionais, como estouro aritmético mencionado abaixo. Muitas linguagens de computador permitem a definição de funções, de forma que uma comparação (A, B) possa ser concebida apropriadamente, mas a questão é se sua definição interna pode ou não empregar algum tipo de sintaxe de três vias ou então deve recorrer a testes repetidos.
Ao implementar uma comparação de três vias onde um operador ou método de comparação de três vias ainda não está disponível, é comum combinar duas comparações, como A = B e A <B, ou A <B e A> B. Em princípio , um compilador pode deduzir que essas duas expressões podem ser substituídas por apenas uma comparação seguida de vários testes do resultado, mas a menção dessa otimização não é encontrada em textos sobre o assunto.
Em alguns casos, a comparação de três vias pode ser simulada subtraindo A e B e examinando o sinal do resultado, explorando instruções especiais para examinar o sinal de um número. No entanto, isso requer que o tipo de A e B tenham uma diferença bem definida. Inteiros com sinal de largura fixa podem estourar quando são subtraídos, os números de ponto flutuante têm o valor NaN com sinal indefinido e as cadeias de caracteres não têm função de diferença correspondente à sua ordem total. No nível da máquina, o estouro normalmente é rastreado e pode ser usado para determinar a ordem após a subtração, mas essas informações geralmente não estão disponíveis para linguagens de nível superior.
Em um caso de uma condicional de três vias fornecida pela linguagem de programação, a declaração aritmética de três vias de Fortran , agora obsoleta , considera o sinal de uma expressão aritmética e oferece três rótulos para saltar de acordo com o sinal do resultado:
IF (expression) negative,zero,positive
A função de biblioteca comum strcmp em C e linguagens relacionadas é uma comparação lexicográfica de três vias de strings; no entanto, essas linguagens carecem de uma comparação geral de três vias de outros tipos de dados.
Operador de nave espacial
O operador de comparação de três vias para os números é denotado como <=>em Perl , rubi , Apache Groovy , PHP , Eclipse Ceilão , e C ++ , e é chamado o operador nave espacial .
A origem do nome deve-se a ele lembrar Randal L. Schwartz da nave espacial em um jogo HP BASIC Star Trek . Outro programador sugeriu que recebeu esse nome porque era semelhante ao lutador TIE de Darth Vader na saga Star Wars .
Exemplo em PHP:
echo 1 <=> 1; // 0
echo 1 <=> 2; // -1
echo 2 <=> 1; // 1
Tipos de dados compostos
As comparações de três vias têm a propriedade de serem fáceis de compor e construir comparações lexicográficas de tipos de dados não primitivos, ao contrário das comparações de duas vias.
Aqui está um exemplo de composição em Perl.
sub compare($$) {
my ($a, $b) = @_;
return $a->{unit} cmp $b->{unit}
|| $a->{rank} <=> $b->{rank}
|| $a->{name} cmp $b->{name};
}
Observe que cmp, em Perl, é para strings, já que <=>é para números. Equivalentes bidirecionais tendem a ser menos compactos, mas não necessariamente menos legíveis. O exemplo acima tira vantagem da avaliação de curto-circuito do ||operador e do fato de que 0 é considerado falso em Perl. Como resultado, se a primeira comparação for igual (portanto avaliada como 0), ela "cairá" para a segunda comparação e assim por diante, até encontrar uma que seja diferente de zero ou até chegar ao fim.
Em algumas linguagens, incluindo Python , Ruby , Haskell , etc., a comparação de listas é feita lexicograficamente, o que significa que é possível construir uma cadeia de comparações como o exemplo acima, colocando os valores em listas na ordem desejada; por exemplo, em Ruby:
[a.unit, a.rank, a.name] <=> [b.unit, b.rank, b.name]