Standard Deviation is not transitive?

Question

I am trying to implement a Comparator, considering that the objects going to be compared (Word) have two properties defined as int.

I want to get the standard deviation from these two values (may be more, but 2 now), and sort my list by which objects have the lowest one. But apparently, it is saying that my method is not transitive based on this question (I presume, since I've got the same exception). But I cannot see how, here it will just compare the results of the standard deviation.

Am I confused with the math and did not consider a special case where points out that this method is not transitive or have I done something wrong?

Sorting the list:

for(Map.Entry<String,List<Word>> entry: list.entrySet()){
 Collections.sort(entry.getValue(), Collections.reverseOrder(new SimpleComparator()));
 ...
}

Comparator Class:

import java.util.Comparator;

public class SimpleComparator implements Comparator<Word> {
    @Override
    public int compare(Word word1, Word word2) {
        int b1,b2,f1,f2;
        double average1,average2, result1,result2;
        b1 = word1.getAttr1();
        b2 = word2.getAttr1();
        f1 = word1.getAttr2();
        f2 = word2.getAttr2();
        average1 = (b1-f1)/2;
        average2 = (b2-f2)/2;
        result1 = Math.sqrt((Math.pow(b1-average1,2)+Math.pow(f1-average1,2))/2);
        result2 = Math.sqrt((Math.pow(b2-average2,2)+Math.pow(f2-average2,2))/2);
        return (int)(result1 - result2);
    }
}

Because of rounding, your comparator is inconsistent with equals. I think you want to use (for example) ?: to get -1, 0, and 1 as the results. — Andrew Lazarus, Nov 12 '14 at 05:40

Andy Senn · Accepted Answer · 2014-11-12T06:39:47.773

3

You should use Math.signum(result1 - result2), which will produce a -1 if the result is negative, 0 if the result is zero, and 1 if the result is positive. Make sure to keep the result as a double - The truncation that occurs when casting a double to an int would yield inaccurate results.

Instead, replace your return statement with:

return (int) Math.signum( result1 - result2 );

In this case, the result of 0.9 - 0.3 would be 0.6, the signum of which would be 1. However, if we were to cast the double 0.6 to an int, the result would be 0, not 1, indicating that they are equal. However, we know that this is not true. The reason for this is that when casting a numeric data type to one of lower precision, the value is not rounded - it simply loses precision, meaning that the values after the decimal point just fall off.

See the JavaDocs for Comparator.comare(T, T)

The implementor must ensure that sgn(compare(x, y)) == -sgn(compare(y, x)) for all x and y.

edited Nov 12 '14 at 06:39

answered Nov 12 '14 at 05:42

Andy Senn

649
5
13

Yeah, I thought that maybe the ugly casting was the problem, but I didn't know about `Math.signum(a,b)`. However, if I should keep with double, how I am going to Override the Compare method? – Patrick Bard Nov 12 '14 at 06:28
So, trying to stay with double, using `return Double.compare(result1,result2);` would be ok, right? – Patrick Bard Nov 12 '14 at 06:32
1

You don't need to return a double, you just need to keep the precision of the resulting double when calculating the difference. I'll update my answer to clarify. – Andy Senn Nov 12 '14 at 06:32
Yes, I know I don't need to return a double. That's why I couldn't use `Math.signum` with my Comparator. `Math.signum` returns a double, while `Double.compare` returns an int – Patrick Bard Nov 12 '14 at 06:36
Ah, I follow now. Yes, that would also work. It pretty much follows the same idea as Math.signum(...). – Andy Senn Nov 12 '14 at 06:42

Xline · Answer 2 · 2014-11-12T06:27:11.753

Your compare(x1,x2) method violates the condition:

the implementor must ensure that compare(x, y)==0 implies that sgn(compare(x, z))==sgn(compare(y, z)) for all z.

Here is a counter example to your method where compare(w1,w2)=0

public static void main(String[] args) {

 Word w1=new Word(2,5);
 Word w2=new Word(1,5);
 Word w3=new Word(2,4);

    System.out.println(Math.signum(getStandardDeviation(w1, w3))==Math.signum(getStandardDeviation(w2, w3)));
}

public static double getStandardDeviation(Word word1,Word word2)
{
    int b1,b2,f1,f2;
    double average1,average2, result1,result2;
    b1 = word1.getAttr1();
    b2 = word2.getAttr1();
    f1 = word1.getAttr2();
    f2 = word2.getAttr2();
    average1 = (b1-f1)/2;
    average2 = (b2-f2)/2;
    result1 = Math.sqrt((Math.pow(b1-average1,2)+Math.pow(f1-average1,2))/2);
    result2 = Math.sqrt((Math.pow(b2-average2,2)+Math.pow(f2-average2,2))/2);
    return (int)(result1 - result2);
}

}

Standard Deviation is not transitive?

2 Answers2