Error de Java: el método de comparación viola su contrato general

84

Vi muchas preguntas sobre esto e intenté resolver el problema, pero después de una hora de búsqueda en Google y muchas pruebas y errores, todavía no puedo solucionarlo. Espero que algunos de ustedes capten el problema.

Esto es lo que obtengo:

java.lang.IllegalArgumentException: Comparison method violates its general contract!
    at java.util.ComparableTimSort.mergeHi(ComparableTimSort.java:835)
    at java.util.ComparableTimSort.mergeAt(ComparableTimSort.java:453)
    at java.util.ComparableTimSort.mergeForceCollapse(ComparableTimSort.java:392)
    at java.util.ComparableTimSort.sort(ComparableTimSort.java:191)
    at java.util.ComparableTimSort.sort(ComparableTimSort.java:146)
    at java.util.Arrays.sort(Arrays.java:472)
    at java.util.Collections.sort(Collections.java:155)
    ...

Y este es mi comparador:

@Override
public int compareTo(Object o) {
    if(this == o){
        return 0;
    }

    CollectionItem item = (CollectionItem) o;

    Card card1 = CardCache.getInstance().getCard(cardId);
    Card card2 = CardCache.getInstance().getCard(item.getCardId());

    if (card1.getSet() < card2.getSet()) {
        return -1;
    } else {
        if (card1.getSet() == card2.getSet()) {
            if (card1.getRarity() < card2.getRarity()) {
                return 1;
            } else {
                if (card1.getId() == card2.getId()) {
                    if (cardType > item.getCardType()) {
                        return 1;
                    } else {
                        if (cardType == item.getCardType()) {
                            return 0;
                        }
                        return -1;
                    }
                }
                return -1;
            }
        }
        return 1;
    }
}

¿Alguna idea?

Lakatos Gyula
fuente
¿Qué línea de código hace que se lance esta excepción? ¿Qué hay en las líneas 835 y 453 de ComparableTimSort.java?
Hovercraft Full Of Eels
Me parece que debería tener este método delegado a la Cardclase: return card1.compareTo(card2)e implementar esta lógica allí.
Hunter McMillen
2
@HovercraftFullOfEels Es una clase de Oracle, no escrita por mí. Es una excepción en esa línea. El método es muy largo y parece difícil de entender.
Lakatos Gyula
@HunterMcMillen No puedo hacer eso. La tarjeta solo contiene los datos estáticos de una tarjeta (nombre, texto, etc.) mientras que esta clase contiene algunas variables cambiantes como el tipo y la cantidad.
Lakatos Gyula
1
Después de leer el libro Clean Code, tampoco lo sé.
Lakatos Gyula

Respuestas:

97

El mensaje de excepción es bastante descriptivo. El contrato se menciona es la transitividad : si A > By B > Centonces para cualquier A, By C: A > C. Lo revisé con papel y lápiz y su código parece tener algunos agujeros:

if (card1.getRarity() < card2.getRarity()) {
  return 1;

no vuelves -1si card1.getRarity() > card2.getRarity().


if (card1.getId() == card2.getId()) {
  //...
}
return -1;

Volverá -1si los id no son iguales. Debería regresar -1o 1dependiendo de qué identificación era más grande.


Mira esto. Además de ser mucho más legible, creo que debería funcionar:

if (card1.getSet() > card2.getSet()) {
    return 1;
}
if (card1.getSet() < card2.getSet()) {
    return -1;
};
if (card1.getRarity() < card2.getRarity()) {
    return 1;
}
if (card1.getRarity() > card2.getRarity()) {
    return -1;
}
if (card1.getId() > card2.getId()) {
    return 1;
}
if (card1.getId() < card2.getId()) {
    return -1;
}
return cardType - item.getCardType();  //watch out for overflow!
Tomasz Nurkiewicz
fuente
15
En realidad, el ejemplo que dio no viola la transitividad, pero la regla sgn (compare (x, y)) == -sgn (compare (y, x)) como se indica en docs.oracle.com/javase/7/docs/ api / java / util /… - eso es antisimetría en términos matemáticos.
Hans-Peter Störr
1
Sugeriría usarlo if (card1.getSet() != card2.getSet()) return card1.getSet() > card2.getSet() ? 1 : -1;para obtener más velocidad, si a alguien le importa.
maaartinus
Encontré esto y fue un problema de simetría en mi Comparador. La parte difícil de diagnosticar fue que mi debilidad fue el primer campo (una verificación de campo booleano, no una comparación adecuada) que no verificaba que ambos fueran verdaderos y correctos. Sin embargo, esto solo se expuso después de que agregué una comparación subordinada posterior que debe haber perturbado el orden de clasificación.
Thomas W
1
@maaartinus ¡gracias por tu sugerencia! Fue perfecto para mí :)
Sonhja
45

Puede usar la siguiente clase para identificar errores de transitividad en sus comparadores:

/**
 * @author Gili Tzabari
 */
