Many languages define that compare functions should return ANY negative value, zero, or ANY positive value. Is there some reason that it shouldn't be clearly defined as -1 0 and 1? Does a wide range in possible return values help more advanced algorithms to work more efficiently? If so, what algorithms work this way?
4 Answers
If you allow comparison function to return any negative value instead of exactly -1, this can make for a simpler implementation. For instance, you can write
return this.position - that.position;
instead of having to write
if(this.position == that.position) {
return 0;
}
else if(this.position < that.position) {
return -1;
} else
return 1;
}
(The alternative is to use an operator, like Perl's <=>, that generates exactly -1, 0, or 1. But it's easier to define a lenient API than to get a new operator into your language, unless you're Larry Wall.)
answered Jan 13, 2015 at 8:31
-
3To add a very important point: As a rule of thumb arithmetic operations are almost faster than if-statements on almost every hardware. That's because if-statements need more complex binary code, namely the jump statements in assembler code are very time consuming. In other words the processing unit has to handle more complex statements and therefore to touch more statements internally.– shylynxJan 13, 2015 at 10:31
-
The other important thing to note is that while this implementation of comparison is both simpler and faster than the version that must return specific values, the processor can check for negative, zero or positive conditions just as easily and efficiently as it can for specific values, so taken over both the calculation and the use of the comparison there is a net gain of efficiency.– JulesJan 13, 2015 at 20:27
-
Note that this approach only works if the type of
positionis smaller than the return type of the comparison function. For example in Java,Integer.MAX_VALUEis bigger than-1, butInteger.MAX_VALUE - (-1)is negative due to overflow. Jan 14, 2015 at 9:35
For simple use cases it allows for a very trivial implementation:
public int compare(Child a, Child b) {
return a.age - b.age;
}
//sort children by age to determine who babysits
Meanwhile if more complex logic is required it is still easy to return the magic numbers -1, 0, or 1 once order is determined.
As CodesInChaos says in the comments the subtraction method fails to accommodate any overflow that may occur. General purpose libraries require greater robustness and complexity in their comparisons.
Here are a couple of a battle tested implementations:
Java's
Integer.compare():public static int compare(int x, int y) { return (x < y) ? -1 : ((x == y) ? 0 : 1); }Mono's
Int32.CompareTo():public int CompareTo (object value) { if (value == null) return 1; if (!(value is System.Int32)) throw new ArgumentException (Locale.GetText ("Value is not a System.Int32")); int xv = (int) value; if (m_value == xv) return 0; if (m_value > xv) return 1; else return -1; }
As you can see both of these apply the required logic then return the appropriate magic number.
-
1Which won't work in most languages due to integer overflows. Similarly negating the value to reverse the ordering doesn't work for two's complement integers. Jan 13, 2015 at 11:01
-
@CodesInChaos Very true, I've clarified that it is a toy example. Jan 13, 2015 at 15:38
-
@CodesInChaos Got any children older than a billion years? Combined with one who is younger than minus a billion? Yes, then you can worry about overflows on the subtractions. I don't understand your comment on the negating. Jan 13, 2015 at 15:46
-
@user949300 1) Why would you write specific comparison code for the age of humans? You write that code once, so it's correct for every integer, and then reuse it. For example for the
Childtype, you'd write something likereturn child1.Age.CompareTo(child2.Age)whereint.CompareToneeds to handle every integer. 2)-int.MinValue == int.MinValue, so negating doesn't change the sign for this case. Jan 13, 2015 at 16:08 -
1The fact that in the general case overflow may occur does not mean this technique cannot be used; there are many specific cases where it is valid: comparing chars (on systems where sizeof(char) < sizeof(int), which is mostly true) is probably the most important.– JulesJan 13, 2015 at 20:32
Return value semantics has almost nothing to do with implementation. This specification leaves no space for unspecified behavior and is statically verifiable.
If return value is specified to be an arbitrary number, this can checked statically - compiler can easily verify that function doesn't return string. Otherwise static verification is impossible - values that are outside of given range can't be eliminated statically for non-enum types. Therefore calling code will have to deal with unspecified values in runtime, emitting more unspecified behavior.
We can safely say that this decision is made to mimic behavior Jörg described in his comment - complete specification, every option covered.
It's because when you do a compare you are usually just taking the difference of two values and instead of wasting more time and effort into mapping the result to {-1,0,1}, just leave the result and define the function as so. For example x.comparedTo(y) = 0 means that if x and y are both 5, (5 - 5) = 0 but if x = 100 and y = 150, (100 - 150) = -50 and so x < y.
-
2this seems to merely repeat point made (and better explained) in prior answer– gnatJan 13, 2015 at 9:03
Eq | Lt | Gt. Yet another thing that is wrong with the above definition, at least in languages with universal comparability, is that it assumes a total ordering, IOW, there is no way to indicate "these two values can't be ordered". You actually would need an enumEq | Lt | Gt | Neither.