Comparación de tres vías

En informática , una comparación de tres vías toma dos valores A y B pertenecientes a un tipo con un orden total y determina si A < B, A = B o A > B en una sola operación, de acuerdo con la ley matemática de la tricotomía .

Se puede implementar en términos de una función (como strcmpen C ), un método (como compareToen Java ) o un operador (como el operador de nave espacial <=> en Perl , PHP y C++ ).

Muchos procesadores tienen conjuntos de instrucciones que admiten dicha operación en tipos primitivos. Algunas máquinas tienen enteros con signo basados ​​en una representación de signo y magnitud o complemento a uno (ver representaciones de números con signo ), las cuales permiten un cero positivo y negativo diferenciado . Esto no viola la tricotomía siempre que se adopte un orden total consistente: ya sea −0 = +0 o −0 < +0 es válido. Sin embargo, los tipos de punto flotante comunes tienen una excepción a la tricotomía: hay un valor especial "NaN" ( Not a Number ) tal que x < NaN, x > NaN y x = NaN son todos falsos para todos los valores de punto flotante x (incluido el propio NaN).

En C , las funciones strcmpy memcmprealizan una comparación de tres vías entre cadenas y búferes de memoria, respectivamente. Devuelven un número negativo cuando el primer argumento es lexicográficamente más pequeño que el segundo, cero cuando los argumentos son iguales y un número positivo en caso contrario. Esta convención de devolver el "signo de la diferencia" se extiende a funciones de comparación arbitrarias mediante la función de ordenación estándar qsort, que toma una función de comparación como argumento y requiere que la respete.

En Perl (solo para comparaciones numéricas, el cmpoperador se usa para comparaciones léxicas de cadenas), PHP (desde la versión 7), Ruby y Apache Groovy , el "operador de nave espacial" <=>devuelve los valores −1, 0 o 1 dependiendo de si A < B, A = B o A > B, respectivamente. Las funciones de Python 2.x cmp(eliminadas en 3.x), OCaml compare y Kotlin compareTo calculan lo mismo. En la biblioteca estándar de Haskell , la función de comparación de tres vías está definida para todos los tipos de la clase ; devuelve el tipo , cuyos valores son (menor que), (igual) y (mayor que): ^[1]compareOrd OrderingLTEQGT

Ordenación de datos = LT | EQ | GT       

Muchos lenguajes de programación orientados a objetos tienen una función de comparación de tres vías , que realiza una comparación de tres vías entre el objeto y otro objeto dado. Por ejemplo, en Java , cualquier clase que implementa la Comparableinterfaz tiene un método compareTo que devuelve un entero negativo, cero o un entero positivo, o lanza un NullPointerException(si uno o ambos objetos son null). De manera similar, en el marco .NET , cualquier clase que implementa la IComparableinterfaz tiene un método CompareTo de este tipo. En C++ , cualquier clase que pueda compararse de tres maneras puede ser un parámetro para instancias de std::compare_three_way, std::strong_order, std::weak_order o std::partial_order.

Desde la versión 1.5 de Java, se puede calcular lo mismo utilizando el Math.signummétodo estático si se puede conocer la diferencia sin problemas computacionales como el desbordamiento aritmético mencionado a continuación. Muchos lenguajes de programación permiten la definición de funciones, por lo que se podría idear una función compare(A,B) de manera adecuada, pero la pregunta es si su definición interna puede emplear algún tipo de sintaxis de tres vías o si, de lo contrario, se debe recurrir a pruebas repetidas.

Al implementar una comparación de tres vías donde un operador o método de comparación de tres vías no está disponible, es común combinar dos comparaciones, como A = B y A < B, o A < B y A > B. En principio, un compilador podría deducir que estas dos expresiones podrían reemplazarse por una sola comparación seguida de múltiples pruebas del resultado, pero no se encuentran menciones de esta optimización en los textos sobre el tema.