public final class Comparators
{
    /**
     * Verify that a comparator is transitive.
     *
     * @param <T>        the type being compared
     * @param comparator the comparator to test
     * @param elements   the elements to test against
     * @throws AssertionError if the comparator is not transitive
     */
    public static <T> void verifyTransitivity(Comparator<T> comparator, Collection<T> elements)
    {
        for (T first: elements)
        {
            for (T second: elements)
            {
                int result1 = comparator.compare(first, second);
                int result2 = comparator.compare(second, first);
                if (result1 != -result2)
                {
                    // Uncomment the following line to step through the failed case
                    //comparator.compare(first, second);
                    throw new AssertionError("compare(" + first + ", " + second + ") == " + result1 +
                        " but swapping the parameters returns " + result2);
                }
            }
        }
        for (T first: elements)
        {
            for (T second: elements)
            {
                int firstGreaterThanSecond = comparator.compare(first, second);
                if (firstGreaterThanSecond <= 0)
                    continue;
                for (T third: elements)
                {
                    int secondGreaterThanThird = comparator.compare(second, third);
                    if (secondGreaterThanThird <= 0)
                        continue;
                    int firstGreaterThanThird = comparator.compare(first, third);
                    if (firstGreaterThanThird <= 0)
                    {
                        // Uncomment the following line to step through the failed case
                        //comparator.compare(first, third);
                        throw new AssertionError("compare(" + first + ", " + second + ") > 0, " +
                            "compare(" + second + ", " + third + ") > 0, but compare(" + first + ", " + third + ") == " +
                            firstGreaterThanThird);
                    }
                }
            }
        }
    }

    /**
     * Prevent construction.
     */
    private Comparators()
    {
    }
}

Simplemente invoca Comparators.verifyTransitivity(myComparator, myCollection)delante del código que falla.

Gili
fuente
3
Este código valida compare (a, b) = - compare (b, c). No comprueba que si compara (a, b)> 0 && compare (b, c)> 0, entonces compare (a, c)> 0
Olaf Achthoven
3
Realmente encontré tu clase muy, muy útil. Gracias.
crigore
Gracias, tuve que regresar y votar a favor de la respuesta, ya que esta clase es muy útil al depurar un comparador, no solo para el propósito mencionado aquí, ya que también se puede cambiar para probar otras circunstancias.
Jaco-Ben Vosloo
36

También tiene algo que ver con la versión de JDK. Si funciona bien en JDK6, tal vez tenga el problema en JDK 7 descrito por usted, porque se ha cambiado el método de implementación en jdk 7.

Mira esto:

Descripción: el algoritmo de clasificación utilizado por java.util.Arrays.sorty (indirectamente) por java.util.Collections.sortha sido reemplazado. La nueva implementación de ordenación puede lanzar un IllegalArgumentExceptionsi detecta un Comparableque viola el Comparablecontrato. La implementación anterior ignoró silenciosamente tal situación. Si desea el comportamiento anterior, puede utilizar la nueva propiedad del sistema java.util.Arrays.useLegacyMergeSort, para restaurar el comportamiento anterior de ordenación por combinación.

No sé la razón exacta. Sin embargo, si agrega el código antes de usar sort. Estará bien.

System.setProperty("java.util.Arrays.useLegacyMergeSort", "true");
Justin Civi
fuente
1
El problema estaba en la lógica que usé para comparar cosas. Votaré esto, espero que pueda ayudar a alguien que esté buscando este tipo de problema.
Lakatos Gyula
10
Eso solo debe usarse como una solución rápida y fea para que las cosas funcionen nuevamente hasta que arregle el comparador. Si ocurre la excepción, significa que su comparador tiene errores y el orden de clasificación será extraño. Debe considerar todas las reglas dadas en docs.oracle.com/javase/7/docs/api/java/util/… .
Hans-Peter Störr
¿Qué pasa si "raro" es lo que estaba buscando? (a,b) -> { return (new int[]{-1,1})[(int)((Math.random()*2)%2)]}Sé que Collections.shuffleexiste, pero no me gusta estar sobreprotegido.
Cueva Jefferey
Tengo una aplicación antigua y con JDK8 recibí este error. Usar JDK6 funciona correctamente, así que simplemente bajé a 6, gracias.
Stefano Scarpanti
6

Considere el siguiente caso:

Primero, o1.compareTo(o2)se llama. card1.getSet() == card2.getSet()resulta ser cierto y también lo es card1.getRarity() < card2.getRarity(), por lo que devuelve 1.

Entonces, o2.compareTo(o1)se llama. De nuevo, card1.getSet() == card2.getSet()es cierto. Luego, pasa a lo siguiente else, luego card1.getId() == card2.getId()resulta ser cierto, y también lo es cardType > item.getCardType(). Devuelve 1 de nuevo.

De eso o1 > o2, y o2 > o1. Rompiste el contrato.

