CODEWITHSUNDEEP
javasorting
StepTNT
StepTNT

Reputation: 3967

Comparison method violates its general contract while sorting

Yeah, I know there are a lot of questions with the same issue but I really can't seem to find what's wrong with my comparator.

So, here it is:

evaluateComparator = (m1, m2) -> {
    Color color = m1.getColor(); // m1 and m2 will have the same one
    double m1Value, m2Value;
    if (sortingCache.containsKey(m1)) {
        m1Value = sortingCache.get(m1);
    } else {
        // The value has not been computed before so it's not in the cache and I need to compute it now     
        someClass.doSomething(m1);
        m1Value = someClass.getValue();
        someClass.undoSomething(m1);
        sortingCache.put(m1, m1Value);
    }
    if (sortingCache.containsKey(m2)) {
        m2Value = sortingCache.get(m2);
    } else {
        // The value has not been computed before so it's not in the cache and I need to compute it now     
        someClass.doSomething(m2);
        m2Value = someClass.getValue();
        someClass.undoSomething(m2);
        sortingCache.put(m2, m2Value);
    }
    // Since I'm comparing two doubles I can use the Double's comparator
    return Double.compare(m1Value, m2Value);
};

The code is quite simple: I need to sort some objects based on how they would change my main structure, and I want the highest values first.

Since computing the impact of the m1 or m2 objects may take some time, I just cache values in order to reuse them so, before sorting, I check if I have a cached value or if I need to compute it.

Once I computed the result of applying m1 or m2 to my structure, I revert the changes back.

You can see this like some kind of evaluation sorting taken from the AI's world: I want to sort the moves based on the board score that I'd have applying them.

Do you have any idea on this?

EDIT: Since something strange involving hashing and caching may be involved, I removed all the references to the cache but I still have the issue.

evaluateComparator = (m1, m2) -> {
    double m1Value, m2Value;

    someClass.doSomething(m1);
    m1Value = someClass.getValue();
    someClass.undoSomething(m1);

    someClass.doSomething(m2);
    m2Value = someClass.getValue();
    someClass.undoSomething(m2);

    return Double.compare(m1Value, m2Value);
};

Upvotes: 0

Views: 75

Answers (1)

Marko Topolnik
Marko Topolnik

Reputation: 200196

That doesn't exactly count as simple code for a comparator implementation. A lot of things could go wrong there and the critical code (doSomething and undoSomething) isn't shown. From the looks of it, m1 and m2 are mutable objects and if they change such that they are not equal to themselves from an earlier time, the sorting algorithm breaks. I see this as the most likely explanation of your error.

Another approach to fix your problem, and which I would recommend anyway, is rethinking your approach. Since any sorting algorithm must touch each value at least once, your lazy initialization scheme brings nothing but an overhead in complexity. Instead prepare a plain list of moves with their values baked in (you'll need an object representing both the move and its evaluation) and merely sort this list of immutable objects using their natural order (a trivial implementation of compareTo will do it). At that point your bug will be left with very little place to hide and could possibly disappear before you're done.

Upvotes: 1

Related Questions