En algunos casos, la comparación de tres vías se puede simular restando A y B y examinando el signo del resultado, aprovechando instrucciones especiales para examinar el signo de un número. Sin embargo, esto requiere que el tipo de A y B tenga una diferencia bien definida. Los números enteros con signo de ancho fijo pueden desbordarse cuando se restan, los números de punto flotante tienen el valor NaN con signo indefinido y las cadenas de caracteres no tienen una función de diferencia correspondiente a su orden total. A nivel de máquina, el desbordamiento generalmente se rastrea y se puede usar para determinar el orden después de la resta, pero esta información generalmente no está disponible para lenguajes de nivel superior.

En un caso de una condicional de tres vías proporcionada por el lenguaje de programación, la declaración aritmética de tres vías IF de Fortran, ahora obsoleta , considera el signo de una expresión aritmética y ofrece tres etiquetas para saltar según el signo del resultado:

 SI ( expresión ) negativo , cero , positivo  

La función de biblioteca común strcmp en C y lenguajes relacionados es una comparación lexicográfica de tres vías de cadenas; sin embargo, estos lenguajes carecen de una comparación general de tres vías de otros tipos de datos.

El operador de comparación de tres vías u "operador de nave espacial" para números se denota como <=>en Perl , Ruby , Apache Groovy , PHP , Eclipse Ceylon y C++ , y se llama operador de nave espacial . ^[2]

En C++ , la revisión C++20 agrega el operador de nave espacial <=>, que devuelve un valor que codifica si los 2 valores son iguales, menores, mayores o desordenados y puede devolver diferentes tipos dependiendo de lo estricto de la comparación. ^[3]

El origen del nombre se debe a que le recuerda a Randal L. Schwartz a la nave espacial de un juego HP BASIC Star Trek ^{. [4]} Otro codificador ha sugerido que se llamó así porque se parecía al caza TIE de Darth Vader en la saga Star Wars . ^[5]

Ejemplo en PHP:

eco  1  <=>  1 ;  // 0 eco  1  <=>  2 ;  // -1 eco  2  <=>  1 ;  // 1

Ejemplo en C++:

1 <=> 1 ; // se evalúa como std::strong_ordering::equal 1 <=> 2 ; // se evalúa como std::strong_ordering::less 2 <=> 1 ; // se evalúa como std::strong_ordering::greater         

Las comparaciones de tres vías tienen la propiedad de ser fáciles de componer y construir comparaciones lexicográficas de tipos de datos no primitivos, a diferencia de las comparaciones de dos vías.

Aquí hay un ejemplo de composición en Perl.

sub comparar ($$) { mi ( $a , $b ) = @_ ; devolver $a -> { unidad } cmp $b -> { unidad } || $a -> { rango } <=> $b -> { rango } || $a -> { nombre } cmp $b -> { nombre }; }                   

Tenga en cuenta que cmp, en Perl, es para cadenas, ya que <=>es para números. Los equivalentes de dos vías tienden a ser menos compactos, pero no necesariamente menos legibles. Lo anterior aprovecha la evaluación de cortocircuito del ||operador y el hecho de que 0 se considera falso en Perl. Como resultado, si la primera comparación es igual (por lo tanto, se evalúa como 0), "pasará a la segunda comparación, y así sucesivamente, hasta que encuentre una que no sea cero, o hasta que llegue al final.

En algunos lenguajes, incluidos Python , Ruby , Haskell , etc., la comparación de listas se realiza lexicográficamente, lo que significa que es posible construir una cadena de comparaciones como el ejemplo anterior colocando los valores en listas en el orden deseado; por ejemplo, en Ruby:

[ a . unidad , a . rango , a . nombre ] <=> [ b . unidad , b . rango , b . nombre ]      

En C++:

std :: tie ( a.unidad , a.rango , a.nombre ) <=> std :: tie ( b.unidad , b.rango , b.nombre )​​​​​​​​​​​​      

• cadena