Three-way Comparison
   HOME

TheInfoList



OR:

In
computer science Computer science is the study of computation, automation, and information. Computer science spans theoretical disciplines (such as algorithms, theory of computation, information theory, and automation) to Applied science, practical discipli ...
, a three-way comparison takes two values A and B belonging to a type with a
total order In mathematics, a total or linear order is a partial order in which any two elements are comparable. That is, a total order is a binary relation \leq on some set X, which satisfies the following for all a, b and c in X: # a \leq a ( reflexive) ...
and determines whether A < B, A = B, or A > B in a single operation, in accordance with the mathematical
law of trichotomy In mathematics, the law of trichotomy states that every real number is either positive, negative, or zero. ...
.


Machine-level computation

Many processors have
instruction set In computer science, an instruction set architecture (ISA), also called computer architecture, is an abstract model of a computer. A device that executes instructions described by that ISA, such as a central processing unit (CPU), is called an ' ...
s that support such an operation on primitive types. Some machines have signed
integer An integer is the number zero (), a positive natural number (, , , etc.) or a negative integer with a minus sign (−1, −2, −3, etc.). The negative numbers are the additive inverses of the corresponding positive numbers. In the language ...
s based on a sign-and-magnitude or one's complement representation (see
signed number representations In computing, signed number representations are required to encode negative numbers in binary number systems. In mathematics, negative numbers in any base are represented by prefixing them with a minus sign ("−"). However, in RAM or CPU regis ...
), both of which allow a differentiated positive and negative
zero 0 (zero) is a number representing an empty quantity. In place-value notation Positional notation (or place-value notation, or positional numeral system) usually denotes the extension to any base of the Hindu–Arabic numeral system (or ...
. This does not violate trichotomy as long as a consistent total order is adopted: either −0 = +0 or −0 < +0 is valid. Common
floating point In computing, floating-point arithmetic (FP) is arithmetic that represents real numbers approximately, using an integer with a fixed precision, called the significand, scaled by an integer exponent of a fixed base. For example, 12.345 can be ...
types, however, have an exception to trichotomy: there is a special value "NaN" (
Not a Number Nan or NAN may refer to: Places China * Nan County, Yiyang, Hunan, China * Nan Commandery, historical commandery in Hubei, China Thailand * Nan Province ** Nan, Thailand, the administrative capital of Nan Province * Nan River People Given name ...
) such that ''x'' < NaN, ''x'' > NaN, and ''x'' = NaN are all false for all floating-point values ''x'' (including NaN itself).


High-level languages


Capabilities

In C, the functions strcmp and memcmp perform a three-way comparison between strings and memory buffers, respectively. They return a negative number when the first argument is
lexicographically In mathematics, the lexicographic or lexicographical order (also known as lexical order, or dictionary order) is a generalization of the alphabetical order of the dictionaries to sequences of ordered symbols or, more generally, of elements of a ...
smaller than the second, zero when the arguments are equal, and a positive number otherwise. This convention of returning the "sign of the difference" is extended to arbitrary comparison functions by the standard sorting function
qsort qsort is a C standard library function that implements a polymorphic sorting algorithm for arrays of arbitrary objects according to a user-provided comparison function. It is named after the "quicker sort" algorithm (a quicksort variant due to R ...
, which takes a comparison function as an argument and requires it to abide by it. In
C++ C++ (pronounced "C plus plus") is a high-level general-purpose programming language created by Danish computer scientist Bjarne Stroustrup as an extension of the C programming language, or "C with Classes". The language has expanded significan ...
, the
C++20 C++20 is a version of the ISO/IEC 14882 standard for the C++ programming language. C++20 replaced the prior version of the C++ standard, called C++17. The standard was technically finalized by WG21 at the meeting in Prague in February 2020, a ...
revision adds the "spaceship operator" <=>, which similarly returns the sign of the difference and can also return different types (convertible to signed integers) depending on the strictness of the comparison. In
Perl Perl is a family of two high-level, general-purpose, interpreted, dynamic programming languages. "Perl" refers to Perl 5, but from 2000 to 2019 it also referred to its redesigned "sister language", Perl 6, before the latter's name was offici ...
(for numeric comparisons only, the cmp operator is used for string lexical comparisons),
PHP PHP is a general-purpose scripting language geared toward web development. It was originally created by Danish-Canadian programmer Rasmus Lerdorf in 1993 and released in 1995. The PHP reference implementation is now produced by The PHP Group ...
(since version 7),
Ruby A ruby is a pinkish red to blood-red colored gemstone, a variety of the mineral corundum ( aluminium oxide). Ruby is one of the most popular traditional jewelry gems and is very durable. Other varieties of gem-quality corundum are called sa ...
, and
Apache Groovy Apache Groovy is a Java-syntax-compatible object-oriented programming language for the Java platform. It is both a static and dynamic language with features similar to those of Python, Ruby, and Smalltalk. It can be used as both a programming lan ...
, the "spaceship operator" <=> returns the values −1, 0, or 1 depending on whether A < B, A = B, or A > B, respectively. The Python 2.x cmp(removed in 3.x),
OCaml OCaml ( , formerly Objective Caml) is a general-purpose programming language, general-purpose, multi-paradigm programming language which extends the Caml dialect of ML (programming language), ML with object-oriented programming, object-oriented ...
compare, and Kotlin compareTo functions compute the same thing. In the
Haskell Haskell () is a general-purpose, statically-typed, purely functional programming language with type inference and lazy evaluation. Designed for teaching, research and industrial applications, Haskell has pioneered a number of programming lan ...
standard library, the three-way comparison function compare is defined for all types in the Ord
class Class or The Class may refer to: Common uses not otherwise categorized * Class (biology), a taxonomic rank * Class (knowledge representation), a collection of individuals or objects * Class (philosophy), an analytical concept used differentl ...
; it returns type Ordering, whose values are LT (less than), EQ (equal), and GT (greater than): data Ordering = LT , EQ , GT Many object-oriented languages have a three-way comparison
method Method ( grc, μέθοδος, methodos) literally means a pursuit of knowledge, investigation, mode of prosecuting such inquiry, or system. In recent centuries it more often means a prescribed process for completing a task. It may refer to: *Scien ...
, which performs a three-way comparison between the object and another given object. For example, in
Java Java (; id, Jawa, ; jv, ꦗꦮ; su, ) is one of the Greater Sunda Islands in Indonesia. It is bordered by the Indian Ocean to the south and the Java Sea to the north. With a population of 151.6 million people, Java is the world's List ...
, any class that implements the Comparable interface has
compareTo
method which either returns a negative integer, zero, or a positive integer, or throws a NullPointerException (if one or both objects are null). Similarly, in the
.NET Framework The .NET Framework (pronounced as "''dot net"'') is a proprietary software framework developed by Microsoft that runs primarily on Microsoft Windows. It was the predominant implementation of the Common Language Infrastructure (CLI) until bein ...
, any class that implements the IComparable interface has such
CompareTo
method. Since Java version 1.5, the same can be computed using the Math.signum static method if the difference can be known without computational problems such as
arithmetic overflow Arithmetic () is an elementary part of mathematics that consists of the study of the properties of the traditional operations on numbers—addition, subtraction, multiplication, division, exponentiation, and extraction of roots. In the 19th cen ...
mentioned below. Many computer languages allow the definition of functions so a ''compare(A,B)'' could be devised appropriately, but the question is whether or not its internal definition can employ some sort of three-way syntax or else must fall back on repeated tests. When implementing a three-way comparison where a three-way comparison operator or method is not already available, it is common to combine two comparisons, such as A = B and A < B, or A < B and A > B. In principle, a compiler might deduce that these two expressions could be replaced by only one comparison followed by multiple tests of the result, but mention of this optimisation is not to be found in texts on the subject. In some cases, three-way comparison can be simulated by subtracting A and B and examining the sign of the result, exploiting special instructions for examining the sign of a number. However, this requires the type of A and B to have a well-defined difference. Fixed-width signed integers may overflow when they are subtracted, floating-point numbers have the value NaN with undefined sign, and character strings have no difference function corresponding to their total order. At the machine level, overflow is typically tracked and can be used to determine order after subtraction, but this information is not usually available to higher-level languages. In one case of a three-way conditional provided by the programming language, Fortran's now-deprecated three-way
arithmetic IF The arithmetic IF statement is a three-way arithmetic conditional statement, first seen in the first release of Fortran in 1957, and found in all later versions, and some other programming languages, such as FOCAL. Unlike the logical IF stateme ...
statement considers the sign of an arithmetic expression and offers three labels to jump to according to the sign of the result: IF (expression) negative,zero,positive The common library function strcmp in C and related languages is a three-way lexicographic comparison of strings; however, these languages lack a general three-way comparison of other data types.


Spaceship operator

The three-way comparison operator for numbers is denoted as <=> in
Perl Perl is a family of two high-level, general-purpose, interpreted, dynamic programming languages. "Perl" refers to Perl 5, but from 2000 to 2019 it also referred to its redesigned "sister language", Perl 6, before the latter's name was offici ...
,
Ruby A ruby is a pinkish red to blood-red colored gemstone, a variety of the mineral corundum ( aluminium oxide). Ruby is one of the most popular traditional jewelry gems and is very durable. Other varieties of gem-quality corundum are called sa ...
,
Apache Groovy Apache Groovy is a Java-syntax-compatible object-oriented programming language for the Java platform. It is both a static and dynamic language with features similar to those of Python, Ruby, and Smalltalk. It can be used as both a programming lan ...
,
PHP PHP is a general-purpose scripting language geared toward web development. It was originally created by Danish-Canadian programmer Rasmus Lerdorf in 1993 and released in 1995. The PHP reference implementation is now produced by The PHP Group ...
, Eclipse Ceylon, and
C++ C++ (pronounced "C plus plus") is a high-level general-purpose programming language created by Danish computer scientist Bjarne Stroustrup as an extension of the C programming language, or "C with Classes". The language has expanded significan ...
, and is called the ''spaceship operator''. The name's origin is due to it reminding Randal L. Schwartz of the spaceship in an HP BASIC ''
Star Trek ''Star Trek'' is an American science fiction media franchise created by Gene Roddenberry, which began with the eponymous 1960s television series and quickly became a worldwide pop-culture phenomenon. The franchise has expanded into vari ...
'' game. Another coder has suggested that it was so named because it looked similar to Darth Vader's
TIE fighter The Twin Ion Engine (TIE) fighter is a series of fictional starfighters featured in the '' Star Wars'' universe. TIE fighters are depicted as fast, agile, yet fragile starfighters produced by Sienar Fleet Systems for the Galactic Empire and b ...
in the ''
Star Wars ''Star Wars'' is an American epic film, epic space opera multimedia franchise created by George Lucas, which began with the Star Wars (film), eponymous 1977 film and quickly became a worldwide popular culture, pop-culture Cultural impact of S ...
'' saga. Example in PHP: echo 1 <=> 1; // 0 echo 1 <=> 2; // -1 echo 2 <=> 1; // 1


Composite data types

Three-way comparisons have the property of being easy to compose and build
lexicographic Lexicography is the study of lexicons, and is divided into two separate academic disciplines. It is the art of compiling dictionaries. * Practical lexicography is the art or craft of compiling, writing and editing dictionaries. * Theoretica ...
comparisons of non-primitive data types, unlike two-way comparisons. Here is a composition example in Perl. sub compare($$) Note that cmp, in Perl, is for strings, since <=> is for numbers. Two-way equivalents tend to be less compact but not necessarily less legible. The above takes advantage of
short-circuit evaluation A short circuit (sometimes abbreviated to short or s/c) is an electrical circuit that allows a current to travel along an unintended path with no or very low electrical impedance. This results in an excessive current flowing through the circuit. ...
of the , , operator, and the fact that 0 is considered false in Perl. As a result, if the first comparison is equal (thus evaluates to 0), it will "fall through" to the second comparison, and so on, until it finds one that is non-zero, or until it reaches the end. In some languages, including
Python Python may refer to: Snakes * Pythonidae, a family of nonvenomous snakes found in Africa, Asia, and Australia ** ''Python'' (genus), a genus of Pythonidae found in Africa and Asia * Python (mythology), a mythical serpent Computing * Python (pro ...
,
Ruby A ruby is a pinkish red to blood-red colored gemstone, a variety of the mineral corundum ( aluminium oxide). Ruby is one of the most popular traditional jewelry gems and is very durable. Other varieties of gem-quality corundum are called sa ...
,
Haskell Haskell () is a general-purpose, statically-typed, purely functional programming language with type inference and lazy evaluation. Designed for teaching, research and industrial applications, Haskell has pioneered a number of programming lan ...
, etc., comparison of lists is done lexicographically, which means that it is possible to build a chain of comparisons like the above example by putting the values into lists in the order desired; for example, in Ruby: .unit, a.rank, a.name<=> .unit, b.rank, b.name/syntaxhighlight>


See also

* strcmp


References

{{DEFAULTSORT:Three-Way Comparison Conditional constructs Operators (programming)