Kniffliges Java-Problem mit sort-Methode

[Senior Sanchez]

Hallo,

ich habe ein kniffliges Problem, dass sich mit der Sortierung von Arrays via Arrays.sort() unter Java beschäftigt. Unter Java 6 läuft das fein, aber unter Java 7 gibt es da eine IllegalArgumentException, weil die Sortiermethode innerhalb Javas geändert wurde. Es geht um folgenden Fehler:

java.lang.IllegalArgumentException: Comparison method violates its general contract!

Diese Methode hier löst vermutlich den Fehler aus:


public int compare(IntDouble o1, IntDouble o2) {
if (o1.val < o2.val)
return -1;
if (o1.val > o2.val)
return 1;
if (o1.i < o2.i)
return -1;
if (o1.i > o2.i)
return 1;
return 0;
}


Das Attribut i ist dabei ein eindeutiger Integer während val ein double ist. Habt ihr eine idee, was mit dieser compare()-Funktion nicht stimmt? Sie verletzt irgendwie eine notwendige Eigenschaft an Sortierfunktionen ("contract"), die an die compare-Methode von Comparatoren gestellt wird. Mir fällt bloß kein passender Fall dazu ein.

Klar kann man über ein Flag das alte Sortierverhalten erzwingen, aber irgendetwas scheint ja nicht zu stimmen.

[Trap]

Es gibt 3 Eigenschaften die für alle möglichen Werte gelten müssen: http://docs.oracle.com/javase/7/docs/api/java/util/Comparator.html
Reflexivität -> compare(a,a)==0
Antisymmetrie -> compare(a,b)==-compare(b,a)
Transitivität -> compare(a,b)==-1 && compare(b,c)==-1 => compare(a,c)==-1

Wie deine Methode eine davon verletzen kann weiß ich spontan auch nicht. Vielleicht ist sie nicht transitiv...

Eventuell stimmt auch dein Equals für double.NaN nicht.

[EPIC_FAIL]

http://dertompson.com/2012/11/23/sort-algorithm-changes-in-java-7/
Schau mal da.

Ich gehe mal stark davon aus, dass bei deinem Code auch je nach Reihenfolge der Vergleiche unterschiedliche Werte per return zurückgegeben werden. Das würde die Eigenschaft der Symmetrie verletzten.

[Gast]

Könnte mir Vorstellen, dass das Problem sein könnte, dass gleichzeitig x.val < y.val, aber x.i > y.i gelten kann, und dadurch von der Reihenfolge der Vergleiche abhängt, ob das Ergebnis 1 oder -1 ist.

Ob das laut Applikationslogik überhaupt möglich ist, sieht Java ja nicht.

Wie sich das mit dem Kontrakt beisst, sehe ich aber nicht, sofern er wirklich nur die 3 von Trap genannten Punkte beinhaltet.

[#44]

Eventuell stimmt auch dein Equals für double.NaN nicht.
Ich würde auch vermuten, dass NaN am ehesten für das Problem verantwortlich ist, da die Vergleichsoperatoren hier immer false liefern und damit die Transitivität verletzt werden kann.

Kommt NaN in deiner zu sortierenden Menge vor?

Die compare-Methode von Double kann mit NaN umgehen:

public int compare(IntDouble o1, IntDouble o2) {
int dblRes = Double.compare(o1.val, o2.val);
if (dblRes == 0)
return o1.i - o2.i;
return dblRes;
}

[Senior Sanchez]

Ah, guter Tipp! An Double.NaN habe ich nicht gedacht, aber ich werde das mal ausprobieren.

[Ganon]

Ja, könntest du ja auch gleich Integer.compare nehmen. So in der Art:


public int compare(IntDouble o1, IntDouble o2) {
int res = Double.compare(o1.val, o2.val)
if (res == 0) {
return Integer.compare(o1.i, o2.i)
}
return res;
}


Finde ich "lesbarer" als o1.i - o2.i. Aber das musst du entscheiden :D

[Senior Sanchez]

Es sei an dieser Stelle angemerkt, dass der Code nicht von mir ist, sondern aus einer Bibliothek und die läuft unter Java 7 nicht sauber. ;)

Ich werde das so umstricken, denn ich denke, dass es an Double.NaN liegen muss. Nimmt man normale, reellwertige Zahlen an, werden alle Eigenschaften erfüllt.

Reflexivität:

1. Fall: a.val = a.val, a.i = a.i
compare(a,a) = 0

--> Reflexivität erfüllt

Antisymmetrie:

1. Fall: a.val > b.val, (a.i, b.i = don't care)
compare(a,b) = 1
compare(b,a) = -1

2. Fall: a.val < b.val (a.i, b.i = don't care)
compare(a,b) = -1
compare(b,a) = 1

3. Fall: a.val = b.val, a.i < b.i
compare(a,b) = -1
compare(b,a) = 1

4. Fall: a.val = b.val, a.i > b.i
compare(a,b) = 1
compare(b,a) = -1

--> Antisymmetrie erfüllt

Transitivität:

compare(a,b) = -1 && compare(b,c) = -1 --> compare(a,c) = -1

1. Fall: a.val < b.val, b.val < c.val
compare(a,c) = -1

2. Fall: a.i < b.i, b.i < c.i (wenn alle val gleich sind)
compare(a,c) = -1

--> Transitivität erfüllt

[Senior Sanchez]

Problem gelöst. Unter Nutzung eurer vorgeschlagenen Methoden klappt es. Wahrscheinlich waren da wirklich einige Double.NaNs Schuld.