eran
fuente
2
        if (card1.getRarity() < card2.getRarity()) {
            return 1;

Sin embargo, si card2.getRarity()es menor que, card1.getRarity()es posible que no devuelva -1 .

De manera similar, echas de menos otros casos. Yo haría esto, puedes cambiar dependiendo de tu intención:

public int compareTo(Object o) {    
    if(this == o){
        return 0;
    }

    CollectionItem item = (CollectionItem) o;

    Card card1 = CardCache.getInstance().getCard(cardId);
    Card card2 = CardCache.getInstance().getCard(item.getCardId());
    int comp=card1.getSet() - card2.getSet();
    if (comp!=0){
        return comp;
    }
    comp=card1.getRarity() - card2.getRarity();
    if (comp!=0){
        return comp;
    }
    comp=card1.getSet() - card2.getSet();
    if (comp!=0){
        return comp;
    }   
    comp=card1.getId() - card2.getId();
    if (comp!=0){
        return comp;
    }   
    comp=card1.getCardType() - card2.getCardType();

    return comp;

    }
}
Joe
fuente
1

También podría ser un error de OpenJDK ... (no en este caso, pero es el mismo error)

Si alguien como yo se topa con esta respuesta con respecto al

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

entonces también podría ser un error en la versión de Java. Tengo un compareTo funcionando desde hace varios años en algunas aplicaciones. Pero de repente dejó de funcionar y arroja el error después de que se realizaron todas las comparaciones (comparo 6 atributos antes de devolver "0").

Ahora acabo de encontrar este informe de error de OpenJDK:

leole
fuente
1

Tuve el mismo síntoma. Para mí, resultó que otro hilo estaba modificando los objetos comparados mientras se realizaba la clasificación en una secuencia. Para resolver el problema, asigné los objetos a objetos temporales inmutables, recogí el Stream en una Colección temporal e hice la clasificación.

Carl Rosenberger
fuente
0

Tuve que ordenar por varios criterios (fecha y, si es la misma fecha; otras cosas ...). Lo que estaba funcionando en Eclipse con una versión anterior de Java, ya no funcionó en Android: el método de comparación viola el contrato ...

Después de leer en StackOverflow, escribí una función separada que llamé desde compare () si las fechas son las mismas. Esta función calcula la prioridad, según los criterios, y devuelve -1, 0 o 1 para comparar (). Parece que funciona ahora.

Jean Burkhardt
fuente
0

Recibí el mismo error con una clase como la siguiente StockPickBean. Llamado desde este código:

List<StockPickBean> beansListcatMap.getValue();
beansList.sort(StockPickBean.Comparators.VALUE);

public class StockPickBean implements Comparable<StockPickBean> {
    private double value;
    public double getValue() { return value; }
    public void setValue(double value) { this.value = value; }

    @Override
    public int compareTo(StockPickBean view) {
        return Comparators.VALUE.compare(this,view); //return 
        Comparators.SYMBOL.compare(this,view);
    }

    public static class Comparators {
        public static Comparator<StockPickBean> VALUE = (val1, val2) -> 
(int) 
         (val1.value - val2.value);
    }
}

Después de recibir el mismo error:

java.lang.IllegalArgumentException: ¡El método de comparación viola su contrato general!

Cambié esta línea:

public static Comparator<StockPickBean> VALUE = (val1, val2) -> (int) 
         (val1.value - val2.value);

a:

public static Comparator<StockPickBean> VALUE = (StockPickBean spb1, 
StockPickBean spb2) -> Double.compare(spb2.value,spb1.value);

Eso corrige el error.

pmkent
fuente
0

Me encontré con un problema similar en el que estaba tratando de ordenar un n x 2 2D arraynombre contestsque es una matriz 2D de enteros simples. Esto funcionó la mayoría de las veces, pero arrojó un error de tiempo de ejecución para una entrada: -

Arrays.sort(contests, (row1, row2) -> {
            if (row1[0] < row2[0]) {
                return 1;
            } else return -1;
        });

Error:-

Exception in thread "main" java.lang.IllegalArgumentException: Comparison method violates its general contract!
    at java.base/java.util.TimSort.mergeHi(TimSort.java:903)
    at java.base/java.util.TimSort.mergeAt(TimSort.java:520)
    at java.base/java.util.TimSort.mergeForceCollapse(TimSort.java:461)
    at java.base/java.util.TimSort.sort(TimSort.java:254)
    at java.base/java.util.Arrays.sort(Arrays.java:1441)
    at com.hackerrank.Solution.luckBalance(Solution.java:15)
    at com.hackerrank.Solution.main(Solution.java:49)

Mirando las respuestas anteriores, intenté agregar una condición equalsy no sé por qué, pero funcionó. Con suerte, debemos especificar explícitamente lo que se debe devolver para todos los casos (mayor que, igual y menor que):

        Arrays.sort(contests, (row1, row2) -> {
            if (row1[0] < row2[0]) {
                return 1;
            }
            if(row1[0] == row2[0]) return 0;
            return -1;
        });
Prateek Bhuwania
fuente